SyntaxShelf

Recursion

2 snippets across 2 stacks - Interview Prep, Python

DSAInterview Prep

O(2^n) - Exponential Time

DSA · Big-O Notation
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.

Frequently asked questions

How does Interview Prep handle recursion?
This task is covered in 2 stacks on this page: Interview Prep, Python. The "O(2^n) - Exponential Time" snippet in Interview Prep uses `Each element doubles the work. Common in recursive solutions without memoization.`.
Which code does the Interview Prep example use?
The "O(2^n) - Exponential Time" snippet uses `Each element doubles the work. Common in recursive solutions without memoization.`, from the Big-O Notation section of the Interview Prep cheat sheet.
Which stacks cover "recursion" on this page?
Interview Prep, Python. Together they hold 2 copy-ready snippets for this task.
Is there anything to watch out for?
Yes. For "O(2^n) - Exponential Time": 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.

Browse all tasks by intent