Recursion Best Practices and Pitfalls
Best practices for using recursion and common pitfalls to avoid.
Recursion Best Practices and Pitfalls
Best Practices
- Always define a base case (prevent infinite recursion).
- Ensure progress toward the base case (each call reduces the problem).
- Use memoization for overlapping subproblems (fibonacci).
- Prefer iteration for simple problems (factorial, countdown).
- Use recursion for trees and divide-and-conquer.
Pitfalls
- No base case: infinite recursion -> stack overflow.
- No progress: base case is never reached (e.g.,
factorial(n)callingfactorial(n)instead offactorial(n-1)). - Stack overflow: deep recursion (10,000+ calls).
- Redundant computation: fibonacci without memoization is O(2^n).
- Mutating shared state: recursive calls may interfere with each other.
The Takeaway
Best practices: always define a base case, ensure progress, use memoization for overlapping subproblems, prefer iteration for simple problems, use recursion for trees. Pitfalls: no base case (stack overflow), no progress, deep recursion, redundant computation, and shared state mutation.
Always define a base case, ensure progress toward the base case, use memoization for overlapping subproblems, prefer iteration for simple problems, and use recursion for trees and divide-and-conquer.
No base case (infinite recursion, stack overflow), no progress toward the base case, stack overflow for deep recursion, redundant computation without memoization, and mutating shared state across recursive calls.
Ensure the base case is reached before the stack limit (usually 10,000-20,000 frames). For deep recursion, use iteration, trampolines, or tail call optimization (not available in most JS engines). Keep recursion shallow.
When subproblems overlap (the same input is computed multiple times). Fibonacci is the classic example: without memoization, O(2^n); with memoization, O(n). Cache results in a Map or object.
Iteration. Factorial is a simple loop. Recursion adds function call overhead and stack growth with no readability benefit. Use recursion for trees and complex structures; iteration for simple mathematical operations.
Ready to master React completely?
Want to upskill yourself, crack your next interview, and get your dream job? Join our comprehensive course to dive deeper with high-quality video tutorials, solve interview questions, and a premium community.
Master React
Want to upskill yourself, crack your next interview, and get your dream job? Join our comprehensive course.