DevAcademia lesson/C++ Functions
C++ Recursion
Topic progressTopic 81 of 109 - 74% complete
~9 min lesson27 learning blocks5 code examples1 checks/interactions
Lesson outline
What is Recursion?
Recursion is a programming technique where a function calls itself to solve smaller instances of the same problem.
A recursive function has two essential parts:
- Base case(s): A condition that terminates the recursion
- Recursive case: The function calls itself with modified parameters
Basic Recursion Example
Recursion vs Iteration
| Aspect | Recursion | Iteration |
|---|---|---|
| Code Readability | Often shorter and expressive | More explicit and sometimes longer |
| Memory Usage | Uses call stack: O(depth) frames (risk of overflow) | O(1) stack usage (loop variables only) |
| Performance | Function call overhead; may allocate many frames | Generally faster; no call overhead |
| Use Cases | Tree/graph traversal, divide & conquer | Simple loops, fixed iterations |
Fibonacci Sequence
Common Recursion Patterns
- Divide and Conquer: Split the problem into smaller subproblems (e.g., merge sort)
- Tree Traversal: Process nodes recursively (in-order, pre-order, post-order)
- Backtracking: Explore possible solutions and backtrack (e.g., maze solving, N-Queens)
- Dynamic Programming: Combine recursion with memoization to avoid redundant work
Recursion Pitfalls
- Missing base case leads to infinite recursion
- Deep recursion can cause stack overflow
- Naive solutions may repeat calculations unnecessarily
- Debugging deeply recursive code can be challenging
Tail Recursion Optimization
Tail recursion happens when the recursive call is the final action in the function.
C++ does not guarantee tail-call optimization; some compilers may optimize tail calls under certain build options. Do not rely on it for deep recursion - prefer an iterative version when stack depth matters.
Efficient Alternatives (Memoization/Iteration)
Many recursive problems have efficient non-recursive forms. For Fibonacci, an iterative approach avoids exponential blow-up and uses O(1) extra space.
Was this topic clear?