Recursion

O(2^n) — Exponential Time

syntax

Each element doubles the work. Common in recursive solutions without memoization.

example

// JavaScript
function fibNaive(n) {
  if (n <= 1) return n;
  return fibNaive(n - 1) + fibNaive(n - 2);
}
// Each call branches into 2 → O(2^n)

# Python
def fib_naive(n):
    if n <= 1:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)
# Fix with memoization → O(n)

output

Time: O(2^n) without memo | O(n) with memo | Space: O(n)

Note Generating all subsets of a set is O(2^n). This is a red flag in interviews — if your solution is exponential, look for overlapping subproblems (DP) or pruning (backtracking). Always mention that memoization brings it down.

PYPython

Recursion

PY · Functions

syntax

def func(n):
    if base_case: return value
    return func(modified_n)

example

def factorial(n: int) -> int:
    if n <= 1:
        return 1
    return n * factorial(n - 1)

print(factorial(6))

import sys
print(f"Recursion limit: {sys.getrecursionlimit()}")

output

720
Recursion limit: 1000

Note Python's default recursion limit is 1000. Deeply recursive algorithms should be rewritten iteratively or use sys.setrecursionlimit() with caution.

DSAInterview Prep

PYPython