Recursion in Python – DSA

Introduction
Fundamentals of Recursion
How Recursion Works
Types of Recursion
Common Recursion Patterns
Classic Recursion Problems
Recursion vs Iteration
Optimization Techniques
Advanced Recursion Topics
Best Practices and Tips

1. Introduction

What is Recursion?

Recursion is a programming technique where a function calls itself directly or indirectly to solve a problem by breaking it down into smaller, similar subproblems.

Key Concept

A recursive function solves a problem by:
1. Breaking it into smaller instances of the same problem
2. Solving the smallest instance (base case)
3. Combining solutions to build the final answer

A recursive function solves a problem by:
1. Breaking it into smaller instances of the same problem
2. Solving the smallest instance (base case)
3. Combining solutions to build the final answer

Python

Why Use Recursion?

Advantages:

✅ Elegant and clean code for naturally recursive problems
✅ Simplifies complex problems (trees, graphs, divide-and-conquer)
✅ Reduces code complexity for certain algorithms
✅ Natural fit for mathematical definitions (factorial, Fibonacci)

Disadvantages:

❌ Higher memory overhead (call stack)
❌ Potential stack overflow for deep recursion
❌ Often slower than iterative solutions
❌ Can be harder to debug

When to Use Recursion?

Use recursion when:

Problem can be divided into similar subproblems
Working with tree or graph structures
Implementing backtracking algorithms
Problem has a natural recursive definition
Code clarity is more important than performance

2. Fundamentals of Recursion

The Two Essential Components

1. Base Case (Termination Condition)

def factorial(n):
    # Base case: stops the recursion
    if n == 0 or n == 1:
        return 1
    # Recursive case
    return n * factorial(n - 1)

def factorial(n):
    # Base case: stops the recursion
    if n == 0 or n == 1:
        return 1
    # Recursive case
    return n * factorial(n - 1)

Python

2. Recursive Case (Self-Call)

def countdown(n):
    # Base case
    if n <= 0:
        print("Blast off!")
        return

    # Process current step
    print(n)

    # Recursive case: problem gets smaller
    countdown(n - 1)

countdown(5)
# Output: 5 4 3 2 1 Blast off!

def countdown(n):
    # Base case
    if n <= 0:
        print("Blast off!")
        return

    # Process current step
    print(n)

    # Recursive case: problem gets smaller
    countdown(n - 1)

countdown(5)
# Output: 5 4 3 2 1 Blast off!

Python

Anatomy of a Recursive Function

def recursive_function(parameters):
    # 1. BASE CASE(S) - Must come first!
    if base_condition:
        return base_value

    # 2. RECURSIVE CASE
    # a. Process current step (optional)
    do_something()

    # b. Make problem smaller
    smaller_problem = reduce(parameters)

    # c. Recursive call
    result = recursive_function(smaller_problem)

    # d. Combine results (optional)
    return process(result)

def recursive_function(parameters):
    # 1. BASE CASE(S) - Must come first!
    if base_condition:
        return base_value

    # 2. RECURSIVE CASE
    # a. Process current step (optional)
    do_something()

    # b. Make problem smaller
    smaller_problem = reduce(parameters)

    # c. Recursive call
    result = recursive_function(smaller_problem)

    # d. Combine results (optional)
    return process(result)

Python

Simple Examples

Example 1: Sum of Natural Numbers

def sum_natural(n):
    """Sum of numbers from 1 to n"""
    # Base case
    if n == 1:
        return 1

    # Recursive case: n + sum(1 to n-1)
    return n + sum_natural(n - 1)

print(sum_natural(5))  # Output: 15 (1+2+3+4+5)

def sum_natural(n):
    """Sum of numbers from 1 to n"""
    # Base case
    if n == 1:
        return 1

    # Recursive case: n + sum(1 to n-1)
    return n + sum_natural(n - 1)

print(sum_natural(5))  # Output: 15 (1+2+3+4+5)

Python

Example 2: Power Function

def power(base, exp):
    """Calculate base^exp using recursion"""
    # Base case
    if exp == 0:
        return 1

    # Recursive case
    return base * power(base, exp - 1)

print(power(2, 5))  # Output: 32

def power(base, exp):
    """Calculate base^exp using recursion"""
    # Base case
    if exp == 0:
        return 1

    # Recursive case
    return base * power(base, exp - 1)

print(power(2, 5))  # Output: 32

Python

Example 3: String Reversal

def reverse_string(s):
    """Reverse a string recursively"""
    # Base case
    if len(s) <= 1:
        return s

    # Recursive case: last char + reverse(rest)
    return s[-1] + reverse_string(s[:-1])

print(reverse_string("hello"))  # Output: "olleh"

def reverse_string(s):
    """Reverse a string recursively"""
    # Base case
    if len(s) <= 1:
        return s

    # Recursive case: last char + reverse(rest)
    return s[-1] + reverse_string(s[:-1])

print(reverse_string("hello"))  # Output: "olleh"

Python

3. How Recursion Works

The Call Stack

Understanding the call stack is crucial for mastering recursion.

Visualization: Factorial(4)

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

result = factorial(4)

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

result = factorial(4)

Python

Call Stack Execution:

Call Stack (Growing):
┌─────────────────────────┐
│ factorial(4)            │ ← 4 * factorial(3)
│ factorial(3)            │ ← 3 * factorial(2)
│ factorial(2)            │ ← 2 * factorial(1)
│ factorial(1)            │ ← returns 1
└─────────────────────────┘

Call Stack (Unwinding):
factorial(1) → 1
factorial(2) → 2 * 1 = 2
factorial(3) → 3 * 2 = 6
factorial(4) → 4 * 6 = 24

Call Stack (Growing):
┌─────────────────────────┐
│ factorial(4)            │ ← 4 * factorial(3)
│ factorial(3)            │ ← 3 * factorial(2)
│ factorial(2)            │ ← 2 * factorial(1)
│ factorial(1)            │ ← returns 1
└─────────────────────────┘

Call Stack (Unwinding):
factorial(1) → 1
factorial(2) → 2 * 1 = 2
factorial(3) → 3 * 2 = 6
factorial(4) → 4 * 6 = 24

Python

Detailed Trace

def factorial_trace(n, depth=0):
    """Factorial with execution trace"""
    indent = "  " * depth
    print(f"{indent}→ factorial({n}) called")

    if n <= 1:
        print(f"{indent}← factorial({n}) returns 1")
        return 1

    result = n * factorial_trace(n - 1, depth + 1)
    print(f"{indent}← factorial({n}) returns {result}")
    return result

factorial_trace(4)

def factorial_trace(n, depth=0):
    """Factorial with execution trace"""
    indent = "  " * depth
    print(f"{indent}→ factorial({n}) called")

    if n <= 1:
        print(f"{indent}← factorial({n}) returns 1")
        return 1

    result = n * factorial_trace(n - 1, depth + 1)
    print(f"{indent}← factorial({n}) returns {result}")
    return result

factorial_trace(4)

Python

Output:

→ factorial(4) called
  → factorial(3) called
    → factorial(2) called
      → factorial(1) called
      ← factorial(1) returns 1
    ← factorial(2) returns 2
  ← factorial(3) returns 6
← factorial(4) returns 24

→ factorial(4) called
  → factorial(3) called
    → factorial(2) called
      → factorial(1) called
      ← factorial(1) returns 1
    ← factorial(2) returns 2
  ← factorial(3) returns 6
← factorial(4) returns 24

Python

Memory Management

import sys

# Check recursion limit
print(sys.getrecursionlimit())  # Default: 1000

# Set custom limit (use cautiously!)
sys.setrecursionlimit(2000)

# Deep recursion example
def deep_recursion(n):
    if n == 0:
        return 0
    return 1 + deep_recursion(n - 1)

# This will cause RecursionError if n > recursion limit
try:
    deep_recursion(1500)
except RecursionError as e:
    print(f"Error: {e}")

import sys

# Check recursion limit
print(sys.getrecursionlimit())  # Default: 1000

# Set custom limit (use cautiously!)
sys.setrecursionlimit(2000)

# Deep recursion example
def deep_recursion(n):
    if n == 0:
        return 0
    return 1 + deep_recursion(n - 1)

# This will cause RecursionError if n > recursion limit
try:
    deep_recursion(1500)
except RecursionError as e:
    print(f"Error: {e}")

Python

4. Types of Recursion

1. Direct Recursion

Function calls itself directly.

def direct_recursion(n):
    if n == 0:
        return
    print(n)
    direct_recursion(n - 1)  # Directly calls itself

def direct_recursion(n):
    if n == 0:
        return
    print(n)
    direct_recursion(n - 1)  # Directly calls itself

Python

2. Indirect Recursion

Function calls another function that eventually calls the first function.

def function_a(n):
    if n > 0:
        print(f"A: {n}")
        function_b(n - 1)

def function_b(n):
    if n > 0:
        print(f"B: {n}")
        function_a(n - 1)

function_a(5)

def function_a(n):
    if n > 0:
        print(f"A: {n}")
        function_b(n - 1)

def function_b(n):
    if n > 0:
        print(f"B: {n}")
        function_a(n - 1)

function_a(5)

Python

Output:

A: 5
B: 4
A: 3
B: 2
A: 1

A: 5
B: 4
A: 3
B: 2
A: 1

Python

3. Tail Recursion

Recursive call is the last operation in the function.

def tail_factorial(n, accumulator=1):
    """Tail recursive factorial"""
    # Base case
    if n == 0:
        return accumulator

    # Recursive call is the LAST operation
    return tail_factorial(n - 1, n * accumulator)

print(tail_factorial(5))  # Output: 120

def tail_factorial(n, accumulator=1):
    """Tail recursive factorial"""
    # Base case
    if n == 0:
        return accumulator

    # Recursive call is the LAST operation
    return tail_factorial(n - 1, n * accumulator)

print(tail_factorial(5))  # Output: 120

Python

Note: Python doesn’t optimize tail recursion, but understanding it is valuable.

4. Head Recursion

Operations are performed during the unwinding phase (after recursive call).

def head_recursion(n):
    """Print numbers in reverse order"""
    if n == 0:
        return

    # Recursive call happens FIRST
    head_recursion(n - 1)

    # Operation happens AFTER (during unwinding)
    print(n)

head_recursion(5)  # Output: 1 2 3 4 5

def head_recursion(n):
    """Print numbers in reverse order"""
    if n == 0:
        return

    # Recursive call happens FIRST
    head_recursion(n - 1)

    # Operation happens AFTER (during unwinding)
    print(n)

head_recursion(5)  # Output: 1 2 3 4 5

Python

5. Tree Recursion

Function makes multiple recursive calls.

def fibonacci(n):
    """Tree recursion: makes 2 recursive calls"""
    if n <= 1:
        return n

    # Two recursive calls create a tree of calls
    return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(6))  # Output: 8

def fibonacci(n):
    """Tree recursion: makes 2 recursive calls"""
    if n <= 1:
        return n

    # Two recursive calls create a tree of calls
    return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(6))  # Output: 8

Python

Call Tree for fibonacci(4):

                    fib(4)
                   /      \
              fib(3)      fib(2)
             /     \      /     \
        fib(2)   fib(1) fib(1) fib(0)
        /    \
    fib(1) fib(0)

                    fib(4)
                   /      \
              fib(3)      fib(2)
             /     \      /     \
        fib(2)   fib(1) fib(1) fib(0)
        /    \
    fib(1) fib(0)

Python

6. Nested Recursion

Recursive call uses another recursive call as parameter.

def ackermann(m, n):
    """Famous nested recursion example"""
    if m == 0:
        return n + 1
    elif n == 0:
        return ackermann(m - 1, 1)
    else:
        # Nested: result of one recursion used in another
        return ackermann(m - 1, ackermann(m, n - 1))

print(ackermann(2, 2))  # Output: 7

def ackermann(m, n):
    """Famous nested recursion example"""
    if m == 0:
        return n + 1
    elif n == 0:
        return ackermann(m - 1, 1)
    else:
        # Nested: result of one recursion used in another
        return ackermann(m - 1, ackermann(m, n - 1))

print(ackermann(2, 2))  # Output: 7

Python

5. Common Recursion Patterns

Pattern 1: Linear Recursion (Process and Recur)

def print_array(arr, index=0):
    """Print array elements using recursion"""
    # Base case
    if index >= len(arr):
        return

    # Process current element
    print(arr[index])

    # Recur for next element
    print_array(arr, index + 1)

print_array([1, 2, 3, 4, 5])

def print_array(arr, index=0):
    """Print array elements using recursion"""
    # Base case
    if index >= len(arr):
        return

    # Process current element
    print(arr[index])

    # Recur for next element
    print_array(arr, index + 1)

print_array([1, 2, 3, 4, 5])

Python

Pattern 2: Divide and Conquer

def binary_search(arr, target, left, right):
    """Binary search using divide and conquer"""
    # Base case
    if left > right:
        return -1

    # Divide
    mid = (left + right) // 2

    # Conquer
    if arr[mid] == target:
        return mid
    elif arr[mid] > target:
        return binary_search(arr, target, left, mid - 1)
    else:
        return binary_search(arr, target, mid + 1, right)

arr = [1, 3, 5, 7, 9, 11, 13]
print(binary_search(arr, 7, 0, len(arr) - 1))  # Output: 3

def binary_search(arr, target, left, right):
    """Binary search using divide and conquer"""
    # Base case
    if left > right:
        return -1

    # Divide
    mid = (left + right) // 2

    # Conquer
    if arr[mid] == target:
        return mid
    elif arr[mid] > target:
        return binary_search(arr, target, left, mid - 1)
    else:
        return binary_search(arr, target, mid + 1, right)

arr = [1, 3, 5, 7, 9, 11, 13]
print(binary_search(arr, 7, 0, len(arr) - 1))  # Output: 3

Python

Pattern 3: Backtracking

def generate_permutations(arr, start=0):
    """Generate all permutations using backtracking"""
    # Base case: reached end
    if start == len(arr) - 1:
        print(arr)
        return

    # Try all possibilities
    for i in range(start, len(arr)):
        # Choose
        arr[start], arr[i] = arr[i], arr[start]

        # Explore
        generate_permutations(arr, start + 1)

        # Unchoose (backtrack)
        arr[start], arr[i] = arr[i], arr[start]

generate_permutations([1, 2, 3])

def generate_permutations(arr, start=0):
    """Generate all permutations using backtracking"""
    # Base case: reached end
    if start == len(arr) - 1:
        print(arr)
        return

    # Try all possibilities
    for i in range(start, len(arr)):
        # Choose
        arr[start], arr[i] = arr[i], arr[start]

        # Explore
        generate_permutations(arr, start + 1)

        # Unchoose (backtrack)
        arr[start], arr[i] = arr[i], arr[start]

generate_permutations([1, 2, 3])

Python

Pattern 4: Tree Recursion with Multiple Branches

def count_paths(grid, row, col):
    """Count paths in grid (can only move right or down)"""
    rows, cols = len(grid), len(grid[0])

    # Base case: reached destination
    if row == rows - 1 and col == cols - 1:
        return 1

    # Out of bounds
    if row >= rows or col >= cols:
        return 0

    # Obstacle
    if grid[row][col] == 1:
        return 0

    # Two choices: go right or down
    paths_right = count_paths(grid, row, col + 1)
    paths_down = count_paths(grid, row + 1, col)

    return paths_right + paths_down

grid = [
    [0, 0, 0],
    [0, 1, 0],
    [0, 0, 0]
]
print(count_paths(grid, 0, 0))  # Output: 2

def count_paths(grid, row, col):
    """Count paths in grid (can only move right or down)"""
    rows, cols = len(grid), len(grid[0])

    # Base case: reached destination
    if row == rows - 1 and col == cols - 1:
        return 1

    # Out of bounds
    if row >= rows or col >= cols:
        return 0

    # Obstacle
    if grid[row][col] == 1:
        return 0

    # Two choices: go right or down
    paths_right = count_paths(grid, row, col + 1)
    paths_down = count_paths(grid, row + 1, col)

    return paths_right + paths_down

grid = [
    [0, 0, 0],
    [0, 1, 0],
    [0, 0, 0]
]
print(count_paths(grid, 0, 0))  # Output: 2

Python

Pattern 5: Accumulator Pattern

def sum_list(arr, index=0, accumulator=0):
    """Sum array using accumulator"""
    # Base case
    if index >= len(arr):
        return accumulator

    # Accumulate and recur
    return sum_list(arr, index + 1, accumulator + arr[index])

print(sum_list([1, 2, 3, 4, 5]))  # Output: 15

def sum_list(arr, index=0, accumulator=0):
    """Sum array using accumulator"""
    # Base case
    if index >= len(arr):
        return accumulator

    # Accumulate and recur
    return sum_list(arr, index + 1, accumulator + arr[index])

print(sum_list([1, 2, 3, 4, 5]))  # Output: 15

Python

6. Classic Recursion Problems

Problem 1: Factorial

def factorial(n):
    """
    Calculate n! = n × (n-1) × ... × 1
    Time: O(n), Space: O(n) for call stack
    """
    if n <= 1:
        return 1
    return n * factorial(n - 1)

# Test
print(factorial(5))  # Output: 120
print(factorial(0))  # Output: 1

def factorial(n):
    """
    Calculate n! = n × (n-1) × ... × 1
    Time: O(n), Space: O(n) for call stack
    """
    if n <= 1:
        return 1
    return n * factorial(n - 1)

# Test
print(factorial(5))  # Output: 120
print(factorial(0))  # Output: 1

Python

Problem 2: Fibonacci Sequence

def fibonacci(n):
    """
    Return nth Fibonacci number
    Time: O(2^n), Space: O(n)
    """
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

# Generate first 10 Fibonacci numbers
for i in range(10):
    print(fibonacci(i), end=' ')
# Output: 0 1 1 2 3 5 8 13 21 34

def fibonacci(n):
    """
    Return nth Fibonacci number
    Time: O(2^n), Space: O(n)
    """
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

# Generate first 10 Fibonacci numbers
for i in range(10):
    print(fibonacci(i), end=' ')
# Output: 0 1 1 2 3 5 8 13 21 34

Python

Problem 3: Sum of Digits

def sum_of_digits(n):
    """
    Calculate sum of digits in a number
    Example: 1234 → 1+2+3+4 = 10
    """
    # Base case
    if n == 0:
        return 0

    # Last digit + sum of remaining digits
    return (n % 10) + sum_of_digits(n // 10)

print(sum_of_digits(1234))  # Output: 10
print(sum_of_digits(9876))  # Output: 30

def sum_of_digits(n):
    """
    Calculate sum of digits in a number
    Example: 1234 → 1+2+3+4 = 10
    """
    # Base case
    if n == 0:
        return 0

    # Last digit + sum of remaining digits
    return (n % 10) + sum_of_digits(n // 10)

print(sum_of_digits(1234))  # Output: 10
print(sum_of_digits(9876))  # Output: 30

Python

Problem 4: Greatest Common Divisor (GCD)

def gcd(a, b):
    """
    Euclidean algorithm for GCD
    Time: O(log min(a,b)), Space: O(log min(a,b))
    """
    # Base case
    if b == 0:
        return a

    # Recursive case: gcd(b, a mod b)
    return gcd(b, a % b)

print(gcd(48, 18))   # Output: 6
print(gcd(100, 35))  # Output: 5

def gcd(a, b):
    """
    Euclidean algorithm for GCD
    Time: O(log min(a,b)), Space: O(log min(a,b))
    """
    # Base case
    if b == 0:
        return a

    # Recursive case: gcd(b, a mod b)
    return gcd(b, a % b)

print(gcd(48, 18))   # Output: 6
print(gcd(100, 35))  # Output: 5

Python

Problem 5: Tower of Hanoi

def tower_of_hanoi(n, source, destination, auxiliary):
    """
    Solve Tower of Hanoi puzzle
    Move n disks from source to destination using auxiliary
    Time: O(2^n), Space: O(n)
    """
    if n == 1:
        print(f"Move disk 1 from {source} to {destination}")
        return

    # Move n-1 disks from source to auxiliary
    tower_of_hanoi(n - 1, source, auxiliary, destination)

    # Move largest disk from source to destination
    print(f"Move disk {n} from {source} to {destination}")

    # Move n-1 disks from auxiliary to destination
    tower_of_hanoi(n - 1, auxiliary, destination, source)

tower_of_hanoi(3, 'A', 'C', 'B')

def tower_of_hanoi(n, source, destination, auxiliary):
    """
    Solve Tower of Hanoi puzzle
    Move n disks from source to destination using auxiliary
    Time: O(2^n), Space: O(n)
    """
    if n == 1:
        print(f"Move disk 1 from {source} to {destination}")
        return

    # Move n-1 disks from source to auxiliary
    tower_of_hanoi(n - 1, source, auxiliary, destination)

    # Move largest disk from source to destination
    print(f"Move disk {n} from {source} to {destination}")

    # Move n-1 disks from auxiliary to destination
    tower_of_hanoi(n - 1, auxiliary, destination, source)

tower_of_hanoi(3, 'A', 'C', 'B')

Python

Output:

Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

Python

Problem 6: Palindrome Check

def is_palindrome(s, left=0, right=None):
    """
    Check if string is palindrome
    Time: O(n), Space: O(n)
    """
    # Initialize right pointer on first call
    if right is None:
        right = len(s) - 1

    # Base case: pointers crossed
    if left >= right:
        return True

    # Characters don't match
    if s[left] != s[right]:
        return False

    # Check remaining substring
    return is_palindrome(s, left + 1, right - 1)

print(is_palindrome("racecar"))  # Output: True
print(is_palindrome("hello"))    # Output: False

def is_palindrome(s, left=0, right=None):
    """
    Check if string is palindrome
    Time: O(n), Space: O(n)
    """
    # Initialize right pointer on first call
    if right is None:
        right = len(s) - 1

    # Base case: pointers crossed
    if left >= right:
        return True

    # Characters don't match
    if s[left] != s[right]:
        return False

    # Check remaining substring
    return is_palindrome(s, left + 1, right - 1)

print(is_palindrome("racecar"))  # Output: True
print(is_palindrome("hello"))    # Output: False

Python

Problem 7: Array Sum

def array_sum(arr, n=None):
    """
    Sum all elements in array
    Time: O(n), Space: O(n)
    """
    # Initialize n on first call
    if n is None:
        n = len(arr)

    # Base case
    if n == 0:
        return 0

    # Last element + sum of rest
    return arr[n - 1] + array_sum(arr, n - 1)

print(array_sum([1, 2, 3, 4, 5]))  # Output: 15

def array_sum(arr, n=None):
    """
    Sum all elements in array
    Time: O(n), Space: O(n)
    """
    # Initialize n on first call
    if n is None:
        n = len(arr)

    # Base case
    if n == 0:
        return 0

    # Last element + sum of rest
    return arr[n - 1] + array_sum(arr, n - 1)

print(array_sum([1, 2, 3, 4, 5]))  # Output: 15

Python

Problem 8: Power Function (Optimized)

def power_optimized(base, exp):
    """
    Calculate base^exp using binary exponentiation
    Time: O(log n), Space: O(log n)
    """
    # Base cases
    if exp == 0:
        return 1
    if exp == 1:
        return base

    # If exponent is even: base^n = (base^(n/2))^2
    if exp % 2 == 0:
        half = power_optimized(base, exp // 2)
        return half * half

    # If exponent is odd: base^n = base × base^(n-1)
    return base * power_optimized(base, exp - 1)

print(power_optimized(2, 10))   # Output: 1024
print(power_optimized(3, 5))    # Output: 243

def power_optimized(base, exp):
    """
    Calculate base^exp using binary exponentiation
    Time: O(log n), Space: O(log n)
    """
    # Base cases
    if exp == 0:
        return 1
    if exp == 1:
        return base

    # If exponent is even: base^n = (base^(n/2))^2
    if exp % 2 == 0:
        half = power_optimized(base, exp // 2)
        return half * half

    # If exponent is odd: base^n = base × base^(n-1)
    return base * power_optimized(base, exp - 1)

print(power_optimized(2, 10))   # Output: 1024
print(power_optimized(3, 5))    # Output: 243

Python

Problem 9: Binary Search

def binary_search_recursive(arr, target, left=0, right=None):
    """
    Binary search using recursion
    Time: O(log n), Space: O(log n)
    """
    if right is None:
        right = len(arr) - 1

    # Base case: element not found
    if left > right:
        return -1

    mid = (left + right) // 2

    # Found the element
    if arr[mid] == target:
        return mid

    # Search left half
    if arr[mid] > target:
        return binary_search_recursive(arr, target, left, mid - 1)

    # Search right half
    return binary_search_recursive(arr, target, mid + 1, right)

arr = [1, 3, 5, 7, 9, 11, 13, 15]
print(binary_search_recursive(arr, 7))   # Output: 3
print(binary_search_recursive(arr, 10))  # Output: -1

def binary_search_recursive(arr, target, left=0, right=None):
    """
    Binary search using recursion
    Time: O(log n), Space: O(log n)
    """
    if right is None:
        right = len(arr) - 1

    # Base case: element not found
    if left > right:
        return -1

    mid = (left + right) // 2

    # Found the element
    if arr[mid] == target:
        return mid

    # Search left half
    if arr[mid] > target:
        return binary_search_recursive(arr, target, left, mid - 1)

    # Search right half
    return binary_search_recursive(arr, target, mid + 1, right)

arr = [1, 3, 5, 7, 9, 11, 13, 15]
print(binary_search_recursive(arr, 7))   # Output: 3
print(binary_search_recursive(arr, 10))  # Output: -1

Python

Problem 10: Subset Generation

def generate_subsets(arr, index=0, current=[]):
    """
    Generate all subsets of array
    Time: O(2^n), Space: O(n)
    """
    # Base case: processed all elements
    if index == len(arr):
        print(current)
        return

    # Choice 1: Don't include current element
    generate_subsets(arr, index + 1, current)

    # Choice 2: Include current element
    generate_subsets(arr, index + 1, current + [arr[index]])

generate_subsets([1, 2, 3])

def generate_subsets(arr, index=0, current=[]):
    """
    Generate all subsets of array
    Time: O(2^n), Space: O(n)
    """
    # Base case: processed all elements
    if index == len(arr):
        print(current)
        return

    # Choice 1: Don't include current element
    generate_subsets(arr, index + 1, current)

    # Choice 2: Include current element
    generate_subsets(arr, index + 1, current + [arr[index]])

generate_subsets([1, 2, 3])

Python

Output:

[]
[3]
[2]
[2, 3]
[1]
[1, 3]
[1, 2]
[1, 2, 3]

[]
[3]
[2]
[2, 3]
[1]
[1, 3]
[1, 2]
[1, 2, 3]

Python

Problem 11: N-Queens Problem

def solve_n_queens(n):
    """
    Solve N-Queens problem using backtracking
    Place n queens on n×n board so no two queens attack each other
    """
    def is_safe(board, row, col):
        # Check column
        for i in range(row):
            if board[i] == col:
                return False

        # Check diagonal (top-left to bottom-right)
        for i in range(row):
            if abs(board[i] - col) == abs(i - row):
                return False

        return True

    def solve(board, row):
        if row == n:
            solutions.append(board[:])
            return

        for col in range(n):
            if is_safe(board, row, col):
                board[row] = col
                solve(board, row + 1)
                board[row] = -1  # Backtrack

    solutions = []
    solve([-1] * n, 0)
    return solutions

def print_board(board):
    n = len(board)
    for row in range(n):
        line = ""
        for col in range(n):
            if board[row] == col:
                line += "Q "
            else:
                line += ". "
        print(line)
    print()

# Solve 4-Queens
solutions = solve_n_queens(4)
print(f"Found {len(solutions)} solutions")
for solution in solutions[:2]:  # Print first 2 solutions
    print_board(solution)

def solve_n_queens(n):
    """
    Solve N-Queens problem using backtracking
    Place n queens on n×n board so no two queens attack each other
    """
    def is_safe(board, row, col):
        # Check column
        for i in range(row):
            if board[i] == col:
                return False

        # Check diagonal (top-left to bottom-right)
        for i in range(row):
            if abs(board[i] - col) == abs(i - row):
                return False

        return True

    def solve(board, row):
        if row == n:
            solutions.append(board[:])
            return

        for col in range(n):
            if is_safe(board, row, col):
                board[row] = col
                solve(board, row + 1)
                board[row] = -1  # Backtrack

    solutions = []
    solve([-1] * n, 0)
    return solutions

def print_board(board):
    n = len(board)
    for row in range(n):
        line = ""
        for col in range(n):
            if board[row] == col:
                line += "Q "
            else:
                line += ". "
        print(line)
    print()

# Solve 4-Queens
solutions = solve_n_queens(4)
print(f"Found {len(solutions)} solutions")
for solution in solutions[:2]:  # Print first 2 solutions
    print_board(solution)

Python

Problem 12: Merge Sort

def merge_sort(arr):
    """
    Sort array using merge sort
    Time: O(n log n), Space: O(n)
    """
    # Base case: array of length 0 or 1
    if len(arr) <= 1:
        return arr

    # Divide
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    # Conquer (merge)
    return merge(left, right)

def merge(left, right):
    """Merge two sorted arrays"""
    result = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result.extend(left[i:])
    result.extend(right[j:])
    return result

arr = [38, 27, 43, 3, 9, 82, 10]
print(merge_sort(arr))  # Output: [3, 9, 10, 27, 38, 43, 82]

def merge_sort(arr):
    """
    Sort array using merge sort
    Time: O(n log n), Space: O(n)
    """
    # Base case: array of length 0 or 1
    if len(arr) <= 1:
        return arr

    # Divide
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    # Conquer (merge)
    return merge(left, right)

def merge(left, right):
    """Merge two sorted arrays"""
    result = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result.extend(left[i:])
    result.extend(right[j:])
    return result

arr = [38, 27, 43, 3, 9, 82, 10]
print(merge_sort(arr))  # Output: [3, 9, 10, 27, 38, 43, 82]

Python

Problem 13: Quick Sort

def quick_sort(arr, low=0, high=None):
    """
    Sort array using quick sort
    Time: O(n log n) average, O(n²) worst
    Space: O(log n)
    """
    if high is None:
        high = len(arr) - 1

    if low < high:
        # Partition and get pivot index
        pi = partition(arr, low, high)

        # Recursively sort elements before and after partition
        quick_sort(arr, low, pi - 1)
        quick_sort(arr, pi + 1, high)

    return arr

def partition(arr, low, high):
    """Partition array around pivot"""
    pivot = arr[high]
    i = low - 1

    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]

    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

arr = [10, 7, 8, 9, 1, 5]
print(quick_sort(arr))  # Output: [1, 5, 7, 8, 9, 10]

def quick_sort(arr, low=0, high=None):
    """
    Sort array using quick sort
    Time: O(n log n) average, O(n²) worst
    Space: O(log n)
    """
    if high is None:
        high = len(arr) - 1

    if low < high:
        # Partition and get pivot index
        pi = partition(arr, low, high)

        # Recursively sort elements before and after partition
        quick_sort(arr, low, pi - 1)
        quick_sort(arr, pi + 1, high)

    return arr

def partition(arr, low, high):
    """Partition array around pivot"""
    pivot = arr[high]
    i = low - 1

    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]

    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

arr = [10, 7, 8, 9, 1, 5]
print(quick_sort(arr))  # Output: [1, 5, 7, 8, 9, 10]

Python

7. Recursion vs Iteration

Comparison Table

Aspect	Recursion	Iteration
Definition	Function calls itself	Uses loops (for, while)
Termination	Base case	Loop condition
Memory	Uses call stack (higher overhead)	Uses loop variables (lower overhead)
Speed	Generally slower	Generally faster
Code Size	Often shorter, cleaner	Can be longer
Readability	More intuitive for some problems	More straightforward for others
Stack Overflow	Risk with deep recursion	No risk
Use Cases	Trees, graphs, divide-and-conquer	Simple iterations, performance-critical

Same Problem Both Ways

Example 1: Factorial

# Recursive
def factorial_recursive(n):
    if n <= 1:
        return 1
    return n * factorial_recursive(n - 1)

# Iterative
def factorial_iterative(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

# Both produce same result
print(factorial_recursive(5))  # 120
print(factorial_iterative(5))  # 120

# Recursive
def factorial_recursive(n):
    if n <= 1:
        return 1
    return n * factorial_recursive(n - 1)

# Iterative
def factorial_iterative(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

# Both produce same result
print(factorial_recursive(5))  # 120
print(factorial_iterative(5))  # 120

Python

Example 2: Fibonacci

# Recursive (inefficient)
def fib_recursive(n):
    if n <= 1:
        return n
    return fib_recursive(n - 1) + fib_recursive(n - 2)

# Iterative (efficient)
def fib_iterative(n):
    if n <= 1:
        return n

    prev, curr = 0, 1
    for _ in range(2, n + 1):
        prev, curr = curr, prev + curr
    return curr

# Iterative is much faster for large n
import time

n = 35
start = time.time()
result1 = fib_recursive(n)
time1 = time.time() - start

start = time.time()
result2 = fib_iterative(n)
time2 = time.time() - start

print(f"Recursive: {result1} in {time1:.4f}s")
print(f"Iterative: {result2} in {time2:.6f}s")

# Recursive (inefficient)
def fib_recursive(n):
    if n <= 1:
        return n
    return fib_recursive(n - 1) + fib_recursive(n - 2)

# Iterative (efficient)
def fib_iterative(n):
    if n <= 1:
        return n

    prev, curr = 0, 1
    for _ in range(2, n + 1):
        prev, curr = curr, prev + curr
    return curr

# Iterative is much faster for large n
import time

n = 35
start = time.time()
result1 = fib_recursive(n)
time1 = time.time() - start

start = time.time()
result2 = fib_iterative(n)
time2 = time.time() - start

print(f"Recursive: {result1} in {time1:.4f}s")
print(f"Iterative: {result2} in {time2:.6f}s")

Python

Example 3: Array Sum

# Recursive
def sum_recursive(arr, n=None):
    if n is None:
        n = len(arr)
    if n == 0:
        return 0
    return arr[n - 1] + sum_recursive(arr, n - 1)

# Iterative
def sum_iterative(arr):
    total = 0
    for num in arr:
        total += num
    return total

arr = list(range(1000))
print(sum_recursive(arr))  # 499500
print(sum_iterative(arr))  # 499500

# Recursive
def sum_recursive(arr, n=None):
    if n is None:
        n = len(arr)
    if n == 0:
        return 0
    return arr[n - 1] + sum_recursive(arr, n - 1)

# Iterative
def sum_iterative(arr):
    total = 0
    for num in arr:
        total += num
    return total

arr = list(range(1000))
print(sum_recursive(arr))  # 499500
print(sum_iterative(arr))  # 499500

Python

When to Choose Which?

Choose Recursion:

Tree/graph traversal
Divide and conquer algorithms
Backtracking problems
Problems with natural recursive definition
Code clarity is priority

Choose Iteration:

Simple loops and iterations
Performance is critical
Deep recursion likely (avoid stack overflow)
Memory is constrained
Tail recursion (Python doesn’t optimize it)

Converting Recursion to Iteration

Many recursive solutions can be converted to iterative using a stack:

# Recursive tree traversal
def inorder_recursive(root):
    if root:
        inorder_recursive(root.left)
        print(root.val, end=' ')
        inorder_recursive(root.right)

# Iterative tree traversal using stack
def inorder_iterative(root):
    stack = []
    current = root

    while stack or current:
        # Go to leftmost node
        while current:
            stack.append(current)
            current = current.left

        # Process node
        current = stack.pop()
        print(current.val, end=' ')

        # Visit right subtree
        current = current.right

# Recursive tree traversal
def inorder_recursive(root):
    if root:
        inorder_recursive(root.left)
        print(root.val, end=' ')
        inorder_recursive(root.right)

# Iterative tree traversal using stack
def inorder_iterative(root):
    stack = []
    current = root

    while stack or current:
        # Go to leftmost node
        while current:
            stack.append(current)
            current = current.left

        # Process node
        current = stack.pop()
        print(current.val, end=' ')

        # Visit right subtree
        current = current.right

Python

8. Optimization Techniques

1. Memoization (Top-Down Dynamic Programming)

Cache results of expensive recursive calls.

Fibonacci with Memoization

def fibonacci_memo(n, memo={}):
    """
    Fibonacci with memoization
    Time: O(n), Space: O(n)
    """
    # Check cache
    if n in memo:
        return memo[n]

    # Base case
    if n <= 1:
        return n

    # Calculate and cache
    memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
    return memo[n]

# Much faster than naive recursion
print(fibonacci_memo(100))  # Instant!

def fibonacci_memo(n, memo={}):
    """
    Fibonacci with memoization
    Time: O(n), Space: O(n)
    """
    # Check cache
    if n in memo:
        return memo[n]

    # Base case
    if n <= 1:
        return n

    # Calculate and cache
    memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
    return memo[n]

# Much faster than naive recursion
print(fibonacci_memo(100))  # Instant!

Python

Using Python’s LRU Cache

from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci_cached(n):
    """Fibonacci with automatic caching"""
    if n <= 1:
        return n
    return fibonacci_cached(n - 1) + fibonacci_cached(n - 2)

print(fibonacci_cached(100))
print(fibonacci_cached.cache_info())  # See cache statistics

from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci_cached(n):
    """Fibonacci with automatic caching"""
    if n <= 1:
        return n
    return fibonacci_cached(n - 1) + fibonacci_cached(n - 2)

print(fibonacci_cached(100))
print(fibonacci_cached.cache_info())  # See cache statistics

Python

Memoization Pattern

def memoize(func):
    """Generic memoization decorator"""
    cache = {}

    def wrapper(*args):
        if args not in cache:
            cache[args] = func(*args)
        return cache[args]

    return wrapper

@memoize
def expensive_recursion(n):
    if n <= 1:
        return n
    return expensive_recursion(n - 1) + expensive_recursion(n - 2)

print(expensive_recursion(50))

def memoize(func):
    """Generic memoization decorator"""
    cache = {}

    def wrapper(*args):
        if args not in cache:
            cache[args] = func(*args)
        return cache[args]

    return wrapper

@memoize
def expensive_recursion(n):
    if n <= 1:
        return n
    return expensive_recursion(n - 1) + expensive_recursion(n - 2)

print(expensive_recursion(50))

Python

2. Tail Call Optimization (Manual)

Python doesn’t optimize tail recursion, but you can convert to iteration:

# Tail recursive (not optimized in Python)
def factorial_tail(n, accumulator=1):
    if n == 0:
        return accumulator
    return factorial_tail(n - 1, n * accumulator)

# Convert to iteration
def factorial_iterative_from_tail(n):
    accumulator = 1
    while n > 0:
        accumulator *= n
        n -= 1
    return accumulator

# Tail recursive (not optimized in Python)
def factorial_tail(n, accumulator=1):
    if n == 0:
        return accumulator
    return factorial_tail(n - 1, n * accumulator)

# Convert to iteration
def factorial_iterative_from_tail(n):
    accumulator = 1
    while n > 0:
        accumulator *= n
        n -= 1
    return accumulator

Python

3. Using Generators for Large Results

def fibonacci_generator():
    """Generate Fibonacci sequence infinitely"""
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a + b

# Use first 10 Fibonacci numbers
fib_gen = fibonacci_generator()
for _ in range(10):
    print(next(fib_gen), end=' ')
# Output: 0 1 1 2 3 5 8 13 21 34

def fibonacci_generator():
    """Generate Fibonacci sequence infinitely"""
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a + b

# Use first 10 Fibonacci numbers
fib_gen = fibonacci_generator()
for _ in range(10):
    print(next(fib_gen), end=' ')
# Output: 0 1 1 2 3 5 8 13 21 34

Python

4. Reducing Redundant Calculations

Grid Paths with Memoization

def count_paths_memo(grid, row=0, col=0, memo=None):
    """
    Count paths with memoization
    Time: O(m × n), Space: O(m × n)
    """
    if memo is None:
        memo = {}

    # Check cache
    if (row, col) in memo:
        return memo[(row, col)]

    rows, cols = len(grid), len(grid[0])

    # Base case
    if row == rows - 1 and col == cols - 1:
        return 1

    # Out of bounds or obstacle
    if row >= rows or col >= cols or grid[row][col] == 1:
        return 0

    # Calculate and cache
    paths = count_paths_memo(grid, row, col + 1, memo) + \
            count_paths_memo(grid, row + 1, col, memo)

    memo[(row, col)] = paths
    return paths

grid = [
    [0, 0, 0, 0],
    [0, 1, 0, 0],
    [0, 0, 1, 0],
    [0, 0, 0, 0]
]
print(count_paths_memo(grid))

def count_paths_memo(grid, row=0, col=0, memo=None):
    """
    Count paths with memoization
    Time: O(m × n), Space: O(m × n)
    """
    if memo is None:
        memo = {}

    # Check cache
    if (row, col) in memo:
        return memo[(row, col)]

    rows, cols = len(grid), len(grid[0])

    # Base case
    if row == rows - 1 and col == cols - 1:
        return 1

    # Out of bounds or obstacle
    if row >= rows or col >= cols or grid[row][col] == 1:
        return 0

    # Calculate and cache
    paths = count_paths_memo(grid, row, col + 1, memo) + \
            count_paths_memo(grid, row + 1, col, memo)

    memo[(row, col)] = paths
    return paths

grid = [
    [0, 0, 0, 0],
    [0, 1, 0, 0],
    [0, 0, 1, 0],
    [0, 0, 0, 0]
]
print(count_paths_memo(grid))

Python

5. Bottom-Up Approach (Dynamic Programming)

Convert recursive solution to iterative DP:

def fibonacci_dp(n):
    """
    Bottom-up Fibonacci
    Time: O(n), Space: O(n)
    """
    if n <= 1:
        return n

    dp = [0] * (n + 1)
    dp[1] = 1

    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]

    return dp[n]

print(fibonacci_dp(50))

def fibonacci_dp(n):
    """
    Bottom-up Fibonacci
    Time: O(n), Space: O(n)
    """
    if n <= 1:
        return n

    dp = [0] * (n + 1)
    dp[1] = 1

    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]

    return dp[n]

print(fibonacci_dp(50))

Python

Space-Optimized DP

def fibonacci_optimized(n):
    """
    Space-optimized Fibonacci
    Time: O(n), Space: O(1)
    """
    if n <= 1:
        return n

    prev, curr = 0, 1
    for _ in range(2, n + 1):
        prev, curr = curr, prev + curr

    return curr

print(fibonacci_optimized(50))

def fibonacci_optimized(n):
    """
    Space-optimized Fibonacci
    Time: O(n), Space: O(1)
    """
    if n <= 1:
        return n

    prev, curr = 0, 1
    for _ in range(2, n + 1):
        prev, curr = curr, prev + curr

    return curr

print(fibonacci_optimized(50))

Python

9. Advanced Recursion Topics

1. Recursive Data Structures

Linked List Operations

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

# Recursive traversal
def print_list_recursive(node):
    if node is None:
        return
    print(node.data, end=' ')
    print_list_recursive(node.next)

# Recursive search
def search_recursive(node, target):
    if node is None:
        return False
    if node.data == target:
        return True
    return search_recursive(node.next, target)

# Recursive reversal
def reverse_list_recursive(head):
    # Base case: empty or single node
    if head is None or head.next is None:
        return head

    # Reverse rest of list
    new_head = reverse_list_recursive(head.next)

    # Fix pointers
    head.next.next = head
    head.next = None

    return new_head

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

# Recursive traversal
def print_list_recursive(node):
    if node is None:
        return
    print(node.data, end=' ')
    print_list_recursive(node.next)

# Recursive search
def search_recursive(node, target):
    if node is None:
        return False
    if node.data == target:
        return True
    return search_recursive(node.next, target)

# Recursive reversal
def reverse_list_recursive(head):
    # Base case: empty or single node
    if head is None or head.next is None:
        return head

    # Reverse rest of list
    new_head = reverse_list_recursive(head.next)

    # Fix pointers
    head.next.next = head
    head.next = None

    return new_head

Python

Binary Tree Operations

class TreeNode:
    def __init__(self, val=0):
        self.val = val
        self.left = None
        self.right = None

# Tree height
def tree_height(root):
    if root is None:
        return 0
    return 1 + max(tree_height(root.left), tree_height(root.right))

# Count nodes
def count_nodes(root):
    if root is None:
        return 0
    return 1 + count_nodes(root.left) + count_nodes(root.right)

# Sum of all values
def tree_sum(root):
    if root is None:
        return 0
    return root.val + tree_sum(root.left) + tree_sum(root.right)

# Check if tree is balanced
def is_balanced(root):
    def check_height(node):
        if node is None:
            return 0

        left_height = check_height(node.left)
        if left_height == -1:
            return -1

        right_height = check_height(node.right)
        if right_height == -1:
            return -1

        if abs(left_height - right_height) > 1:
            return -1

        return 1 + max(left_height, right_height)

    return check_height(root) != -1

# Path sum
def has_path_sum(root, target_sum):
    if root is None:
        return False

    # Leaf node
    if root.left is None and root.right is None:
        return root.val == target_sum

    remaining = target_sum - root.val
    return has_path_sum(root.left, remaining) or \
           has_path_sum(root.right, remaining)

class TreeNode:
    def __init__(self, val=0):
        self.val = val
        self.left = None
        self.right = None

# Tree height
def tree_height(root):
    if root is None:
        return 0
    return 1 + max(tree_height(root.left), tree_height(root.right))

# Count nodes
def count_nodes(root):
    if root is None:
        return 0
    return 1 + count_nodes(root.left) + count_nodes(root.right)

# Sum of all values
def tree_sum(root):
    if root is None:
        return 0
    return root.val + tree_sum(root.left) + tree_sum(root.right)

# Check if tree is balanced
def is_balanced(root):
    def check_height(node):
        if node is None:
            return 0

        left_height = check_height(node.left)
        if left_height == -1:
            return -1

        right_height = check_height(node.right)
        if right_height == -1:
            return -1

        if abs(left_height - right_height) > 1:
            return -1

        return 1 + max(left_height, right_height)

    return check_height(root) != -1

# Path sum
def has_path_sum(root, target_sum):
    if root is None:
        return False

    # Leaf node
    if root.left is None and root.right is None:
        return root.val == target_sum

    remaining = target_sum - root.val
    return has_path_sum(root.left, remaining) or \
           has_path_sum(root.right, remaining)

Python

2. Mutual Recursion

Functions that call each other.

def is_even(n):
    """Check if number is even using mutual recursion"""
    if n == 0:
        return True
    return is_odd(n - 1)

def is_odd(n):
    """Check if number is odd using mutual recursion"""
    if n == 0:
        return False
    return is_even(n - 1)

print(is_even(10))  # True
print(is_odd(7))    # True

def is_even(n):
    """Check if number is even using mutual recursion"""
    if n == 0:
        return True
    return is_odd(n - 1)

def is_odd(n):
    """Check if number is odd using mutual recursion"""
    if n == 0:
        return False
    return is_even(n - 1)

print(is_even(10))  # True
print(is_odd(7))    # True

Python

Expression Evaluation

def evaluate_expr(expr, pos=0):
    """Evaluate arithmetic expression recursively"""
    return parse_term(expr, pos)

def parse_term(expr, pos):
    """Parse term (handles +, -)"""
    result, pos = parse_factor(expr, pos)

    while pos < len(expr) and expr[pos] in '+-':
        op = expr[pos]
        pos += 1
        operand, pos = parse_factor(expr, pos)
        if op == '+':
            result += operand
        else:
            result -= operand

    return result, pos

def parse_factor(expr, pos):
    """Parse factor (handles *, /)"""
    result, pos = parse_number(expr, pos)

    while pos < len(expr) and expr[pos] in '*/':
        op = expr[pos]
        pos += 1
        operand, pos = parse_number(expr, pos)
        if op == '*':
            result *= operand
        else:
            result /= operand

    return result, pos

def parse_number(expr, pos):
    """Parse number"""
    num_str = ''
    while pos < len(expr) and expr[pos].isdigit():
        num_str += expr[pos]
        pos += 1
    return int(num_str), pos

# Test
result, _ = evaluate_expr("5+3*2-4")
print(result)  # Output: 7

def evaluate_expr(expr, pos=0):
    """Evaluate arithmetic expression recursively"""
    return parse_term(expr, pos)

def parse_term(expr, pos):
    """Parse term (handles +, -)"""
    result, pos = parse_factor(expr, pos)

    while pos < len(expr) and expr[pos] in '+-':
        op = expr[pos]
        pos += 1
        operand, pos = parse_factor(expr, pos)
        if op == '+':
            result += operand
        else:
            result -= operand

    return result, pos

def parse_factor(expr, pos):
    """Parse factor (handles *, /)"""
    result, pos = parse_number(expr, pos)

    while pos < len(expr) and expr[pos] in '*/':
        op = expr[pos]
        pos += 1
        operand, pos = parse_number(expr, pos)
        if op == '*':
            result *= operand
        else:
            result /= operand

    return result, pos

def parse_number(expr, pos):
    """Parse number"""
    num_str = ''
    while pos < len(expr) and expr[pos].isdigit():
        num_str += expr[pos]
        pos += 1
    return int(num_str), pos

# Test
result, _ = evaluate_expr("5+3*2-4")
print(result)  # Output: 7

Python

3. Recursion with Multiple Parameters

Edit Distance (Levenshtein Distance)

def edit_distance(s1, s2, i=None, j=None, memo=None):
    """
    Calculate minimum edit distance between two strings
    Operations: insert, delete, replace
    """
    if i is None:
        i = len(s1)
    if j is None:
        j = len(s2)
    if memo is None:
        memo = {}

    # Check cache
    if (i, j) in memo:
        return memo[(i, j)]

    # Base cases
    if i == 0:
        return j
    if j == 0:
        return i

    # Characters match
    if s1[i - 1] == s2[j - 1]:
        result = edit_distance(s1, s2, i - 1, j - 1, memo)
    else:
        # Try all three operations
        insert = edit_distance(s1, s2, i, j - 1, memo)
        delete = edit_distance(s1, s2, i - 1, j, memo)
        replace = edit_distance(s1, s2, i - 1, j - 1, memo)
        result = 1 + min(insert, delete, replace)

    memo[(i, j)] = result
    return result

print(edit_distance("kitten", "sitting"))  # Output: 3

def edit_distance(s1, s2, i=None, j=None, memo=None):
    """
    Calculate minimum edit distance between two strings
    Operations: insert, delete, replace
    """
    if i is None:
        i = len(s1)
    if j is None:
        j = len(s2)
    if memo is None:
        memo = {}

    # Check cache
    if (i, j) in memo:
        return memo[(i, j)]

    # Base cases
    if i == 0:
        return j
    if j == 0:
        return i

    # Characters match
    if s1[i - 1] == s2[j - 1]:
        result = edit_distance(s1, s2, i - 1, j - 1, memo)
    else:
        # Try all three operations
        insert = edit_distance(s1, s2, i, j - 1, memo)
        delete = edit_distance(s1, s2, i - 1, j, memo)
        replace = edit_distance(s1, s2, i - 1, j - 1, memo)
        result = 1 + min(insert, delete, replace)

    memo[(i, j)] = result
    return result

print(edit_distance("kitten", "sitting"))  # Output: 3

Python

4. Recursion with State

Generate Valid Parentheses

def generate_parentheses(n):
    """
    Generate all combinations of n pairs of valid parentheses
    """
    def backtrack(current, open_count, close_count):
        # Base case: used all parentheses
        if len(current) == 2 * n:
            result.append(current)
            return

        # Add opening parenthesis
        if open_count < n:
            backtrack(current + '(', open_count + 1, close_count)

        # Add closing parenthesis
        if close_count < open_count:
            backtrack(current + ')', open_count, close_count + 1)

    result = []
    backtrack('', 0, 0)
    return result

print(generate_parentheses(3))
# Output: ['((()))', '(()())', '(())()', '()(())', '()()()']

def generate_parentheses(n):
    """
    Generate all combinations of n pairs of valid parentheses
    """
    def backtrack(current, open_count, close_count):
        # Base case: used all parentheses
        if len(current) == 2 * n:
            result.append(current)
            return

        # Add opening parenthesis
        if open_count < n:
            backtrack(current + '(', open_count + 1, close_count)

        # Add closing parenthesis
        if close_count < open_count:
            backtrack(current + ')', open_count, close_count + 1)

    result = []
    backtrack('', 0, 0)
    return result

print(generate_parentheses(3))
# Output: ['((()))', '(()())', '(())()', '()(())', '()()()']

Python

5. Flattening Nested Structures

def flatten_list(nested_list):
    """Flatten arbitrarily nested list"""
    result = []

    for item in nested_list:
        if isinstance(item, list):
            # Recursively flatten nested list
            result.extend(flatten_list(item))
        else:
            result.append(item)

    return result

nested = [1, [2, 3, [4, 5]], 6, [7, [8, 9]]]
print(flatten_list(nested))
# Output: [1, 2, 3, 4, 5, 6, 7, 8, 9]

def flatten_list(nested_list):
    """Flatten arbitrarily nested list"""
    result = []

    for item in nested_list:
        if isinstance(item, list):
            # Recursively flatten nested list
            result.extend(flatten_list(item))
        else:
            result.append(item)

    return result

nested = [1, [2, 3, [4, 5]], 6, [7, [8, 9]]]
print(flatten_list(nested))
# Output: [1, 2, 3, 4, 5, 6, 7, 8, 9]

Python

Flatten Dictionary

def flatten_dict(d, parent_key='', sep='_'):
    """Flatten nested dictionary"""
    items = []

    for k, v in d.items():
        new_key = f"{parent_key}{sep}{k}" if parent_key else k

        if isinstance(v, dict):
            # Recursively flatten nested dict
            items.extend(flatten_dict(v, new_key, sep).items())
        else:
            items.append((new_key, v))

    return dict(items)

nested_dict = {
    'a': 1,
    'b': {
        'c': 2,
        'd': {
            'e': 3
        }
    }
}
print(flatten_dict(nested_dict))
# Output: {'a': 1, 'b_c': 2, 'b_d_e': 3}

def flatten_dict(d, parent_key='', sep='_'):
    """Flatten nested dictionary"""
    items = []

    for k, v in d.items():
        new_key = f"{parent_key}{sep}{k}" if parent_key else k

        if isinstance(v, dict):
            # Recursively flatten nested dict
            items.extend(flatten_dict(v, new_key, sep).items())
        else:
            items.append((new_key, v))

    return dict(items)

nested_dict = {
    'a': 1,
    'b': {
        'c': 2,
        'd': {
            'e': 3
        }
    }
}
print(flatten_dict(nested_dict))
# Output: {'a': 1, 'b_c': 2, 'b_d_e': 3}

Python

6. Recursion with Pruning

Sudoku Solver

def solve_sudoku(board):
    """
    Solve Sudoku puzzle using backtracking with pruning
    """
    def is_valid(board, row, col, num):
        # Check row
        if num in board[row]:
            return False

        # Check column
        if num in [board[i][col] for i in range(9)]:
            return False

        # Check 3x3 box
        box_row, box_col = 3 * (row // 3), 3 * (col // 3)
        for i in range(box_row, box_row + 3):
            for j in range(box_col, box_col + 3):
                if board[i][j] == num:
                    return False

        return True

    def solve():
        for row in range(9):
            for col in range(9):
                if board[row][col] == 0:
                    # Try digits 1-9
                    for num in range(1, 10):
                        if is_valid(board, row, col, num):
                            board[row][col] = num

                            if solve():
                                return True

                            # Backtrack
                            board[row][col] = 0

                    return False
        return True

    solve()
    return board

# Example board (0 represents empty cell)
board = [
    [5, 3, 0, 0, 7, 0, 0, 0, 0],
    [6, 0, 0, 1, 9, 5, 0, 0, 0],
    [0, 9, 8, 0, 0, 0, 0, 6, 0],
    [8, 0, 0, 0, 6, 0, 0, 0, 3],
    [4, 0, 0, 8, 0, 3, 0, 0, 1],
    [7, 0, 0, 0, 2, 0, 0, 0, 6],
    [0, 6, 0, 0, 0, 0, 2, 8, 0],
    [0, 0, 0, 4, 1, 9, 0, 0, 5],
    [0, 0, 0, 0, 8, 0, 0, 7, 9]
]

solve_sudoku(board)
for row in board:
    print(row)

def solve_sudoku(board):
    """
    Solve Sudoku puzzle using backtracking with pruning
    """
    def is_valid(board, row, col, num):
        # Check row
        if num in board[row]:
            return False

        # Check column
        if num in [board[i][col] for i in range(9)]:
            return False

        # Check 3x3 box
        box_row, box_col = 3 * (row // 3), 3 * (col // 3)
        for i in range(box_row, box_row + 3):
            for j in range(box_col, box_col + 3):
                if board[i][j] == num:
                    return False

        return True

    def solve():
        for row in range(9):
            for col in range(9):
                if board[row][col] == 0:
                    # Try digits 1-9
                    for num in range(1, 10):
                        if is_valid(board, row, col, num):
                            board[row][col] = num

                            if solve():
                                return True

                            # Backtrack
                            board[row][col] = 0

                    return False
        return True

    solve()
    return board

# Example board (0 represents empty cell)
board = [
    [5, 3, 0, 0, 7, 0, 0, 0, 0],
    [6, 0, 0, 1, 9, 5, 0, 0, 0],
    [0, 9, 8, 0, 0, 0, 0, 6, 0],
    [8, 0, 0, 0, 6, 0, 0, 0, 3],
    [4, 0, 0, 8, 0, 3, 0, 0, 1],
    [7, 0, 0, 0, 2, 0, 0, 0, 6],
    [0, 6, 0, 0, 0, 0, 2, 8, 0],
    [0, 0, 0, 4, 1, 9, 0, 0, 5],
    [0, 0, 0, 0, 8, 0, 0, 7, 9]
]

solve_sudoku(board)
for row in board:
    print(row)

Python

10. Best Practices and Tips

Essential Guidelines

1. Always Define Base Case First

# ✅ GOOD: Base case clearly defined
def factorial(n):
    if n <= 1:  # Base case first
        return 1
    return n * factorial(n - 1)

# ❌ BAD: Missing or unclear base case
def factorial_bad(n):
    return n * factorial_bad(n - 1)  # Stack overflow!

# ✅ GOOD: Base case clearly defined
def factorial(n):
    if n <= 1:  # Base case first
        return 1
    return n * factorial(n - 1)

# ❌ BAD: Missing or unclear base case
def factorial_bad(n):
    return n * factorial_bad(n - 1)  # Stack overflow!

Python

2. Make Progress Toward Base Case

# ✅ GOOD: Always moving toward base case
def countdown(n):
    if n <= 0:
        return
    print(n)
    countdown(n - 1)  # Getting closer to base case

# ❌ BAD: Not making progress
def infinite_loop(n):
    if n <= 0:
        return
    print(n)
    infinite_loop(n + 1)  # Moving away from base case!

# ✅ GOOD: Always moving toward base case
def countdown(n):
    if n <= 0:
        return
    print(n)
    countdown(n - 1)  # Getting closer to base case

# ❌ BAD: Not making progress
def infinite_loop(n):
    if n <= 0:
        return
    print(n)
    infinite_loop(n + 1)  # Moving away from base case!

Python

3. Use Memoization for Overlapping Subproblems

# ✅ GOOD: Memoization avoids redundant calculations
from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

# ❌ BAD: Exponential time complexity
def fibonacci_slow(n):
    if n <= 1:
        return n
    return fibonacci_slow(n - 1) + fibonacci_slow(n - 2)

# ✅ GOOD: Memoization avoids redundant calculations
from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

# ❌ BAD: Exponential time complexity
def fibonacci_slow(n):
    if n <= 1:
        return n
    return fibonacci_slow(n - 1) + fibonacci_slow(n - 2)

Python

4. Consider Stack Depth

import sys

# Check and set recursion limit
print(f"Current limit: {sys.getrecursionlimit()}")

# For deep recursion, increase limit carefully
sys.setrecursionlimit(5000)

# Or convert to iteration
def deep_sum_iterative(n):
    total = 0
    for i in range(1, n + 1):
        total += i
    return total

import sys

# Check and set recursion limit
print(f"Current limit: {sys.getrecursionlimit()}")

# For deep recursion, increase limit carefully
sys.setrecursionlimit(5000)

# Or convert to iteration
def deep_sum_iterative(n):
    total = 0
    for i in range(1, n + 1):
        total += i
    return total

Python

5. Use Helper Functions

# ✅ GOOD: Clean public interface with helper
def reverse_list(arr):
    """Public function with clean interface"""
    def helper(arr, left, right):
        if left >= right:
            return arr
        arr[left], arr[right] = arr[right], arr[left]
        return helper(arr, left + 1, right - 1)

    return helper(arr, 0, len(arr) - 1)

# ❌ BAD: Exposing implementation details
def reverse_list_bad(arr, left=0, right=None):
    if right is None:
        right = len(arr) - 1
    # ... implementation

# ✅ GOOD: Clean public interface with helper
def reverse_list(arr):
    """Public function with clean interface"""
    def helper(arr, left, right):
        if left >= right:
            return arr
        arr[left], arr[right] = arr[right], arr[left]
        return helper(arr, left + 1, right - 1)

    return helper(arr, 0, len(arr) - 1)

# ❌ BAD: Exposing implementation details
def reverse_list_bad(arr, left=0, right=None):
    if right is None:
        right = len(arr) - 1
    # ... implementation

Python

Debugging Recursion

Add Trace/Debug Information

def factorial_debug(n, depth=0):
    """Factorial with debugging output"""
    indent = "  " * depth
    print(f"{indent}→ factorial({n}) called")

    if n <= 1:
        print(f"{indent}← factorial({n}) = 1")
        return 1

    result = n * factorial_debug(n - 1, depth + 1)
    print(f"{indent}← factorial({n}) = {result}")
    return result

factorial_debug(4)

def factorial_debug(n, depth=0):
    """Factorial with debugging output"""
    indent = "  " * depth
    print(f"{indent}→ factorial({n}) called")

    if n <= 1:
        print(f"{indent}← factorial({n}) = 1")
        return 1

    result = n * factorial_debug(n - 1, depth + 1)
    print(f"{indent}← factorial({n}) = {result}")
    return result

factorial_debug(4)

Python

Visualize Call Stack

class RecursionVisualizer:
    def __init__(self):
        self.depth = 0

    def call(self, func_name, *args):
        print("  " * self.depth + f"→ {func_name}({', '.join(map(str, args))})")
        self.depth += 1

    def return_value(self, func_name, value):
        self.depth -= 1
        print("  " * self.depth + f"← {func_name} = {value}")
        return value

viz = RecursionVisualizer()

def fib_viz(n):
    viz.call("fib", n)
    if n <= 1:
        return viz.return_value("fib", n)
    result = fib_viz(n - 1) + fib_viz(n - 2)
    return viz.return_value("fib", result)

fib_viz(4)

class RecursionVisualizer:
    def __init__(self):
        self.depth = 0

    def call(self, func_name, *args):
        print("  " * self.depth + f"→ {func_name}({', '.join(map(str, args))})")
        self.depth += 1

    def return_value(self, func_name, value):
        self.depth -= 1
        print("  " * self.depth + f"← {func_name} = {value}")
        return value

viz = RecursionVisualizer()

def fib_viz(n):
    viz.call("fib", n)
    if n <= 1:
        return viz.return_value("fib", n)
    result = fib_viz(n - 1) + fib_viz(n - 2)
    return viz.return_value("fib", result)

fib_viz(4)

Python

Performance Considerations

Measure Performance

import time
from functools import wraps

def measure_time(func):
    @wraps(func)
    def wrapper(*args, **kwargs):
        start = time.time()
        result = func(*args, **kwargs)
        end = time.time()
        print(f"{func.__name__} took {end - start:.6f} seconds")
        return result
    return wrapper

@measure_time
def fibonacci_recursive(n):
    if n <= 1:
        return n
    return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)

@measure_time
def fibonacci_iterative(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

fibonacci_recursive(30)
fibonacci_iterative(30)

import time
from functools import wraps

def measure_time(func):
    @wraps(func)
    def wrapper(*args, **kwargs):
        start = time.time()
        result = func(*args, **kwargs)
        end = time.time()
        print(f"{func.__name__} took {end - start:.6f} seconds")
        return result
    return wrapper

@measure_time
def fibonacci_recursive(n):
    if n <= 1:
        return n
    return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)

@measure_time
def fibonacci_iterative(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

fibonacci_recursive(30)
fibonacci_iterative(30)

Python

Common Pitfalls to Avoid

1. Missing Base Case

# ❌ WRONG: No base case → infinite recursion
def bad_recursion(n):
    return bad_recursion(n - 1)

# ✅ CORRECT
def good_recursion(n):
    if n <= 0:  # Base case
        return 0
    return good_recursion(n - 1)

# ❌ WRONG: No base case → infinite recursion
def bad_recursion(n):
    return bad_recursion(n - 1)

# ✅ CORRECT
def good_recursion(n):
    if n <= 0:  # Base case
        return 0
    return good_recursion(n - 1)

Python

2. Modifying Mutable Arguments

# ❌ WRONG: Modifying shared list
def bad_subsets(arr, index=0, current=[]):  # Don't use mutable default!
    if index == len(arr):
        print(current)
        return
    bad_subsets(arr, index + 1, current)
    current.append(arr[index])  # Modifies shared list
    bad_subsets(arr, index + 1, current)

# ✅ CORRECT: Create new list
def good_subsets(arr, index=0, current=None):
    if current is None:
        current = []
    if index == len(arr):
        print(current)
        return
    good_subsets(arr, index + 1, current)
    good_subsets(arr, index + 1, current + [arr[index]])  # New list

# ❌ WRONG: Modifying shared list
def bad_subsets(arr, index=0, current=[]):  # Don't use mutable default!
    if index == len(arr):
        print(current)
        return
    bad_subsets(arr, index + 1, current)
    current.append(arr[index])  # Modifies shared list
    bad_subsets(arr, index + 1, current)

# ✅ CORRECT: Create new list
def good_subsets(arr, index=0, current=None):
    if current is None:
        current = []
    if index == len(arr):
        print(current)
        return
    good_subsets(arr, index + 1, current)
    good_subsets(arr, index + 1, current + [arr[index]])  # New list

Python

3. Inefficient String Concatenation

# ❌ WRONG: Creates new string each time
def inefficient_reverse(s):
    if len(s) <= 1:
        return s
    return s[-1] + inefficient_reverse(s[:-1])  # O(n²) time

# ✅ CORRECT: Use list and join
def efficient_reverse(s):
    def helper(s, index, result):
        if index < 0:
            return ''.join(result)
        result.append(s[index])
        return helper(s, index - 1, result)
    return helper(s, len(s) - 1, [])

# ❌ WRONG: Creates new string each time
def inefficient_reverse(s):
    if len(s) <= 1:
        return s
    return s[-1] + inefficient_reverse(s[:-1])  # O(n²) time

# ✅ CORRECT: Use list and join
def efficient_reverse(s):
    def helper(s, index, result):
        if index < 0:
            return ''.join(result)
        result.append(s[index])
        return helper(s, index - 1, result)
    return helper(s, len(s) - 1, [])

Python

Recursion Checklist

Before writing recursive function, ask:

Have I defined all base cases?
Does each recursive call make progress toward base case?
Are there overlapping subproblems? (Use memoization)
Is stack depth a concern? (Consider iteration)
Could this be more efficient iteratively?
Am I handling mutable arguments correctly?
Have I tested edge cases (empty input, single element)?
Is the recursion depth within Python’s limit?

Interview Tips

Start with Base Case: Always identify and implement base case first
Draw Recursion Tree: Visualize the problem for better understanding
Explain Your Thinking: Walk through a small example
Discuss Time/Space Complexity: Analyze before and after optimization
Mention Alternatives: Discuss recursive vs iterative trade-offs
Test Edge Cases: Empty input, single element, maximum input
Optimize if Needed: Suggest memoization or DP for overlapping subproblems

Example Interview Problem Walkthrough

Problem: Calculate power(x, n) efficiently

# Step 1: Naive recursive solution
def power_v1(x, n):
    """Time: O(n), Space: O(n)"""
    if n == 0:
        return 1
    return x * power_v1(x, n - 1)

# Step 2: Optimized with binary exponentiation
def power_v2(x, n):
    """Time: O(log n), Space: O(log n)"""
    if n == 0:
        return 1

    # Divide and conquer
    half = power_v2(x, n // 2)

    if n % 2 == 0:
        return half * half
    else:
        return x * half * half

# Step 3: Handle negative exponents
def power_v3(x, n):
    """Complete solution"""
    if n == 0:
        return 1

    if n < 0:
        return 1 / power_v3(x, -n)

    half = power_v3(x, n // 2)

    if n % 2 == 0:
        return half * half
    else:
        return x * half * half

# Test all versions
print(power_v1(2, 10))   # 1024
print(power_v2(2, 10))   # 1024
print(power_v3(2, -3))   # 0.125

# Step 1: Naive recursive solution
def power_v1(x, n):
    """Time: O(n), Space: O(n)"""
    if n == 0:
        return 1
    return x * power_v1(x, n - 1)

# Step 2: Optimized with binary exponentiation
def power_v2(x, n):
    """Time: O(log n), Space: O(log n)"""
    if n == 0:
        return 1

    # Divide and conquer
    half = power_v2(x, n // 2)

    if n % 2 == 0:
        return half * half
    else:
        return x * half * half

# Step 3: Handle negative exponents
def power_v3(x, n):
    """Complete solution"""
    if n == 0:
        return 1

    if n < 0:
        return 1 / power_v3(x, -n)

    half = power_v3(x, n // 2)

    if n % 2 == 0:
        return half * half
    else:
        return x * half * half

# Test all versions
print(power_v1(2, 10))   # 1024
print(power_v2(2, 10))   # 1024
print(power_v3(2, -3))   # 0.125

Python

Summary

Key Takeaways

Recursion Basics
- Function calls itself to solve smaller subproblems
- Must have base case and recursive case
- Uses call stack for execution
Types of Recursion
- Direct, indirect, tail, head, tree, nested
- Each has different characteristics and use cases
Common Patterns
- Linear recursion, divide-and-conquer, backtracking
- Tree recursion, accumulator pattern
Optimization
- Memoization for overlapping subproblems
- Convert tail recursion to iteration
- Use dynamic programming for bottom-up approach
Best Practices
- Define base case first
- Ensure progress toward base case
- Use helper functions for clean interface
- Consider iterative alternatives for deep recursion
- Profile and optimize when necessary

Quick Reference

# Basic Template
def recursive_function(problem):
    # Base case
    if is_base_case(problem):
        return base_solution

    # Recursive case
    smaller_problem = reduce(problem)
    smaller_solution = recursive_function(smaller_problem)

    # Combine solutions
    return combine(smaller_solution)

# With Memoization
from functools import lru_cache

@lru_cache(maxsize=None)
def memoized_function(n):
    if n <= 1:
        return n
    return memoized_function(n - 1) + memoized_function(n - 2)

# Backtracking Template
def backtrack(state):
    if is_complete(state):
        process_solution(state)
        return

    for choice in get_choices(state):
        make_choice(state, choice)
        backtrack(state)
        undo_choice(state, choice)

# Basic Template
def recursive_function(problem):
    # Base case
    if is_base_case(problem):
        return base_solution

    # Recursive case
    smaller_problem = reduce(problem)
    smaller_solution = recursive_function(smaller_problem)

    # Combine solutions
    return combine(smaller_solution)

# With Memoization
from functools import lru_cache

@lru_cache(maxsize=None)
def memoized_function(n):
    if n <= 1:
        return n
    return memoized_function(n - 1) + memoized_function(n - 2)

# Backtracking Template
def backtrack(state):
    if is_complete(state):
        process_solution(state)
        return

    for choice in get_choices(state):
        make_choice(state, choice)
        backtrack(state)
        undo_choice(state, choice)

Python

Resources for Further Learning

Classic Problems: Towers of Hanoi, N-Queens, Subset Sum
Algorithms: Merge Sort, Quick Sort, Binary Search
Data Structures: Trees, Graphs, Linked Lists
Advanced Topics: Dynamic Programming, Backtracking, Divide-and-Conquer

Happy Recursing! 🔁

Discover more from Altgr Blog

Subscribe to get the latest posts sent to your email.

Table of Contents

1. Introduction

What is Recursion?

Key Concept

Why Use Recursion?

When to Use Recursion?

2. Fundamentals of Recursion

The Two Essential Components

1. Base Case (Termination Condition)

2. Recursive Case (Self-Call)

Anatomy of a Recursive Function

Simple Examples

Example 1: Sum of Natural Numbers

Example 2: Power Function

Example 3: String Reversal

3. How Recursion Works

The Call Stack

Visualization: Factorial(4)

Detailed Trace

Memory Management

4. Types of Recursion

1. Direct Recursion

2. Indirect Recursion

3. Tail Recursion

4. Head Recursion

5. Tree Recursion

6. Nested Recursion

5. Common Recursion Patterns

Pattern 1: Linear Recursion (Process and Recur)

Pattern 2: Divide and Conquer

Pattern 3: Backtracking

Pattern 4: Tree Recursion with Multiple Branches

Pattern 5: Accumulator Pattern

6. Classic Recursion Problems

Problem 1: Factorial

Problem 2: Fibonacci Sequence

Problem 3: Sum of Digits

Problem 4: Greatest Common Divisor (GCD)

Problem 5: Tower of Hanoi

Problem 6: Palindrome Check

Problem 7: Array Sum

Problem 8: Power Function (Optimized)

Problem 9: Binary Search

Problem 10: Subset Generation

Problem 11: N-Queens Problem

Problem 12: Merge Sort

Problem 13: Quick Sort

7. Recursion vs Iteration

Comparison Table

Same Problem Both Ways

Example 1: Factorial

Example 2: Fibonacci

Example 3: Array Sum

When to Choose Which?

Converting Recursion to Iteration

8. Optimization Techniques

1. Memoization (Top-Down Dynamic Programming)

Fibonacci with Memoization

Using Python’s LRU Cache

Memoization Pattern

2. Tail Call Optimization (Manual)

3. Using Generators for Large Results

4. Reducing Redundant Calculations

Grid Paths with Memoization

5. Bottom-Up Approach (Dynamic Programming)

Space-Optimized DP

9. Advanced Recursion Topics

1. Recursive Data Structures

Linked List Operations

Binary Tree Operations

2. Mutual Recursion

Expression Evaluation

3. Recursion with Multiple Parameters

Edit Distance (Levenshtein Distance)

4. Recursion with State

Generate Valid Parentheses

5. Flattening Nested Structures

Flatten Dictionary

6. Recursion with Pruning

Sudoku Solver