Recursion & Backtracking

Day 16 - Python Interview Series

📚 Introduction to Recursion

Recursion is a programming technique where a function calls itself to solve a problem by breaking it down into smaller, similar subproblems. It's like looking into two mirrors facing each other - you see an infinite reflection, but each reflection is smaller than the previous one.

🎯 Base Case

The condition that stops the recursion. Without it, the function would call itself infinitely, causing a stack overflow.

🔄 Recursive Case

The part where the function calls itself with modified parameters, moving closer to the base case.

📚 Call Stack

Memory structure that keeps track of function calls. Each recursive call adds a new frame to the stack.

🧠 Stack Memory

Limited memory space for function calls. Deep recursion can cause stack overflow if memory is exhausted.

💡 Recursion Examples

Example 1: Factorial Function

Python - Factorial Calculation
def factorial(n):
    # Base case: factorial of 0 or 1 is 1
    if n <= 1:
        return 1
    
    # Recursive case: n! = n * (n-1)!
    return n * factorial(n - 1)

# Example usage
print(factorial(5))  # Output: 120
print(factorial(0))  # Output: 1

# Call stack visualization for factorial(3):
# factorial(3) → 3 * factorial(2)
# factorial(2) → 2 * factorial(1)
# factorial(1) → 1 (base case)
# Result: 3 * 2 * 1 = 6

Example 2: Fibonacci Sequence

Python - Fibonacci Numbers
def fibonacci(n):
    # Base cases
    if n <= 0:
        return 0
    elif n == 1:
        return 1
    
    # Recursive case: F(n) = F(n-1) + F(n-2)
    return fibonacci(n - 1) + fibonacci(n - 2)

# Optimized version with memoization
def fibonacci_memo(n, memo={}):
    if n in memo:
        return memo[n]
    
    if n <= 0:
        return 0
    elif n == 1:
        return 1
    
    memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
    return memo[n]

# Example usage
print(fibonacci(6))     # Output: 8
print(fibonacci_memo(10))  # Output: 55
⚠️ Performance Note: The naive fibonacci function has exponential time complexity O(2^n). Always consider using memoization or iterative approaches for better performance in interviews.

🔙 Introduction to Backtracking

Backtracking is an algorithmic approach that considers searching every possible combination in order to solve computational problems. It builds solutions incrementally and abandons candidates ("backtracks") when they cannot possibly lead to a valid solution.

🔄 Backtracking Algorithm Steps:

  1. Choose: Make a choice from available options
  2. Explore: Recursively explore the consequences of that choice
  3. Unchoose: If the choice doesn't lead to a solution, backtrack (undo the choice)
  4. Repeat: Try the next available choice
💡 When to Use Backtracking: Perfect for constraint satisfaction problems, finding all solutions, optimization problems where you need to explore all possibilities (Sudoku, N-Queens, permutations, combinations).

👑 Backtracking Example: N-Queens Problem

The N-Queens problem asks: "How can you place N chess queens on an N×N chessboard so that no two queens threaten each other?"

Python - N-Queens Solution
def solve_n_queens(n):
    # Initialize the board
    board = [['.' for _ in range(n)] for _ in range(n)]
    solutions = []
    
    def is_safe(row, col):
        # Check column
        for i in range(row):
            if board[i][col] == 'Q':
                return False
        
        # Check diagonal (top-left to bottom-right)
        i, j = row - 1, col - 1
        while i >= 0 and j >= 0:
            if board[i][j] == 'Q':
                return False
            i -= 1
            j -= 1
        
        # Check diagonal (top-right to bottom-left)
        i, j = row - 1, col + 1
        while i >= 0 and j < n:
            if board[i][j] == 'Q':
                return False
            i -= 1
            j += 1
        
        return True
    
    def backtrack(row):
        # Base case: all queens placed successfully
        if row == n:
            solution = [''.join(row) for row in board]
            solutions.append(solution)
            return
        
        # Try placing queen in each column of current row
        for col in range(n):
            if is_safe(row, col):
                # Choose: place queen
                board[row][col] = 'Q'
                
                # Explore: recurse to next row
                backtrack(row + 1)
                
                # Unchoose: backtrack
                board[row][col] = '.'
    
    backtrack(0)
    return solutions

# Example usage
solutions = solve_n_queens(4)
print(f"Found {len(solutions)} solutions for 4-Queens:")
for i, solution in enumerate(solutions):
    print(f"\nSolution {i + 1}:")
    for row in solution:
        print(row)

🧩 How N-Queens Backtracking Works:

Step-by-Step Process:

  1. Start with empty board: Begin at row 0
  2. Place queen: Try placing a queen in each column of current row
  3. Check safety: Verify no conflicts with previously placed queens
  4. Recurse: If safe, move to next row and repeat
  5. Backtrack: If no safe position found, remove last queen and try next column
  6. Solution found: When all N queens are placed safely

🎯 Key Recursion Patterns

Common Recursion Patterns
# 1. Linear Recursion (like factorial)
def linear_recursion(n):
    if n <= 0:  # Base case
        return 1
    return n * linear_recursion(n - 1)

# 2. Binary Recursion (like fibonacci)
def binary_recursion(n):
    if n <= 1:  # Base case
        return n
    return binary_recursion(n - 1) + binary_recursion(n - 2)

# 3. Tail Recursion (optimizable)
def tail_factorial(n, acc=1):
    if n <= 1:
        return acc
    return tail_factorial(n - 1, n * acc)

# 4. Tree Recursion (like tree traversal)
def tree_sum(node):
    if node is None:
        return 0
    return node.val + tree_sum(node.left) + tree_sum(node.right)

🎤 Top 10 Interview Questions: Recursion & Backtracking

Implement a function to calculate the power of a number using recursion Easy
Find all permutations of a given string using backtracking Medium
Solve the classic Tower of Hanoi problem recursively Medium
Generate all possible combinations of parentheses for n pairs Medium
Implement binary search using recursion Easy
Solve Sudoku puzzle using backtracking algorithm Hard
Find all paths from top-left to bottom-right in a matrix Medium
Implement subset sum problem using recursion Medium
Generate all possible letter combinations of a phone number Medium
Solve the Word Search problem using backtracking Hard

🚀 Pro Tips for Interviews

🎯 Always Define Base Case First

Start by identifying and implementing the base case. This prevents infinite recursion and makes your logic clearer.

📊 Consider Time & Space Complexity

Recursion uses O(n) space due to call stack. Some problems might need iterative solutions for better space efficiency.

🧠 Use Memoization

Cache results of expensive recursive calls to avoid redundant computations and improve performance significantly.

🔍 Trace Through Examples

Walk through your recursive function with small examples to verify correctness before coding complex cases.

🎯 Interview Strategy: When solving recursion problems, always explain your base case, recursive relationship, and time/space complexity. Draw the recursion tree for complex problems to visualize the solution.
🚀 Powered by Shaivi Connect