DSA Interview Prep · Lesson

Recursion and the Recursion Tree Method

Trace recursive calls into trees, apply the Master Theorem, and derive time complexities for merge sort, factorial, and Fibonacci variants.

Recursion and the Call Stack

When a function calls itself, each call adds a stack frame, piling up until a base case is hit and they unwind. Picturing this is step one in analyzing recursion.

def factorial(n):
    if n == 0:       # base case
        return 1
    return n * factorial(n - 1)  # recursive call

# Call chain: factorial(4)
#   4 * factorial(3)
#     3 * factorial(2)
#       2 * factorial(1)
#         1 * factorial(0) -> 1
# Unwinds: 1, 2, 6, 24
print(factorial(5))  # 120

The Recursion Tree for Fibonacci

A recursion tree expands each call into its sub-calls. Naive Fibonacci splits into two every time, making a tree of about 2^n nodes — that is O(2^n). See the code.

call_count = [0]

def fib_naive(n):
    call_count[0] += 1
    if n <= 1:
        return n
    return fib_naive(n-1) + fib_naive(n-2)

for n in [5, 10, 15, 20]:
    call_count[0] = 0
    result = fib_naive(n)
    print(f'fib({n})={result}, calls={call_count[0]}')
# Calls roughly double each time n increases by 1

All lessons in this course

← Back to DSA Interview Prep