Module 3: Recursion & Backtracking

Recursion and Backtracking form the foundation of advanced problem solving.
This module trains the mind to break problems into smaller decisions, explore multiple possibilities, and systematically build correct solutions.

Most learners fear recursion not because it is difficult, but because they don’t visualize it correctly. This module fixes that gap.

Recursion Tree & Stack

What is a Recursion Tree?

A recursion tree visually represents how recursive calls branch and execute.

Each node represents:

• A function call
• A state of variables

What is the Call Stack?

The call stack stores:

• Function parameters
• Local variables
• Return addresses

Each recursive call occupies a new stack frame.

Example: Factorial

int fact(int n){
    if(n == 0) return 1;
    return n * fact(n - 1);
}

Call sequence:

• fact(3)
• fact(2)
• fact(1)
• fact(0)

Stack grows until base case, then unwinds.

Key Insight

Understanding recursion is about visualizing stack growth and collapse, not memorizing code.

Tail Recursion

What is Tail Recursion?

A recursive function is tail recursive if the recursive call is the last operation.

Example:

int factTail(int n, int result){
    if(n == 0) return result;
    return factTail(n - 1, n * result);
}

Why Tail Recursion Matters

• Easier to convert to iteration
• Some languages optimize it
• Reduces stack usage (conceptually)

Java does not optimize tail recursion automatically, but understanding it improves logic clarity.

Parameterized vs Functional Recursion

Parameterized Recursion

The result is passed through parameters.

Example:

void sum(int i, int total){
    if(i == 0){
        System.out.println(total);
        return;
    }
    sum(i - 1, total + i);
}

Functional Recursion

The function returns the result.

Example:

int sum(int n){
    if(n == 0) return 0;
    return n + sum(n - 1);
}

When to Use Which

• Parameterized recursion is useful when you don’t need return values
• Functional recursion is cleaner for mathematical problems

Recursion vs Iteration

Recursion

• Elegant
• Mirrors mathematical definitions
• Uses stack memory

Iteration

• More memory-efficient
• Faster in most cases
• Less risk of stack overflow

Example comparison:

Recursive:

int fib(int n){
    if(n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

Iterative:

int a = 0, b = 1;
for(int i = 2; i <= n; i++){
    int c = a + b;
    a = b;
    b = c;
}

Interview Rule

Understand recursion deeply, but optimize with iteration when required.

Backtracking Fundamentals

What is Backtracking?

Backtracking is a technique where:

• You try a choice
• Explore further
• Undo the choice if it fails

It is recursion with decision-making.

Backtracking Template

void solve(state){
    if(baseCondition) return;

    for(choice : allChoices){
        makeChoice;
        solve(updatedState);
        undoChoice;
    }
}

Used in:

• Constraint problems
• Search problems
• Combinatorial problems

Subsets & Subsequences

Subsets

All possible selections of elements (order doesn’t matter).

Example:

void subsets(int index, List<Integer> current){
    if(index == n){
        print(current);
        return;
    }

    current.add(arr[index]);
    subsets(index + 1, current);

    current.remove(current.size() - 1);
    subsets(index + 1, current);
}

Total subsets: 2ⁿ

Subsequences

Same as subsets but often discussed in sequence context.

Key idea: pick or not pick

Permutations & Combinations

Permutations

Order matters.

Example:

void permute(int index){
    if(index == n){
        print(arr);
        return;
    }

    for(int i = index; i < n; i++){
        swap(index, i);
        permute(index + 1);
        swap(index, i);
    }
}

Time Complexity: O(n!)

Combinations

Order does not matter.

Example idea:

• Choose element
• Move forward
• Avoid revisiting

Used in:

• Team selection
• Coin problems
• Constraint problems

N-Queens Problem

Problem Statement

Place N queens on an N×N chessboard such that:

• No two queens share the same row, column, or diagonal

Approach

• Place one queen per row
• Check column and diagonals
• Backtrack if conflict

Core logic:

if(isSafe(row, col)){
    board[row][col] = 'Q';
    solve(row + 1);
    board[row][col] = '.';
}

This problem teaches:

• Constraint checking
• State management
• Backtracking depth control

Sudoku Solver

Problem Idea

Fill a 9×9 board so that:

• Each row has digits 1–9
• Each column has digits 1–9
• Each 3×3 grid has digits 1–9

Approach

• Find empty cell
• Try digits 1–9
• Check validity
• Backtrack if invalid

This problem simulates real-world constraint solving.

Rat in a Maze

Problem Statement

Given a grid with blocked and open cells, find a path from source to destination.

Approach

• Move in allowed directions
• Mark visited
• Backtrack on dead ends

Key learning:

• Path exploration
• Direction arrays
• Visited tracking

Word Search

Problem Statement

Given a grid of characters and a word, check if the word exists in the grid.

Rules:

• Adjacent cells only
• No reuse of same cell

Approach

• DFS + Backtracking
• Match characters sequentially
• Backtrack on mismatch

Used heavily in interviews and online judges.