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.
More to read
Simple math recursion
A factorial multiplies a whole number by every smaller whole number down to 1. So 5! (say it "5 factorial") means 5 x 4 x 3 x 2 x 1.
You can find a factorial with recursion. The base case is 0! or 1!, which both equal 1. For any bigger number n, the recursive case says: n! = n x (n - 1)!.
To find 5!, the function first needs 4!. To find 4!, it needs 3!. This keeps going until it hits the base case, 1! = 1. Then the answers multiply back up: 2! = 2 x 1 = 2, 3! = 3 x 2 = 6, 4! = 4 x 6 = 24, and 5! = 5 x 24 = 120.
Every one of those waiting calls sits on the call stack until the base case finally gives it something to multiply.
Recursion with strings and lists
A palindrome is a word spelled the same forward and backward, like racecar or level.
You can check if a word is a palindrome with recursion. The base case is a word with 0 or 1 letters, since a single letter or an empty string is always a palindrome.
For longer words, compare the first and last letters. If they do not match, the word is not a palindrome, so you can stop right there. If they do match, recurse on the middle part, leaving off the first and last letters.
Keep peeling letters off both ends until you either find a mismatch or shrink all the way down to the base case.
Chapter summary
A recursive function solves a problem by calling itself on a smaller version of the same problem. Every recursive function needs a base case, a simple version it can answer directly without calling itself again.
Recursion builds a bigger answer out of simpler answers, like multiplying numbers together for a factorial, or checking letters from the outside in for a palindrome.
Without a base case, a recursive function calls itself forever, and eventually the program runs out of room on the call stack and crashes.
How a program uses the call stack
Every time a program calls a function, the computer needs to remember where it was so it can come back after the function finishes. It does this with a call stack.
When a function is called, a new frame gets pushed onto the top of the stack. That frame holds the function's local variables and remembers which line to return to. When the function finishes and returns a value, its frame gets popped off, and the program picks up right where it left off in whatever called it.
This is exactly why deep recursion runs into trouble. Each recursive call pushes another frame onto the stack, and none of those frames can be removed until the calls above them finish and return. Go too deep, and the stack runs out of space entirely.
Explore more
2 · Watch
En anglaisTake it off screen
Where it sits
Learn first
Optional connections
18 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.