Complete DSA Series Part 2: Recursion Complete Guide

How Recursion Works

Recursion is a method where a function calls itself to solve a problem by breaking it down into smaller, similar subproblems. Every recursive solution needs two essential components.

Python

# Basic Recursion Structure
def factorial(n):
    # Base Case: Stop when n reaches 0 or 1
    if n <= 1:
        return 1
    
    # Recursive Case: n! = n × (n-1)!
    return n * factorial(n - 1)

# Test
print(f"5! = {factorial(5)}")  # Output: 120
print(f"0! = {factorial(0)}")  # Output: 1

C++

// Basic Recursion Structure in C++
#include <iostream>
using namespace std;

int factorial(int n) {
    // Base Case: Stop when n reaches 0 or 1
    if (n <= 1) {
        return 1;
    }
    
    // Recursive Case: n! = n × (n-1)!
    return n * factorial(n - 1);
}

int main() {
    cout << "5! = " << factorial(5) << endl;  // Output: 120
    cout << "0! = " << factorial(0) << endl;  // Output: 1
    return 0;
}

Java

// Basic Recursion Structure in Java
public class Factorial {
    // Recursive factorial method
    public static int factorial(int n) {
        // Base Case: Stop when n reaches 0 or 1
        if (n <= 1) {
            return 1;
        }
        
        // Recursive Case: n! = n × (n-1)!
        return n * factorial(n - 1);
    }
    
    public static void main(String[] args) {
        System.out.println("5! = " + factorial(5));  // Output: 120
        System.out.println("0! = " + factorial(0));  // Output: 1
    }
}

Call Stack Tracing

Understanding how the call stack works is crucial for mastering recursion. Each recursive call creates a new stack frame with its own local variables.

Python

# Visualizing Call Stack for factorial(4)

def factorial_traced(n, depth=0):
    """Factorial with call stack visualization"""
    indent = "  " * depth
    print(f"{indent}factorial({n}) called")
    
    if n <= 1:
        print(f"{indent}factorial({n}) returns 1 (base case)")
        return 1
    
    result = n * factorial_traced(n - 1, depth + 1)
    print(f"{indent}factorial({n}) returns {result}")
    return result

# Trace factorial(4)
print("Call Stack Trace:")
result = factorial_traced(4)
print(f"\nFinal Result: {result}")

# Output:
# factorial(4) called
#   factorial(3) called
#     factorial(2) called
#       factorial(1) called
#       factorial(1) returns 1 (base case)
#     factorial(2) returns 2
#   factorial(3) returns 6
# factorial(4) returns 24
# Final Result: 24

C++

// Visualizing Call Stack for factorial(4) in C++
#include <iostream>
#include <string>
using namespace std;

int factorial_traced(int n, int depth = 0) {
    string indent(depth * 2, ' ');  // Create indentation
    cout << indent << "factorial(" << n << ") called" << endl;
    
    if (n <= 1) {
        cout << indent << "factorial(" << n << ") returns 1 (base case)" << endl;
        return 1;
    }
    
    int result = n * factorial_traced(n - 1, depth + 1);
    cout << indent << "factorial(" << n << ") returns " << result << endl;
    return result;
}

int main() {
    cout << "Call Stack Trace:" << endl;
    int result = factorial_traced(4);
    cout << "\nFinal Result: " << result << endl;
    return 0;
}

Java

// Visualizing Call Stack for factorial(4) in Java
public class CallStackTrace {
    public static int factorialTraced(int n, int depth) {
        String indent = "  ".repeat(depth);  // Create indentation
        System.out.println(indent + "factorial(" + n + ") called");
        
        if (n <= 1) {
            System.out.println(indent + "factorial(" + n + ") returns 1 (base case)");
            return 1;
        }
        
        int result = n * factorialTraced(n - 1, depth + 1);
        System.out.println(indent + "factorial(" + n + ") returns " + result);
        return result;
    }
    
    public static void main(String[] args) {
        System.out.println("Call Stack Trace:");
        int result = factorialTraced(4, 0);
        System.out.println("\nFinal Result: " + result);
    }
}

Types of Recursion

1. Tail Recursion

The recursive call is the last operation in the function. Can be optimized by compilers to use constant stack space (Tail Call Optimization).

Python

# Tail Recursion - recursive call is last operation
def factorial_tail(n, accumulator=1):
    """
    Tail-recursive factorial
    All computation done BEFORE the recursive call
    """
    if n <= 1:
        return accumulator
    return factorial_tail(n - 1, n * accumulator)  # Last operation

# Test
print(f"Tail recursive: {factorial_tail(5)}")  # Output: 120

C++

// Tail Recursion in C++
#include <iostream>
using namespace std;

int factorial_tail(int n, int accumulator = 1) {
    // Base case
    if (n <= 1) {
        return accumulator;
    }
    // Tail recursive call - computation done before call
    return factorial_tail(n - 1, n * accumulator);
}

int main() {
    cout << "Tail recursive: " << factorial_tail(5) << endl;  // Output: 120
    return 0;
}

Java

// Tail Recursion in Java
public class TailRecursion {
    public static int factorialTail(int n, int accumulator) {
        // Base case
        if (n <= 1) {
            return accumulator;
        }
        // Tail recursive call
        return factorialTail(n - 1, n * accumulator);
    }
    
    public static void main(String[] args) {
        System.out.println("Tail recursive: " + factorialTail(5, 1));  // Output: 120
    }
}

2. Head Recursion

The recursive call is made before any other processing. Work is done during the "unwinding" phase.

Python

# Head Recursion - processing after recursive call
def print_numbers_head(n):
    """
    Head-recursive: prints numbers 1 to n
    Processing happens AFTER the recursive call returns
    """
    if n == 0:
        return
    print_numbers_head(n - 1)  # Recursive call FIRST
    print(n)  # Processing AFTER

# Test
print("Head Recursion (1 to 5):")
print_numbers_head(5)  # Output: 1, 2, 3, 4, 5

C++

// Head Recursion in C++
#include <iostream>
using namespace std;

void printNumbersHead(int n) {
    if (n == 0) {
        return;
    }
    printNumbersHead(n - 1);  // Recursive call FIRST
    cout << n << " ";         // Processing AFTER
}

int main() {
    cout << "Head Recursion (1 to 5): ";
    printNumbersHead(5);  // Output: 1 2 3 4 5
    cout << endl;
    return 0;
}

Java

// Head Recursion in Java
public class HeadRecursion {
    public static void printNumbersHead(int n) {
        if (n == 0) {
            return;
        }
        printNumbersHead(n - 1);  // Recursive call FIRST
        System.out.print(n + " ");  // Processing AFTER
    }
    
    public static void main(String[] args) {
        System.out.print("Head Recursion (1 to 5): ");
        printNumbersHead(5);  // Output: 1 2 3 4 5
        System.out.println();
    }
}

3. Tree Recursion

The function makes multiple recursive calls in each invocation, creating a tree-like call structure.

Python

# Tree Recursion - multiple recursive calls
def fibonacci_tree(n):
    """
    Tree-recursive Fibonacci
    Each call branches into two more calls
    Time: O(2^n) - exponential!
    """
    if n <= 1:
        return n
    return fibonacci_tree(n - 1) + fibonacci_tree(n - 2)  # Two calls

# Test
print(f"Fibonacci(10) = {fibonacci_tree(10)}")  # Output: 55

C++

// Tree Recursion in C++
#include <iostream>
using namespace std;

int fibonacci_tree(int n) {
    // Base case
    if (n <= 1) {
        return n;
    }
    // Tree recursion - two recursive calls
    return fibonacci_tree(n - 1) + fibonacci_tree(n - 2);
}

int main() {
    cout << "Fibonacci(10) = " << fibonacci_tree(10) << endl;  // Output: 55
    return 0;
}

Java

// Tree Recursion in Java
public class TreeRecursion {
    public static int fibonacciTree(int n) {
        // Base case
        if (n <= 1) {
            return n;
        }
        // Tree recursion - two recursive calls
        return fibonacciTree(n - 1) + fibonacciTree(n - 2);
    }
    
    public static void main(String[] args) {
        System.out.println("Fibonacci(10) = " + fibonacciTree(10));  // Output: 55
    }
}

4. Indirect Recursion

Function A calls function B, which calls function A (or through more functions in a cycle).

Python

# Indirect Recursion - functions call each other
def is_even(n):
    if n == 0:
        return True
    return is_odd(n - 1)

def is_odd(n):
    if n == 0:
        return False
    return is_even(n - 1)

# Test
print(f"is_even(4) = {is_even(4)}")  # True
print(f"is_odd(5) = {is_odd(5)}")    # True

C++

// Indirect Recursion in C++
#include <iostream>
using namespace std;

// Forward declaration needed for indirect recursion
bool isOdd(int n);

bool isEven(int n) {
    if (n == 0) return true;
    return isOdd(n - 1);
}

bool isOdd(int n) {
    if (n == 0) return false;
    return isEven(n - 1);
}

int main() {
    cout << "isEven(4) = " << (isEven(4) ? "true" : "false") << endl;  // true
    cout << "isOdd(5) = " << (isOdd(5) ? "true" : "false") << endl;    // true
    return 0;
}

Java

// Indirect Recursion in Java
public class IndirectRecursion {
    public static boolean isEven(int n) {
        if (n == 0) return true;
        return isOdd(n - 1);
    }
    
    public static boolean isOdd(int n) {
        if (n == 0) return false;
        return isEven(n - 1);
    }
    
    public static void main(String[] args) {
        System.out.println("isEven(4) = " + isEven(4));  // true
        System.out.println("isOdd(5) = " + isOdd(5));    // true
    }
}

5. Nested Recursion

A recursive call is used as an argument to another recursive call.

Python

# Nested Recursion - recursive call as argument
def ackermann(m, n):
    """
    Ackermann function - classic nested recursion example
    Grows EXTREMELY fast
    """
    if m == 0:
        return n + 1
    if n == 0:
        return ackermann(m - 1, 1)
    return ackermann(m - 1, ackermann(m, n - 1))  # Nested!

# Test (only small values!)
print(f"ackermann(2, 2) = {ackermann(2, 2)}")  # Output: 7
print(f"ackermann(3, 2) = {ackermann(3, 2)}")  # Output: 29

C++

// Nested Recursion - Ackermann Function in C++
#include <iostream>
using namespace std;

int ackermann(int m, int n) {
    if (m == 0) {
        return n + 1;
    }
    if (n == 0) {
        return ackermann(m - 1, 1);
    }
    // Nested recursion - inner call's result becomes argument
    return ackermann(m - 1, ackermann(m, n - 1));
}

int main() {
    cout << "ackermann(2, 2) = " << ackermann(2, 2) << endl;  // Output: 7
    cout << "ackermann(3, 2) = " << ackermann(3, 2) << endl;  // Output: 29
    return 0;
}

Java

// Nested Recursion - Ackermann Function in Java
public class NestedRecursion {
    public static int ackermann(int m, int n) {
        if (m == 0) {
            return n + 1;
        }
        if (n == 0) {
            return ackermann(m - 1, 1);
        }
        // Nested recursion - inner call's result becomes argument
        return ackermann(m - 1, ackermann(m, n - 1));
    }
    
    public static void main(String[] args) {
        System.out.println("ackermann(2, 2) = " + ackermann(2, 2));  // Output: 7
        System.out.println("ackermann(3, 2) = " + ackermann(3, 2));  // Output: 29
    }
}

Recurrence Relations

Common Recurrence Patterns

Here are the most frequently encountered recurrence patterns in algorithm analysis:

Solving Recurrences: Step-by-Step Example

Let's solve T(n) = 2T(n/2) + n using the substitution method:

Step 1: Expand the recurrence (unroll it)

T(n) = 2T(n/2) + n
     = 2[2T(n/4) + n/2] + n
     = 4T(n/4) + n + n
     = 4[2T(n/8) + n/4] + 2n
     = 8T(n/8) + n + n + n
     = 8T(n/8) + 3n

Step 2: Find the pattern

After k iterations: T(n) = 2? T(n/2?) + kn

Step 3: Find when to stop (base case)

When n/2? = 1, so 2? = n, meaning k = log2(n)

Step 4: Substitute back

T(n) = n × T(1) + n × log2(n)
     = n × O(1) + n log n
     = O(n log n)  ?

Master Theorem

Master Theorem Examples

Classic Recursive Problems

Fibonacci Sequence

Approach 1: Naive Tree Recursion - O(2ⁿ)

The simplest implementation directly follows the mathematical definition, but it's extremely inefficient because it recalculates the same values many times:

                    fib(5)
                   /      \
              fib(4)      fib(3)
             /    \        /    \
         fib(3)  fib(2)  fib(2)  fib(1)
         /   \    /   \    /   \
     fib(2) fib(1) ...  ...  ...

Notice how fib(3) is calculated twice, fib(2) is calculated 3 times!
This exponential growth makes naive recursion impractical for n > 40.

Python - Naive Fibonacci

# Fibonacci - Naive Tree Recursion
# Time Complexity: O(2^n) - exponential
# Space Complexity: O(n) - recursion stack depth

def fib_naive(n):
    """Calculate nth Fibonacci number using naive recursion."""
    # Base cases
    if n <= 1:
        return n
    # Recursive case: F(n) = F(n-1) + F(n-2)
    return fib_naive(n - 1) + fib_naive(n - 2)

# Test - only works reasonably for small n
for i in range(11):
    print(f"F({i}) = {fib_naive(i)}")
# Output: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55

C++ - Naive Fibonacci

#include <iostream>
using namespace std;

// Naive Tree Recursion - O(2^n) time
int fib_naive(int n) {
    // Base cases
    if (n <= 1) {
        return n;
    }
    // Recursive case
    return fib_naive(n - 1) + fib_naive(n - 2);
}

int main() {
    cout << "Fibonacci Sequence (Naive):" << endl;
    for (int i = 0; i <= 10; i++) {
        cout << "F(" << i << ") = " << fib_naive(i) << endl;
    }
    // Output: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55
    return 0;
}

Java - Naive Fibonacci

public class FibonacciNaive {
    // Naive Tree Recursion - O(2^n) time
    public static int fibNaive(int n) {
        // Base cases
        if (n <= 1) {
            return n;
        }
        // Recursive case
        return fibNaive(n - 1) + fibNaive(n - 2);
    }
    
    public static void main(String[] args) {
        System.out.println("Fibonacci Sequence (Naive):");
        for (int i = 0; i <= 10; i++) {
            System.out.println("F(" + i + ") = " + fibNaive(i));
        }
        // Output: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55
    }
}

Approach 2: Memoization (Top-Down DP) - O(n)

We can dramatically improve performance by storing already-computed values in a cache (memo). This technique is called memoization and is the foundation of Dynamic Programming:

Python - Memoized Fibonacci

# Fibonacci - Memoization (Top-Down DP)
# Time Complexity: O(n) - each value computed once
# Space Complexity: O(n) - memo dictionary + recursion stack

def fib_memo(n, memo=None):
    """Calculate nth Fibonacci with memoization."""
    if memo is None:
        memo = {}
    
    # Check if already computed
    if n in memo:
        return memo[n]
    
    # Base cases
    if n <= 1:
        return n
    
    # Compute and store in memo
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

# Now we can calculate much larger values efficiently!
print(f"F(50) = {fib_memo(50)}")   # 12586269025
print(f"F(100) = {fib_memo(100)}") # 354224848179261915075

C++ - Memoized Fibonacci

#include <iostream>
#include <unordered_map>
using namespace std;

// Memoization using hash map - O(n) time
unordered_map<int, long long> memo;

long long fib_memo(int n) {
    // Check if already computed
    if (memo.find(n) != memo.end()) {
        return memo[n];
    }
    
    // Base cases
    if (n <= 1) {
        return n;
    }
    
    // Compute and store in memo
    memo[n] = fib_memo(n - 1) + fib_memo(n - 2);
    return memo[n];
}

int main() {
    cout << "Fibonacci with Memoization:" << endl;
    cout << "F(50) = " << fib_memo(50) << endl;  // 12586269025
    
    // Reset memo for clean test
    memo.clear();
    for (int i = 0; i <= 15; i++) {
        cout << "F(" << i << ") = " << fib_memo(i) << endl;
    }
    return 0;
}

Java - Memoized Fibonacci

import java.util.HashMap;
import java.util.Map;

public class FibonacciMemo {
    // Use HashMap for memoization
    private static Map<Integer, Long> memo = new HashMap<>();
    
    public static long fibMemo(int n) {
        // Check if already computed
        if (memo.containsKey(n)) {
            return memo.get(n);
        }
        
        // Base cases
        if (n <= 1) {
            return n;
        }
        
        // Compute and store in memo
        long result = fibMemo(n - 1) + fibMemo(n - 2);
        memo.put(n, result);
        return result;
    }
    
    public static void main(String[] args) {
        System.out.println("Fibonacci with Memoization:");
        System.out.println("F(50) = " + fibMemo(50));  // 12586269025
        
        // Print sequence
        memo.clear();
        for (int i = 0; i <= 15; i++) {
            System.out.println("F(" + i + ") = " + fibMemo(i));
        }
    }
}

Approach 3: Iterative (Bottom-Up DP) - O(n) time, O(1) space

The most efficient approach uses iteration instead of recursion. We only need to track the last two values, reducing space complexity to O(1):

Python - Iterative Fibonacci

# Fibonacci - Iterative (Bottom-Up DP)
# Time Complexity: O(n)
# Space Complexity: O(1) - only two variables!

def fib_iterative(n):
    """Calculate nth Fibonacci iteratively - most efficient!"""
    if n <= 1:
        return n
    
    # Only track the last two values
    prev2, prev1 = 0, 1  # F(0), F(1)
    
    for i in range(2, n + 1):
        current = prev1 + prev2
        prev2 = prev1
        prev1 = current
    
    return prev1

# Test all three approaches
print("Iterative approach (O(1) space):")
print(f"F(50) = {fib_iterative(50)}")   # 12586269025
print(f"F(100) = {fib_iterative(100)}") # 354224848179261915075

C++ - Iterative Fibonacci

#include <iostream>
using namespace std;

// Iterative approach - O(n) time, O(1) space
long long fib_iterative(int n) {
    if (n <= 1) {
        return n;
    }
    
    // Only track the last two values
    long long prev2 = 0, prev1 = 1;
    
    for (int i = 2; i <= n; i++) {
        long long current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }
    
    return prev1;
}

int main() {
    cout << "Fibonacci Iterative (O(1) space):" << endl;
    cout << "F(50) = " << fib_iterative(50) << endl;  // 12586269025
    
    // Print sequence
    for (int i = 0; i <= 15; i++) {
        cout << "F(" << i << ") = " << fib_iterative(i) << endl;
    }
    return 0;
}

Java - Iterative Fibonacci

public class FibonacciIterative {
    // Iterative approach - O(n) time, O(1) space
    public static long fibIterative(int n) {
        if (n <= 1) {
            return n;
        }
        
        // Only track the last two values
        long prev2 = 0, prev1 = 1;
        
        for (int i = 2; i <= n; i++) {
            long current = prev1 + prev2;
            prev2 = prev1;
            prev1 = current;
        }
        
        return prev1;
    }
    
    public static void main(String[] args) {
        System.out.println("Fibonacci Iterative (O(1) space):");
        System.out.println("F(50) = " + fibIterative(50));  // 12586269025
        
        // Print sequence
        for (int i = 0; i <= 15; i++) {
            System.out.println("F(" + i + ") = " + fibIterative(i));
        }
    }
}

Tower of Hanoi

The Recursive Insight

The key insight is to think recursively: to move n disks from A to C, we need to:

1. Move n-1 disks from A to B (using C as helper)
2. Move the largest disk from A to C
3. Move n-1 disks from B to C (using A as helper)

Visual Trace for 3 Disks

Initial State:          After Move 1:           After Move 2:
    |     |     |           |     |     |           |     |     |
   [1]    |     |           |     |     |          [1]    |     |
   [2]    |     |          [2]    |     |          [2]    |     |
   [3]    |     |          [3]   [1]    |          [3]   [1]    |
  -----  -----  -----     -----  -----  -----     -----  -----  -----
    A      B      C           A      B      C         A      B      C

After Move 3:           After Move 4:           After Move 5:
    |     |     |           |     |     |           |     |     |
    |     |     |           |     |     |           |     |    [1]
   [2]    |     |           |     |     |           |     |    [2]
   [3]   [1]   [2]          |    [1]   [2]          |    [1]   [2]
  -----  -----  -----     -----  -----  -----     -----  -----  -----
    A      B      C           A      B      C         A      B      C

After Move 6:           After Move 7 (DONE!):
    |     |     |           |     |     |
    |     |    [1]          |     |    [1]
    |     |    [2]          |     |    [2]
   [3]    |     |          [3]    |    [3]
  -----  -----  -----     -----  -----  -----
    A      B      C           A      B      C

The 7 moves: (2^3 - 1 = 7)
1. Move disk 1 from A to C
2. Move disk 2 from A to B
3. Move disk 1 from C to B
4. Move disk 3 from A to C  ? The crucial "middle" move
5. Move disk 1 from B to A
6. Move disk 2 from B to C
7. Move disk 1 from A to C

Python

# Tower of Hanoi - Classic Recursion Problem
def tower_of_hanoi(n, source, auxiliary, destination):
    """
    Solve Tower of Hanoi for n disks
    Time Complexity: O(2^n) - must make 2^n - 1 moves
    Space Complexity: O(n) - recursion depth
    """
    if n == 1:
        print(f"Move disk 1 from {source} to {destination}")
        return
    
    # Step 1: Move n-1 disks from source to auxiliary (using destination as helper)
    tower_of_hanoi(n - 1, source, destination, auxiliary)
    
    # Step 2: Move the largest disk from source to destination
    print(f"Move disk {n} from {source} to {destination}")
    
    # Step 3: Move n-1 disks from auxiliary to destination (using source as helper)
    tower_of_hanoi(n - 1, auxiliary, source, destination)

# Test with 3 disks
print("Tower of Hanoi with 3 disks:")
tower_of_hanoi(3, 'A', 'B', 'C')
print(f"\nTotal moves for n disks: 2^n - 1 = {2**3 - 1} moves")

C++

// Tower of Hanoi in C++
#include <iostream>
#include <string>
using namespace std;

void towerOfHanoi(int n, char source, char auxiliary, char destination) {
    // Base case: only one disk
    if (n == 1) {
        cout << "Move disk 1 from " << source << " to " << destination << endl;
        return;
    }
    
    // Step 1: Move n-1 disks from source to auxiliary
    towerOfHanoi(n - 1, source, destination, auxiliary);
    
    // Step 2: Move largest disk from source to destination
    cout << "Move disk " << n << " from " << source << " to " << destination << endl;
    
    // Step 3: Move n-1 disks from auxiliary to destination
    towerOfHanoi(n - 1, auxiliary, source, destination);
}

int main() {
    int n = 3;
    cout << "Tower of Hanoi with " << n << " disks:" << endl;
    towerOfHanoi(n, 'A', 'B', 'C');
    cout << "\nTotal moves: " << (1 << n) - 1 << endl;  // 2^n - 1
    return 0;
}

Java

// Tower of Hanoi in Java
public class TowerOfHanoi {
    public static void towerOfHanoi(int n, char source, char auxiliary, char destination) {
        // Base case: only one disk
        if (n == 1) {
            System.out.println("Move disk 1 from " + source + " to " + destination);
            return;
        }
        
        // Step 1: Move n-1 disks from source to auxiliary
        towerOfHanoi(n - 1, source, destination, auxiliary);
        
        // Step 2: Move largest disk from source to destination
        System.out.println("Move disk " + n + " from " + source + " to " + destination);
        
        // Step 3: Move n-1 disks from auxiliary to destination
        towerOfHanoi(n - 1, auxiliary, source, destination);
    }
    
    public static void main(String[] args) {
        int n = 3;
        System.out.println("Tower of Hanoi with " + n + " disks:");
        towerOfHanoi(n, 'A', 'B', 'C');
        System.out.println("\nTotal moves: " + ((1 << n) - 1));  // 2^n - 1
    }
}

Power Function

Approach 1: Naive Recursion - O(n)

The straightforward approach multiplies the base n times:

Python - Naive Power

# Power Function - Naive Recursion
# Time Complexity: O(n) - makes n recursive calls
# Space Complexity: O(n) - recursion stack depth

def power_naive(base, exp):
    """Calculate base^exp using naive recursion."""
    # Base case: x^0 = 1
    if exp == 0:
        return 1
    # Recursive case: x^n = x * x^(n-1)
    return base * power_naive(base, exp - 1)

# Test
print(f"2^10 = {power_naive(2, 10)}")  # 1024
print(f"3^5 = {power_naive(3, 5)}")    # 243

C++ - Naive Power

#include <iostream>
using namespace std;

// Naive recursion - O(n) time
long long power_naive(int base, int exp) {
    // Base case: x^0 = 1
    if (exp == 0) {
        return 1;
    }
    // Recursive case: x^n = x * x^(n-1)
    return base * power_naive(base, exp - 1);
}

int main() {
    cout << "2^10 = " << power_naive(2, 10) << endl;  // 1024
    cout << "3^5 = " << power_naive(3, 5) << endl;    // 243
    return 0;
}

Java - Naive Power

public class PowerNaive {
    // Naive recursion - O(n) time
    public static long powerNaive(int base, int exp) {
        // Base case: x^0 = 1
        if (exp == 0) {
            return 1;
        }
        // Recursive case: x^n = x * x^(n-1)
        return base * powerNaive(base, exp - 1);
    }
    
    public static void main(String[] args) {
        System.out.println("2^10 = " + powerNaive(2, 10));  // 1024
        System.out.println("3^5 = " + powerNaive(3, 5));    // 243
    }
}

Approach 2: Fast Power (Exponentiation by Squaring) - O(log n)

The optimized approach halves the exponent at each step:

Computing 2^10 using Fast Power:

2^10 ? exp is even ? (2^5)^2
    2^5 ? exp is odd ? 2 × 2^4
        2^4 ? exp is even ? (2^2)^2
            2^2 ? exp is even ? (2^1)^2
                2^1 ? exp is odd ? 2 × 2^0
                    2^0 = 1

Unrolling:
2^0 = 1
2^1 = 2 × 1 = 2
2^2 = 2^2 = 4
2^4 = 4^2 = 16
2^5 = 2 × 16 = 32
2^10 = 32^2 = 1024

Only 4 multiplications instead of 10!

Python - Fast Power

# Power Function - Exponentiation by Squaring
# Time Complexity: O(log n) - halves problem each step
# Space Complexity: O(log n) - recursion stack depth

def power_fast(base, exp):
    """
    Fast exponentiation using squaring technique.
    x^n = (x^(n/2))^2 if n is even
    x^n = x * x^(n-1) if n is odd
    """
    # Base case
    if exp == 0:
        return 1
    
    # Even exponent: square the half-power
    if exp % 2 == 0:
        half = power_fast(base, exp // 2)
        return half * half
    
    # Odd exponent: reduce by 1 and multiply by base
    else:
        return base * power_fast(base, exp - 1)

# Test - works efficiently for large exponents
print(f"2^10 = {power_fast(2, 10)}")    # 1024
print(f"2^30 = {power_fast(2, 30)}")    # 1073741824
print(f"3^20 = {power_fast(3, 20)}")    # 3486784401

C++ - Fast Power

#include <iostream>
using namespace std;

// Fast power - O(log n) time
long long power_fast(int base, int exp) {
    // Base case
    if (exp == 0) {
        return 1;
    }
    
    // Even exponent: square the half-power
    if (exp % 2 == 0) {
        long long half = power_fast(base, exp / 2);
        return half * half;
    }
    
    // Odd exponent: reduce by 1 and multiply by base
    return base * power_fast(base, exp - 1);
}

int main() {
    cout << "2^10 = " << power_fast(2, 10) << endl;   // 1024
    cout << "2^30 = " << power_fast(2, 30) << endl;   // 1073741824
    cout << "3^20 = " << power_fast(3, 20) << endl;   // 3486784401
    return 0;
}

Java - Fast Power

public class PowerFast {
    // Fast power - O(log n) time
    public static long powerFast(int base, int exp) {
        // Base case
        if (exp == 0) {
            return 1;
        }
        
        // Even exponent: square the half-power
        if (exp % 2 == 0) {
            long half = powerFast(base, exp / 2);
            return half * half;
        }
        
        // Odd exponent: reduce by 1 and multiply by base
        return base * powerFast(base, exp - 1);
    }
    
    public static void main(String[] args) {
        System.out.println("2^10 = " + powerFast(2, 10));   // 1024
        System.out.println("2^30 = " + powerFast(2, 30));   // 1073741824
        System.out.println("3^20 = " + powerFast(3, 20));   // 3486784401
    }
}

Approach 3: Iterative Fast Power - O(log n) time, O(1) space

We can eliminate the recursion stack using an iterative approach with bit manipulation:

Python - Iterative Fast Power

# Power Function - Iterative with Bit Manipulation
# Time Complexity: O(log n)
# Space Complexity: O(1) - no recursion stack!

def power_iterative(base, exp):
    """
    Iterative fast power using binary representation.
    Example: 2^13 = 2^(1101 in binary) = 2^8 * 2^4 * 2^1
    """
    result = 1
    
    while exp > 0:
        # If current bit is 1, multiply result by base
        if exp % 2 == 1:  # or: if exp & 1:
            result *= base
        # Square the base for next bit
        base *= base
        # Move to next bit
        exp //= 2  # or: exp >>= 1
    
    return result

# Test
print(f"2^10 iterative = {power_iterative(2, 10)}")  # 1024
print(f"3^13 iterative = {power_iterative(3, 13)}")  # 1594323

C++ - Iterative Fast Power

#include <iostream>
using namespace std;

// Iterative fast power - O(log n) time, O(1) space
long long power_iterative(int base, int exp) {
    long long result = 1;
    long long b = base;  // Use long long to prevent overflow
    
    while (exp > 0) {
        // If current bit is 1, multiply result by base
        if (exp & 1) {  // Same as exp % 2 == 1
            result *= b;
        }
        // Square the base for next bit
        b *= b;
        // Move to next bit
        exp >>= 1;  // Same as exp /= 2
    }
    
    return result;
}

int main() {
    cout << "2^10 iterative = " << power_iterative(2, 10) << endl;  // 1024
    cout << "3^13 iterative = " << power_iterative(3, 13) << endl;  // 1594323
    return 0;
}

Java - Iterative Fast Power

public class PowerIterative {
    // Iterative fast power - O(log n) time, O(1) space
    public static long powerIterative(int base, int exp) {
        long result = 1;
        long b = base;  // Use long to prevent overflow
        
        while (exp > 0) {
            // If current bit is 1, multiply result by base
            if ((exp & 1) == 1) {  // Same as exp % 2 == 1
                result *= b;
            }
            // Square the base for next bit
            b *= b;
            // Move to next bit
            exp >>= 1;  // Same as exp /= 2
        }
        
        return result;
    }
    
    public static void main(String[] args) {
        System.out.println("2^10 iterative = " + powerIterative(2, 10));  // 1024
        System.out.println("3^13 iterative = " + powerIterative(3, 13));  // 1594323
    }
}

LeetCode Practice Problems

Practice these classic recursion problems to solidify your understanding. Each problem is presented with solutions in all three languages.

# LeetCode 509 - Fibonacci Number
# Time: O(n) with memoization, Space: O(n)

class Solution:
    def fib(self, n: int) -> int:
        memo = {0: 0, 1: 1}
        
        def helper(n):
            if n in memo:
                return memo[n]
            memo[n] = helper(n - 1) + helper(n - 2)
            return memo[n]
        
        return helper(n)

# Test
sol = Solution()
print(sol.fib(10))  # Output: 55
print(sol.fib(20))  # Output: 6765

#include <iostream>
#include <unordered_map>
using namespace std;

// LeetCode 509 - Fibonacci Number
// Time: O(n) with memoization
class Solution {
private:
    unordered_map<int, int> memo;
    
    int helper(int n) {
        if (memo.find(n) != memo.end()) {
            return memo[n];
        }
        memo[n] = helper(n - 1) + helper(n - 2);
        return memo[n];
    }
    
public:
    int fib(int n) {
        memo[0] = 0;
        memo[1] = 1;
        return helper(n);
    }
};

int main() {
    Solution sol;
    cout << sol.fib(10) << endl;  // Output: 55
    return 0;
}

import java.util.HashMap;
import java.util.Map;

// LeetCode 509 - Fibonacci Number
// Time: O(n) with memoization
class Solution {
    private Map<Integer, Integer> memo = new HashMap<>();
    
    public int fib(int n) {
        memo.put(0, 0);
        memo.put(1, 1);
        return helper(n);
    }
    
    private int helper(int n) {
        if (memo.containsKey(n)) {
            return memo.get(n);
        }
        int result = helper(n - 1) + helper(n - 2);
        memo.put(n, result);
        return result;
    }
    
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.fib(10));  // Output: 55
    }
}

# LeetCode 206 - Reverse Linked List (Recursive)
# Time: O(n), Space: O(n) for call stack

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        # Base case: empty list or single node
        if not head or not head.next:
            return head
        
        # Recursively reverse the rest of the list
        new_head = self.reverseList(head.next)
        
        # Fix the links: make next node point back to current
        head.next.next = head
        head.next = None  # Current node is now the tail
        
        return new_head

# Helper to create and print list
def create_list(arr):
    if not arr:
        return None
    head = ListNode(arr[0])
    curr = head
    for val in arr[1:]:
        curr.next = ListNode(val)
        curr = curr.next
    return head

def print_list(head):
    vals = []
    while head:
        vals.append(str(head.val))
        head = head.next
    print(" -> ".join(vals))

# Test
sol = Solution()
head = create_list([1, 2, 3, 4, 5])
print("Original:", end=" ")
print_list(head)
reversed_head = sol.reverseList(head)
print("Reversed:", end=" ")
print_list(reversed_head)
# Output: 5 -> 4 -> 3 -> 2 -> 1

#include <iostream>
using namespace std;

// LeetCode 206 - Reverse Linked List
// Time: O(n), Space: O(n) for call stack

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        // Base case: empty list or single node
        if (!head || !head->next) {
            return head;
        }
        
        // Recursively reverse the rest
        ListNode* newHead = reverseList(head->next);
        
        // Fix the links
        head->next->next = head;
        head->next = nullptr;
        
        return newHead;
    }
};

// Helper function to print list
void printList(ListNode* head) {
    while (head) {
        cout << head->val;
        if (head->next) cout << " -> ";
        head = head->next;
    }
    cout << endl;
}

int main() {
    // Create list: 1 -> 2 -> 3 -> 4 -> 5
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);
    
    cout << "Original: ";
    printList(head);
    
    Solution sol;
    ListNode* reversed = sol.reverseList(head);
    
    cout << "Reversed: ";
    printList(reversed);
    // Output: 5 -> 4 -> 3 -> 2 -> 1
    
    return 0;
}

// LeetCode 206 - Reverse Linked List
// Time: O(n), Space: O(n) for call stack

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

class Solution {
    public ListNode reverseList(ListNode head) {
        // Base case: empty list or single node
        if (head == null || head.next == null) {
            return head;
        }
        
        // Recursively reverse the rest
        ListNode newHead = reverseList(head.next);
        
        // Fix the links
        head.next.next = head;
        head.next = null;
        
        return newHead;
    }
    
    // Helper to print list
    public void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val);
            if (head.next != null) System.out.print(" -> ");
            head = head.next;
        }
        System.out.println();
    }
    
    public static void main(String[] args) {
        // Create list: 1 -> 2 -> 3 -> 4 -> 5
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        
        Solution sol = new Solution();
        System.out.print("Original: ");
        sol.printList(head);
        
        ListNode reversed = sol.reverseList(head);
        System.out.print("Reversed: ");
        sol.printList(reversed);
        // Output: 5 -> 4 -> 3 -> 2 -> 1
    }
}

# LeetCode 50 - Pow(x, n)
# Time: O(log n), Space: O(log n) for recursion stack

class Solution:
    def myPow(self, x: float, n: int) -> float:
        # Handle negative exponent
        if n < 0:
            x = 1 / x
            n = -n
        
        return self.fastPow(x, n)
    
    def fastPow(self, x: float, n: int) -> float:
        # Base case
        if n == 0:
            return 1.0
        
        # Use fast exponentiation
        if n % 2 == 0:
            half = self.fastPow(x, n // 2)
            return half * half
        else:
            return x * self.fastPow(x, n - 1)

# Test
sol = Solution()
print(f"2^10 = {sol.myPow(2, 10)}")     # 1024.0
print(f"2^(-2) = {sol.myPow(2, -2)}")   # 0.25
print(f"2.1^3 = {sol.myPow(2.1, 3)}")   # 9.261

#include <iostream>
using namespace std;

// LeetCode 50 - Pow(x, n)
// Time: O(log n), Space: O(log n)

class Solution {
public:
    double myPow(double x, int n) {
        // Use long long to handle INT_MIN case
        long long N = n;
        
        // Handle negative exponent
        if (N < 0) {
            x = 1 / x;
            N = -N;
        }
        
        return fastPow(x, N);
    }
    
private:
    double fastPow(double x, long long n) {
        // Base case
        if (n == 0) {
            return 1.0;
        }
        
        // Fast exponentiation
        if (n % 2 == 0) {
            double half = fastPow(x, n / 2);
            return half * half;
        } else {
            return x * fastPow(x, n - 1);
        }
    }
};

int main() {
    Solution sol;
    cout << "2^10 = " << sol.myPow(2, 10) << endl;   // 1024
    cout << "2^(-2) = " << sol.myPow(2, -2) << endl; // 0.25
    cout << "2.1^3 = " << sol.myPow(2.1, 3) << endl; // 9.261
    return 0;
}

// LeetCode 50 - Pow(x, n)
// Time: O(log n), Space: O(log n)

class Solution {
    public double myPow(double x, int n) {
        // Use long to handle Integer.MIN_VALUE case
        long N = n;
        
        // Handle negative exponent
        if (N < 0) {
            x = 1 / x;
            N = -N;
        }
        
        return fastPow(x, N);
    }
    
    private double fastPow(double x, long n) {
        // Base case
        if (n == 0) {
            return 1.0;
        }
        
        // Fast exponentiation
        if (n % 2 == 0) {
            double half = fastPow(x, n / 2);
            return half * half;
        } else {
            return x * fastPow(x, n - 1);
        }
    }
    
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println("2^10 = " + sol.myPow(2, 10));   // 1024.0
        System.out.println("2^(-2) = " + sol.myPow(2, -2)); // 0.25
        System.out.println("2.1^3 = " + sol.myPow(2.1, 3)); // 9.261
    }
}

# LeetCode 21 - Merge Two Sorted Lists
# Time: O(n + m), Space: O(n + m) for recursion stack

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        # Base cases
        if not l1:
            return l2
        if not l2:
            return l1
        
        # Recursive case: take smaller head, merge rest
        if l1.val <= l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2

# Test
def create_list(arr):
    if not arr:
        return None
    head = ListNode(arr[0])
    curr = head
    for val in arr[1:]:
        curr.next = ListNode(val)
        curr = curr.next
    return head

def print_list(head):
    vals = []
    while head:
        vals.append(str(head.val))
        head = head.next
    print(" -> ".join(vals))

sol = Solution()
l1 = create_list([1, 2, 4])
l2 = create_list([1, 3, 4])
merged = sol.mergeTwoLists(l1, l2)
print_list(merged)  # 1 -> 1 -> 2 -> 3 -> 4 -> 4

#include <iostream>
using namespace std;

// LeetCode 21 - Merge Two Sorted Lists
// Time: O(n + m), Space: O(n + m)

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        // Base cases
        if (!l1) return l2;
        if (!l2) return l1;
        
        // Take smaller head, merge rest
        if (l1->val <= l2->val) {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        } else {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
};

void printList(ListNode* head) {
    while (head) {
        cout << head->val;
        if (head->next) cout << " -> ";
        head = head->next;
    }
    cout << endl;
}

int main() {
    // Create l1: 1 -> 2 -> 4
    ListNode* l1 = new ListNode(1);
    l1->next = new ListNode(2);
    l1->next->next = new ListNode(4);
    
    // Create l2: 1 -> 3 -> 4
    ListNode* l2 = new ListNode(1);
    l2->next = new ListNode(3);
    l2->next->next = new ListNode(4);
    
    Solution sol;
    ListNode* merged = sol.mergeTwoLists(l1, l2);
    printList(merged);  // 1 -> 1 -> 2 -> 3 -> 4 -> 4
    
    return 0;
}

// LeetCode 21 - Merge Two Sorted Lists
// Time: O(n + m), Space: O(n + m)

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // Base cases
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        
        // Take smaller head, merge rest
        if (l1.val <= l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
    
    public void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val);
            if (head.next != null) System.out.print(" -> ");
            head = head.next;
        }
        System.out.println();
    }
    
    public static void main(String[] args) {
        // Create l1: 1 -> 2 -> 4
        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(2);
        l1.next.next = new ListNode(4);
        
        // Create l2: 1 -> 3 -> 4
        ListNode l2 = new ListNode(1);
        l2.next = new ListNode(3);
        l2.next.next = new ListNode(4);
        
        Solution sol = new Solution();
        ListNode merged = sol.mergeTwoLists(l1, l2);
        sol.printList(merged);  // 1 -> 1 -> 2 -> 3 -> 4 -> 4
    }
}