DSA — Techniques

Recursion

A function that calls itself with a smaller input. Every recursive solution needs a base case and a recursive case.

— min read
BaseCase
RecursiveCase
O(n)Call Stack
MemoizeOptimize
✓Trees / DP
// FIBONACCI CALL TREE
Visualize the fibonacci recursive call tree
How It Works
Python Code
Complexity
Quiz
Practice
Interview Qs
01
Base Case
Define when to stop — without this you get infinite recursion.
if n <= 1: return n
02
Recursive Case
Break problem into smaller version of itself.
return fib(n-1) + fib(n-2)
03
Call Stack
Each call is pushed on the stack, popped when it returns.
O(n) stack depth for fib
04
Memoization
Cache results to avoid recomputing — O(2^n) → O(n).
memo = {}
python 
# Naive recursion — O(2^n)
def fib(n):
    if n <= 1: return n
    return fib(n-1) + fib(n-2)

# Memoized recursion — O(n)
def fib_memo(n, memo={}):
    if n <= 1: return n
    if n in memo: return memo[n]
    memo[n] = fib_memo(n-1) + fib_memo(n-2)
    return memo[n]

# General template
def solve(problem):
    if base_case(problem): return base_result
    smaller = reduce(problem)
    return combine(solve(smaller))
O(2^n)
Naive Fib
Each call spawns 2 more — exponential
O(n)
Memoized
Each subproblem computed once
O(n)
Stack Space
n frames on call stack max depth
Backtrack
Technique
Recursion + undo = backtracking
What MUST every recursive function have?
Q1
What is Recursion?
Recursion is when a function calls itself to solve a smaller version of the same problem. Every recursive function needs a base case (stopping condition) and a recursive case (function calls itself).
Q2
Base Case vs Recursive Case
Base Case: The simplest instance that can be solved without recursion (e.g., factorial(0) = 1). Recursive Case: The function calls itself with a smaller input (e.g., factorial(n) = n × factorial(n-1)).
Q3
What is Stack Overflow in Recursion?
Each recursive call adds a frame to the call stack. Without a base case, calls continue infinitely until memory is exhausted — causing a stack overflow error.
Q4
What is Memoization?
Memoization caches results of expensive function calls to avoid recomputation. Reduces Fibonacci from O(2^n) to O(n) time complexity.
Q5
What is Tail Recursion?
Tail recursion occurs when the recursive call is the LAST operation — no computation after it returns. Some languages optimize this, but Python does NOT.
Q6
Recursion vs Iteration
Recursion: Cleaner code for tree/graph problems, but uses O(n) stack space. Iteration: More efficient (O(1) space), but can be less intuitive for divide-and-conquer problems.
Q7
Common Recursion Problems
Fibonacci, Factorial, Climbing Stairs, Tree Traversals (in-order, pre-order, post-order), Merge Sort, Quick Sort, Permutations, Subsets, Combination Sum.
Progress 0 / 4 solved
4 problems · 1 PBC · 3 Startup
#128 Combination Sum Razorpay STARTUP →
#131 Climbing Stairs Swiggy STARTUP →
#076 Serialize and Deserialize Binary Tree Google PBC →
#088 Flatten Binary Tree to Linked List Meesho STARTUP →
← Binary Search