aloalgoRecursion Basics
Recursion is when a function calls itself. It's a powerful technique for solving problems that can be broken down into smaller, similar subproblems.The Two Parts of Recursion
Every recursive function needs:- Base case: When to stop (prevents infinite recursion)
- Recursive case: How to break down the problem
Visualizing the Call Stack
Common Patterns
Linear Recursion
Binary Recursion (Two Branches)
Tree Recursion (Multiple Branches)
Recursion vs Iteration
Tail Recursion
When the recursive call is the last operation, it's called tail recursion. Some languages optimize this, but Python does not.Common Mistakes
When to Use Recursion
- Tree/graph traversal: Naturally recursive structures
- Divide and conquer: Merge sort, quick sort
- Backtracking: Exploring all possibilities
- Dynamic programming: Breaking into subproblems
- Nested structures: Parsing, nested lists
Tips for Recursive Thinking
- Trust the recursion: Assume the recursive call works correctly
- Focus on one level: What does THIS call do?
- Identify the subproblem: What's the smaller version?
- Define base cases first: When is the answer obvious?
Time and Space Complexity
| Pattern | Time | Space (Stack) |
|---|---|---|
| Linear (factorial) | O(n) | O(n) |
| Binary (fibonacci) | O(2ⁿ) | O(n) |
| Tree traversal | O(n) | O(h)* |
| Divide & conquer | O(n log n)** | O(log n) |
**For merge sort; varies by algorithm
Common Interview Tips
- Always state base case first: Write and explain the base case before the recursive case.
- Trace through small examples: Walk through your recursion with n=0, n=1, n=2 to verify correctness.
- Consider stack overflow: For deep recursion (n > 1000), mention potential stack issues and iterative alternatives.
- Know when to iterate: Simple linear problems are often cleaner with loops.
Was this helpful?
Company
Practice
© 2026 aloalgo. All rights reserved.