DataslopeRecursion
Learn recursive thinking, the call stack, classic recursive functions, stack overflow, and recursion trade-offs in C++
Recursion is a technique where a function solves a problem by calling itself on a smaller version of the same problem. It is a natural fit for trees, divide-and-conquer algorithms, backtracking, and definitions that already refer to themselves.
Recursive thinking
Every correct recursive function needs two parts:
| Part | Purpose |
|---|---|
| Base case | Stops on the smallest input |
| Recursive case | Reduces the problem and calls the same function |
This mirrors mathematical induction: prove the smallest case, then show that a correct answer for a smaller input leads to a correct answer for the next input.
Ask two questions
What is the smallest input I can answer immediately? How does every other input move closer to that input?
The call stack
Each call gets its own stack frame containing parameters, local variables, and a return address. Recursive calls add frames until a base case returns.
Factorial
n! means n * (n - 1) * ... * 1, and 0! is 1.
Naive Fibonacci
The Fibonacci sequence is recursive by definition: fib(n) = fib(n - 1) + fib(n - 2). The direct version is short, but exponential because it repeats subproblems.
Repeated calls motivate memoization, a dynamic programming idea we will revisit later.
Recursive array sum
A recursive array function often carries an index that moves toward the end.
Power: naive and fast
Naive recursive power multiplies by a exactly n times, so it is O(n).
Fast exponentiation squares a half-power and reduces the exponent by half, giving O(log n).
Stack overflow and tail recursion
A stack overflow happens when recursive calls create more frames than the stack can hold. Causes include missing base cases, huge inputs, or recursion that shrinks too slowly. Avoid it by verifying the base case, switching to iteration for deep inputs, converting tail recursion to a loop, or increasing stack size only when you control the runtime.
Tail recursion means the recursive call is the final action. Clang may optimize some tail calls, but C++ does not guarantee this optimization.
Recursion vs iteration
Recursion can make tree-shaped logic elegant and close to the math. Iteration usually uses less memory, avoids stack-depth limits, and can be faster. Choose clarity first, then adapt when constraints require it.
Practice: count digits recursively
Implement int countDigits(int n). The input is positive. Do not print inside the function; the driver prints several calls.
Practice: reverse a string recursively
Implement std::string reverseStr(const std::string& s) recursively. The driver prints the reverse of recursion.
Check your understanding
Why is a base case necessary in recursion?
It makes the function run in O(1) time.
It stops recursive calls from continuing forever.
It stores all previous answers automatically.
It lets C++ allocate variables on the heap.
What is the time complexity of naive recursive Fibonacci?
O(n)
O(n log n)
Exponential, often written as O(2^n)
O(log n)
What does recursion use under the hood to remember unfinished calls?
A priority queue
A hash table
The call stack
A sorted vector