How does recursion actually work?
A recursive function solves a problem by calling itself on a smaller version of the same problem until it reaches a base case it can answer directly. Each call waits on the call stack, and the results combine as the calls return, in reverse order.
Two parts every recursive function needs
A base case answers the smallest version of the problem without recursing. A recursive case breaks the problem into a smaller version of itself and calls the function on that. Factorial is the classic example: n! = n × (n − 1)!, and 1! = 1. In code: if n ≤ 1, return 1; otherwise return n * factorial(n − 1).
Each recursive call has to move toward the base case. Here n drops by 1 each time, so it is guaranteed to reach 1.
Tracing factorial(4)
Each call gets its own frame on the call stack, holding its own copy of n. The calls go down first, then the answers come back up:
- factorial(4) needs factorial(3), so it pauses.
- factorial(3) needs factorial(2), so it pauses.
- factorial(2) needs factorial(1), so it pauses.
- factorial(1) hits the base case and returns 1.
- factorial(2) resumes and returns 2 × 1 = 2.
- factorial(3) resumes and returns 3 × 2 = 6.
- factorial(4) resumes and returns 4 × 6 = 24.
At the deepest point, four frames sit on the stack at once. Nothing is multiplied until the base case returns.
Where recursion goes wrong
- No base case, or a recursive case that never reaches it, means calls pile up until the program runs out of stack space. In Java that is a StackOverflowError.
- Code after the recursive call runs on the way back up, in reverse order. Exam questions that print before and after the call test exactly this.
- Naive recursion can repeat work. fib(n) = fib(n − 1) + fib(n − 2) calls fib(5) 15 times in total, and the count grows exponentially. Storing results you have already computed (memoization) fixes it.
AP Computer Science A asks you to trace recursive methods, so practice writing out the stack by hand. Recursion also powers divide-and-conquer algorithms like the one in merge sort vs bubble sort.
Watching the stack
Ask Isotoon "How does recursion actually work?" and you get a short animated video. A useful one stacks a frame for each call of factorial(4), pauses each one with its own n, then unwinds them one by one as the answers multiply back up. A follow-up such as "Why is naive recursive Fibonacci so slow?" continues it as the next part. The rest of the subject is on computer science.
Questions
- What is a base case in recursion?
- The input small enough to answer directly, without another recursive call. It is what stops the recursion. For factorial, the base case is n less than or equal to 1, which returns 1.
- Is recursion faster than a loop?
- Usually not. Each call adds a stack frame, which costs time and memory. Recursion is chosen because it makes some problems, like tree traversal and merge sort, much simpler to write correctly.
- What causes a stack overflow?
- Too many calls waiting on the stack at once, usually because the base case is missing or never reached. Very deep but correct recursion can also run out of stack space.