đ Recursion
Solve problems by breaking them into smaller subproblems. Master base cases, recursive calls, and call stack visualization.
Overview
What is Recursion?
Key Recursive Algorithms
Factorial
Compute n! using recursive multiplication: n à (n-1)!
Fibonacci
Classic recursive sequence where each number is sum of two preceding
Tower of Hanoi
Move n disks from source to destination using auxiliary peg
Power Set
Generate all subsets of a set using recursive inclusion/exclusion
Interactive Visualizer
Recursion Tree Visualization
Factorial Recursion Tree
Watch how recursive calls build up the call stack and unwind as base cases are reached.
Deep Dive: Factorial
Time Complexity
Time: O(n)Space Complexity
Space: O(n)Stack Depth
nHow It Works
python
def factorial(n):
if n <= 1:
return 1
return n * factorial(n - 1)Identify Base Case
Determine the simplest input that can be solved without recursion.
Define Recursive Case
Express the problem in terms of smaller instances of itself.
Ensure Progress
Each recursive call must move closer to the base case.
Combine Results
Use returned values from recursive calls to build the final answer.
Real-World Applications
File System Traversal
Recursively navigate directory trees to list, search, or process files
Tree & Graph Algorithms
DFS, tree traversals (preorder, inorder, postorder) are inherently recursive
Parsing Expressions
Recursive descent parsers evaluate mathematical expressions and programming languages
Divide & Conquer
Merge Sort, Quick Sort, Binary Search all use recursion naturally
Backtracking Problems
N-Queens, Sudoku, permutations use recursion to explore solution spaces
Fractal Generation
Mathematical fractals like Mandelbrot set use recursive patterns
Interview Questions
What's the difference between recursion and iteration?
Recursion uses function calls and the call stack; iteration uses loops. Recursion is cleaner for problems with recursive structure (trees, graphs). Iteration is generally more efficient (no function call overhead) and avoids stack overflow.
What is tail recursion? Why is it important?
Tail recursion is when the recursive call is the last operation in the function. Some compilers optimize tail recursion into iteration (TCO - Tail Call Optimization), making it as efficient as a loop. Python doesn't have TCO by default.
How would you convert a recursive function to iterative?
Use an explicit stack (data structure) to simulate the call stack. This is always possible since recursion uses the call stack internally. Example: depth-first tree traversal can be done recursively or iteratively with a stack.
What causes stack overflow in recursion?
Each recursive call adds a frame to the call stack. If the recursion is too deep (thousands of calls), the stack runs out of memory. This happens when: 1) no base case, 2) problem size is too large, 3) base case is never reached.
Knowledge Check
1. What is a base case in recursion?
2. What is the space complexity of a recursive function that calls itself n times?
3. Which data structure is used internally to manage recursive function calls?
4. What happens if a recursive function has no base case?
5. What technique optimizes recursive functions that recompute the same subproblems?
Common Mistakes to Avoid
Missing base case - leads to infinite recursion and stack overflow
Not reducing problem size - each call must move toward the base case
Stack overflow from deep recursion - consider iterative approach for large inputs
Recomputing same subproblems - use memoization for overlapping subproblems (Fibonacci)
Not understanding recursion vs iteration tradeoffs - recursion isn't always better