Recursion

Introduction

Recursion is a fundamental programming technique where a function calls itself to solve a problem. It’s a powerful approach that can make complex problems more elegant and easier to understand by breaking them down into smaller, similar subproblems.

In this article, we’ll explore recursion concepts through practical LeetCode problems, providing clean, well-explained solutions in both C# and Python.

What is Recursion?

Recursion is a method of solving problems where:

• A function calls itself with a smaller or simpler version of the problem
• The problem is broken down into smaller subproblems of the same type
• Eventually, the problem becomes simple enough to solve directly (base case)
• Solutions to subproblems are combined to solve the original problem

Key Components of Recursion:

1. Base Case The simplest instance of the problem that can be solved directly without recursion. This prevents infinite recursion.

2. Recursive Case The part where the function calls itself with a smaller or modified version of the problem.

3. Recursive Call The function calling itself with different parameters that move toward the base case.

Example: Factorial

int Factorial(int n) 
{
    // Base case
    if (n <= 1) 
        return 1;
    
    // Recursive case
    return n * Factorial(n - 1);
}

When to Use Recursion:

• Tree/Graph Traversal: Natural recursive structures
• Divide and Conquer: Problems that can be split into similar subproblems
• Backtracking: Exploring all possibilities
• Mathematical Problems: Problems with recursive definitions
• Dynamic Programming: Often implemented recursively with memoization

Advantages of Recursion:

• Elegant Code: Often more readable and intuitive
• Natural Fit: Perfect for recursive data structures (trees, graphs)
• Problem Decomposition: Breaks complex problems into simpler ones

Disadvantages of Recursion:

• Stack Overflow: Deep recursion can cause stack overflow
• Memory Overhead: Each recursive call uses stack space
• Performance: May be slower than iterative solutions due to function call overhead

Understanding the Call Stack

When a recursive function is called, each recursive call is added to the call stack:

1. Function calls are pushed onto the stack
2. Base case is reached and returns a value
3. Values are popped from the stack and combined
4. Final result is returned

Example: Factorial(4)

Factorial(4)
  → Factorial(3)
    → Factorial(2)
      → Factorial(1)  [Base case: returns 1]
    → Returns 2 * 1 = 2
  → Returns 3 * 2 = 6
→ Returns 4 * 6 = 24

Problem 1: Pow(x, n)

Problem Statement

Implement pow(x, n), which calculates x raised to the power n (i.e., xⁿ).

Understanding the Problem

We need to calculate x raised to the power n efficiently. A naive approach would multiply x by itself n times, which is O(n). We can use recursion to achieve O(log n) by using the property:

xⁿ = (xⁿ/²)² if n is even xⁿ = x × (xⁿ/²)² if n is odd

Solution Strategy

Divide and Conquer with Recursion:

1. Base case: If n == 0, return 1
2. Handle negative exponent: Convert to positive and take reciprocal
3. Recursive case:
   • Calculate xⁿ/² recursively
   • If n is even: return (xⁿ/²)²
   • If n is odd: return x × (xⁿ/²)²

This reduces the problem size by half at each step, achieving O(log n) time complexity.

C# Solution

public class Solution 
{
    public double MyPow(double x, int n) 
    {
        // Base case: any number to the power of 0 is 1
        if (n == 0)
            return 1;
        
        // Handle negative exponent
        if (n < 0)
        {
            // Convert to positive and take reciprocal
            // Using -(n+1) to handle integer overflow edge case
            return (1.0 / x) * MyPow(1.0 / x, -(n + 1));
        }
        
        // Recursive case: calculate x^(n/2)
        double half = MyPow(x, n / 2);
        
        // If n is even: (x^(n/2))^2
        if (n % 2 == 0)
            return half * half;
        
        // If n is odd: x * (x^(n/2))^2
        else
            return x * half * half;
    }
}

Python 3 Solution

class Solution:
    def myPow(self, x: float, n: int) -> float:
        # Base case: any number to the power of 0 is 1
        if not n:
            return 1
        
        # Handle negative exponent
        if n < 0:
            return 1 / self.myPow(x, -n)
        
        # If n is odd: x * x^(n-1)
        if n % 2:
            return x * self.myPow(x, n - 1)
        
        # If n is even: (x^2)^(n/2)
        return self.myPow(x * x, n // 2)

Complexity Analysis

• Time Complexity: O(log n) – we halve the exponent at each step
• Space Complexity: O(log n) – recursion stack depth

Key Insight

The recursive approach uses the mathematical property that xⁿ = (x²)ⁿ/², allowing us to reduce the problem size exponentially rather than linearly.

Problem 2: K-th Symbol in Grammar

Problem Statement

We build a table of n rows (1-indexed). We start by writing 0 in the 1st row. Now in every subsequent row, we look at the previous row and replace each occurrence of 0 with 01, and each occurrence of 1 with 10.

• For example, for n = 3, the 1st row is 0, the 2nd row is 01, and the 3rd row is 0110.

Given two integer n and k, return the k-th (1-indexed) symbol in the n-th row of a table of n rows.

Understanding the Problem

This problem has a recursive structure:

• Row 1: 0
• Row 2: 01 (0 → 01, 1 → 10)
• Row 3: 0110 (0 → 01, 1 → 10, 1 → 10, 0 → 01)
• Row 4: 01101001

Key Observation:

• The k-th symbol in row n depends on the parent symbol in row n-1
• If k is odd, it’s the first symbol of the parent’s transformation
• If k is even, it’s the second symbol of the parent’s transformation
• Parent position: (k + 1) / 2 (ceiling division)

Solution Strategy

Recursive Approach:

1. Base case: If n == 1, return 0 (first row)
2. Find the parent symbol in row n-1 at position (k + 1) / 2
3. Determine if k is odd or even
4. Return based on parent:
   • If parent is 1: return 1 if k is odd, 0 if k is even
   • If parent is 0: return 0 if k is odd, 1 if k is even

C# Solution

public class Solution 
{
    public int KthGrammar(int n, int k) 
    {
        // Base case: first row always starts with 0
        if (n == 1)
            return 0;
        
        // Find parent symbol in previous row
        // Parent position is ceiling of k/2: (k/2 + k%2)
        int parent = KthGrammar(n - 1, (k / 2 + k % 2));
        
        // Determine if k is odd (1-indexed)
        bool isOdd = (k % 2 == 1);
        
        // Transformation rules:
        // 0 → 01 (odd position = 0, even position = 1)
        // 1 → 10 (odd position = 1, even position = 0)
        if (parent == 1)
        {
            return isOdd ? 1 : 0;
        }
        else
        {
            return isOdd ? 0 : 1;
        }
    }
}

Python 3 Solution

class Solution:
    def kthGrammar(self, n: int, k: int) -> int:
        # Base case: first row always starts with 0
        if n == 1:
            return 0
        
        # Find parent symbol in previous row
        # Parent position is ceiling of k/2
        parent = self.kthGrammar(n - 1, (k // 2 + k % 2))
        
        # Determine if k is odd (1-indexed)
        isOdd = (k % 2 == 1)
        
        # Transformation rules:
        # 0 → 01 (odd position = 0, even position = 1)
        # 1 → 10 (odd position = 1, even position = 0)
        if parent == 1:
            return 1 if isOdd else 0
        else:
            return 0 if isOdd else 1

Complexity Analysis

• Time Complexity: O(n) – we recurse n times (once per row)
• Space Complexity: O(n) – recursion stack depth

Key Insight

Instead of building the entire row (which would be exponential in size), we use recursion to trace back to the parent symbol. This allows us to find the k-th symbol without constructing the entire row.

Recursion Patterns

1. Linear Recursion

Each recursive call makes at most one recursive call. Example: Factorial, Fibonacci.

int Factorial(int n) 
{
    if (n <= 1) return 1;
    return n * Factorial(n - 1);  // Single recursive call
}

2. Binary Recursion

Each recursive call makes two recursive calls. Example: Binary tree traversal.

void Inorder(TreeNode root) 
{
    if (root == null) return;
    Inorder(root.left);   // First recursive call
    Process(root);
    Inorder(root.right);  // Second recursive call
}

3. Tail Recursion

The recursive call is the last operation. Can be optimized to iteration.

int FactorialTail(int n, int acc) 
{
    if (n <= 1) return acc;
    return FactorialTail(n - 1, n * acc);  // Tail call
}

4. Divide and Conquer

Problem is divided into smaller subproblems, solved recursively, then combined.

int BinarySearch(int[] arr, int left, int right, int target) 
{
    if (left > right) return -1;
    
    int mid = left + (right - left) / 2;
    
    if (arr[mid] == target) return mid;
    
    // Divide: search left or right half
    if (arr[mid] > target)
        return BinarySearch(arr, left, mid - 1, target);
    else
        return BinarySearch(arr, mid + 1, right, target);
}

Key Takeaways

Recursion Best Practices:

1. Always Define a Base Case Without a base case, recursion will continue infinitely, causing stack overflow.

2. Ensure Progress Toward Base Case Each recursive call should move closer to the base case. Otherwise, infinite recursion occurs.

3. Consider Stack Overflow For deep recursion, consider iterative solutions or tail recursion optimization.

4. Use Memoization for Overlapping Subproblems If the same subproblems are solved multiple times, cache results to avoid redundant calculations.

5. Think About Space Complexity Each recursive call uses stack space. Deep recursion can be memory-intensive.

When to Use Recursion:

• Natural Recursive Structure: Trees, graphs, nested structures
• Divide and Conquer: Problems that can be split into similar subproblems
• Backtracking: Exploring all possibilities
• Mathematical Problems: Problems with recursive definitions
• Simpler Code: When recursive solution is more readable

When to Avoid Recursion:

• Deep Recursion: When recursion depth is very large
• Performance Critical: When iterative solution is significantly faster
• Simple Iteration: When iterative solution is straightforward
• Memory Constraints: When stack space is limited

Converting Recursion to Iteration:

Many recursive problems can be converted to iterative solutions using:

• Stack: Explicitly manage the call stack
• Loop: For tail-recursive functions
• State Variables: Track state instead of using call stack

Common Recursion Mistakes:

• Missing Base Case: Causes infinite recursion
• Not Progressing: Recursive call doesn’t move toward base case
• Stack Overflow: Too deep recursion
• Redundant Calculations: Not using memoization when needed

Conclusion

Recursion is a powerful technique that can make complex problems more elegant and easier to understand. The key is identifying when a problem has a recursive structure and defining clear base cases and recursive cases.

Key patterns to remember:

• Base Case: Always define a stopping condition
• Recursive Case: Break problem into smaller subproblems
• Progress: Ensure each call moves toward the base case
• Optimization: Use memoization for overlapping subproblems

Practice identifying recursive patterns and converting problems into recursive solutions. Start with simple problems like factorial and Fibonacci, then progress to more complex problems like tree traversals and divide-and-conquer algorithms.

Remember: Recursion is a tool, not always the best solution. Consider the trade-offs between recursive and iterative approaches, especially for performance-critical applications.

Happy coding!