Recursion & Backtracking

Solving Problems by Solving Smaller Selves

Recursion is a fundamental problem-solving technique where a function calls itself to solve a smaller version of the same problem. Backtracking is a refined form of recursion that builds a solution incrementally and abandons paths ("backtracks") as soon as it determines they cannot lead to a valid solution.

1. Understanding Recursion

Every recursive algorithm has two essential components:

Base Case: A condition that stops the recursion. It represents the simplest possible version of the problem that can be solved directly.
Recursive Step: The part of the function that breaks the problem down and calls itself with a modified input that moves it closer to the base case.

The Call Stack

Recursion is managed by the "call stack". When a function is called, a "stack frame" containing its local variables and parameters is pushed onto the stack. When it calls itself, a new frame is pushed on top. The stack unwinds as functions return, popping frames off the top.

Call Stack for factorial(3)

main() calls factorial(3)

factorial(3) calls factorial(2)

factorial(2) calls factorial(1)

factorial(1) is base case, returns 1

factorial(2) returns 2 * 1 = 2

factorial(3) returns 3 * 2 = 6

2. Backtracking

Backtracking is an algorithmic technique for solving problems by exploring all possible candidates and discarding those that do not satisfy the problem's constraints. It uses a "brute-force" approach but intelligently prunes the search space.

The "Choose, Explore, Un-choose" Template

Most backtracking problems can be solved with a standard template:

Choose: Make a choice from a set of possibilities. Add this choice to the current solution path.
Explore: Recursively call the function to explore further possibilities based on the current choice.
Un-choose (Backtrack): Once the recursive call returns, undo the choice you made so it doesn't affect other paths in the search.

Decision Tree for Permutations of [A, B]

Start

Choose A

Path: [A]

Choose B

Found: [A,B]

Choose B

Path: [B]

Choose A

Found: [B,A]

Classic Problems

Classic Problem: Subsets

Given a set of distinct integers, nums, return all possible subsets (the power set). This is a perfect example of the "choose/don't choose" backtracking pattern.

from typing import List

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        result = []
        path = []

        def backtrack(start_index):
            # Add the current subset combination to the result
            result.append(list(path))

            for i in range(start_index, len(nums)):
                # Choose: Add the element to the current path
                path.append(nums[i])
                # Explore: Recurse with the next index
                backtrack(i + 1)
                # Un-choose: Remove the element to backtrack
                path.pop()
        
        backtrack(0)
        return result

Classic Problem: Permutations

Given a collection of distinct integers, return all possible permutations. This involves swapping elements and ensuring we don't reuse an element in the same path.

from typing import List

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        result = []
        def backtrack(start_index):
            if start_index == len(nums):
                result.append(list(nums))
                return
            
            for i in range(start_index, len(nums)):
                # Choose: Swap the current element with the start element
                nums[start_index], nums[i] = nums[i], nums[start_index]
                # Explore
                backtrack(start_index + 1)
                # Un-choose: Swap back to restore the original state for other paths
                nums[start_index], nums[i] = nums[i], nums[start_index]

        backtrack(0)
        return result

Classic Problem: N-Queens

The N-Queens puzzle is the problem of placing N chess queens on an N×N chessboard so that no two queens threaten each other. This is a classic backtracking problem where we place queens row by row and check for validity before proceeding.

from typing import List

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        col = set()
        posDiag = set() # (r + c)
        negDiag = set() # (r - c)
        res = []
        board = [["."] * n for _ in range(n)]

        def backtrack(r):
            if r == n:
                res.append(["".join(row) for row in board])
                return

            for c in range(n):
                if c in col or (r + c) in posDiag or (r - c) in negDiag:
                    continue

                # Choose
                col.add(c)
                posDiag.add(r + c)
                negDiag.add(r - c)
                board[r][c] = "Q"

                # Explore
                backtrack(r + 1)

                # Un-choose
                col.remove(c)
                posDiag.remove(r + c)
                negDiag.remove(r - c)
                board[r][c] = "."

        backtrack(0)
        return res

Interactive Recursion (Fibonacci)

Visualize the recursive call tree for the Fibonacci sequence. The animation shows how `fib(n)` calls `fib(n-1)` first, completes that entire branch, and then calls `fib(n-2)`. Use the zoom controls and scrollbars to explore the tree.

Enter n (0-6)

Animation Speed

Enter a number and click Visualize.