Recursion and the Call Stack
A function that calls itself on a smaller version of the same problem, with a base case that stops the descent. Every call that has not returned yet waits on the call stack, which is why deep recursion runs out of room.
What a learner can do afterwards
- Write a recursive function with a base case and a case that shrinks the input
- Trace the call stack for a small input and say which call returns first
- Rewrite a simple loop as recursion, and say what a missing base case causes
1 · Read
A recursive function solves a problem by calling itself on a smaller version of the same problem. You always give it a base case, a tiny input it answers directly, and every other call must shrink the input toward that base.
Follow factorial: 0 factorial and 1 factorial both equal 1, and for bigger n, n factorial is n times n minus 1 factorial. To find 5 factorial you wait through 4, 3 and 2 factorial down to the base, then multiply back up to 120. Adding down works the same: sum to 3 is 3 plus 2 plus 1 plus 0, which is 6.
Every call that has not returned yet waits on the call stack. You push a frame per call and pop it on return, so the deepest call finishes first. Without a base case the calls never stop and the stack runs out of room. The palindrome check shows the same shape: compare the outer letters, then recurse on the middle until 1 letter or none remains, as level shrinks to eve and then to v.
You rewrite a loop as recursion by naming its stop as the base and its step as the shrink. A loop adding 1 to n becomes a base of 0 returning 0 plus n added to the call on n minus 1. If the input never shrinks, the base stays out of reach.
Shrink each call toward a base case, and the stack unwinds from the deepest call upward.
2 · Watch
Take it off screen
Where it sits
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.