Beginner LevelData Structures & Algorithms
What is Recursion and how do you identify the Base Case?
ā Interview Prompt: Explain recursion, call stack frames, base case vs recursive case, and demonstrate with Factorial and Fibonacci examples.
Recursion is when a function calls itself with a smaller or simpler sub-problem until it reaches a base case that returns a known value without further recursion.
Key Components:
1
Base Case: The termination condition that stops recursion (e.g.,
n === 0).2
Recursive Case: The function calling itself with a smaller input toward the base case.
3
Call Stack: Each recursive call pushes a frame; too many calls without a base case ā Stack Overflow.
Recursion vs Iteration:
ā¢
Recursion is elegant but uses $O(N)$ call stack space (can cause stack overflow for large $N$).
ā¢
Most recursive solutions can be converted to iterative using an explicit stack.
Code Implementation Example
typescript
// Factorial ā O(N) time, O(N) space (call stack)
function factorial(n: number): number {
if (n <= 1) return 1; // base case
return n * factorial(n - 1); // recursive case
}
// Fibonacci ā naive O(2^N); memoized O(N)
function fib(n: number, memo: Record<number, number> = {}): number {
if (n <= 1) return n;
if (memo[n]) return memo[n];
return (memo[n] = fib(n - 1, memo) + fib(n - 2, memo));
}
console.log(factorial(5)); // 120
console.log(fib(10)); // 55š”Factorial (basic recursion) and memoized Fibonacci.
šÆ Interview Key Takeaway
Always define a clear base case to prevent infinite recursion. Use memoization to eliminate redundant recursive calls from O(2^N) to O(N).
#DSA#Recursion#Base Case#Fibonacci#Beginner
Back to all Data Structures & Algorithms Questionsā