Recursion solves a problem by calling itself on smaller subproblems. Every recursive function needs a base case and progress toward it—otherwise stack overflow.
Structure
- Base case — return known answer (n=0, empty tree)
- Recursive case — call on smaller input
- Combine results — often return value of subcall
Complexity
Factorial naive recursion depth n → O(n) stack space. Fibonacci naive recursion does overlapping work—O(2ⁿ) time without memoization.
Factorial example
#include
long long fact(int n) {
if (n <= 1) return 1;
return n * fact(n - 1);
}
int main() {
std::cout << "5! = " << fact(5) << "\n";
return 0;
} Important interview questions and answers
- Q: Missing base case?
A: Infinite recursion until stack overflow. - Q: When prefer iteration?
A: Deep recursion or hot paths—loops avoid stack limits; tail recursion may optimize in some compilers.
Self-check
- What two parts must every recursion have?
- What is stack space for factorial(n)?
Tip: Every recursive call needs a base case that stops—say it aloud before coding.
Interview prep
- Base case?
Stops recursion—without it, stack overflow.
- Fibonacci naive?
O(2^n) time without memo—DP fixes overlap.