Menu

Earn Premium with Referrals

Invite your friends and earn Premium rewards through our referral program.

See how it works and start inviting friends.

Recursion Revision
DSA

Recursion Revision

Quickly revise recursive thinking, base cases, recursive cases, and call-stack behavior.

function solve(index, path):
    if index == n:
        add path to result
        return

    // choice 1: include
    add arr[index] to path
    solve(index + 1, path)
    remove last element

    // choice 2: exclude
    solve(index + 1, path)

Input: Array / string Core Idea: At each index → pick or skip Time: O(2^n)

public void subsets(int[] nums, int index, List<Integer> path, List<List<Integer>> res) {
    if (index == nums.length) {
        res.add(new ArrayList<>(path));
        return;
    }

    // include
    path.add(nums[index]);
    subsets(nums, index + 1, path, res);
    path.remove(path.size() - 1);

    // exclude
    subsets(nums, index + 1, path, res);
}
def subsets(nums, index, path, res):
    if index == len(nums):
        res.append(path[:])
        return

    # include
    path.append(nums[index])
    subsets(nums, index + 1, path, res)
    path.pop()

    # exclude
    subsets(nums, index + 1, path, res)
void subsets(vector<int>& nums, int index, vector<int>& path, vector<vector<int>>& res) {
    if (index == nums.size()) {
        res.push_back(path);
        return;
    }

    // include
    path.push_back(nums[index]);
    subsets(nums, index + 1, path, res);
    path.pop_back();

    // exclude
    subsets(nums, index + 1, path, res);
}
function subsets(nums, index, path, res) {
    if (index === nums.length) {
        res.push([...path]);
        return;
    }

    // include
    path.push(nums[index]);
    subsets(nums, index + 1, path, res);
    path.pop();

    // exclude
    subsets(nums, index + 1, path, res);
}

2 Divide & Conquer Recursion

function solve(l, r):
    if l >= r:
        return base_value

    mid = (l + r) / 2

    left = solve(l, mid)
    right = solve(mid+1, r)

    return combine(left, right)

Input: Array / range Core Idea: Split → solve → merge Examples: Merge Sort, Binary Search

public void mergeSort(int[] arr, int l, int r) {
    if (l >= r) return;

    int mid = (l + r) / 2;

    mergeSort(arr, l, mid);
    mergeSort(arr, mid + 1, r);

    merge(arr, l, mid, r);
}
def merge_sort(arr, l, r):
    if l >= r:
        return

    mid = (l + r) // 2

    merge_sort(arr, l, mid)
    merge_sort(arr, mid + 1, r)

    merge(arr, l, mid, r)
void mergeSort(vector<int>& arr, int l, int r) {
    if (l >= r) return;

    int mid = (l + r) / 2;

    mergeSort(arr, l, mid);
    mergeSort(arr, mid + 1, r);

    merge(arr, l, mid, r);
}
function mergeSort(arr, l, r) {
    if (l >= r) return;

    const mid = Math.floor((l + r) / 2);

    mergeSort(arr, l, mid);
    mergeSort(arr, mid + 1, r);

    merge(arr, l, mid, r);
}

3 Tree Recursion (Binary / N-ary Trees)

function dfs(node):
    if node == null:
        return base

    left = dfs(node.left)
    right = dfs(node.right)

    return combine(left, right)

Input: Tree structure Core Idea: Node → left + right recursion Used in: Height, diameter, LCA

class TreeNode {
    int val;
    TreeNode left, right;
}

public int height(TreeNode root) {
    if (root == null) return 0;

    int left = height(root.left);
    int right = height(root.right);

    return 1 + Math.max(left, right);
}
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def height(root):
    if root is None:
        return 0

    left = height(root.left)
    right = height(root.right)

    return 1 + max(left, right)
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
};

int height(TreeNode* root) {
    if (root == nullptr) return 0;

    int left = height(root->left);
    int right = height(root->right);

    return 1 + max(left, right);
}
class TreeNode {
    constructor(val = 0, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function height(root) {
    if (root === null) return 0;

    const left = height(root.left);
    const right = height(root.right);

    return 1 + Math.max(left, right);
}

4 DFS Recursion (Graphs / Grid)

function dfs(node):
    mark visited

    for neighbor in node:
        if not visited:
            dfs(neighbor)

Input: Graph / Matrix Core Idea: Explore all connected nodes Used in: Islands, Flood Fill

public void dfs(int[][] grid, int i, int j, boolean[][] vis) {
    if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length)
        return;

    if (vis[i][j] || grid[i][j] == 0)
        return;

    vis[i][j] = true;

    dfs(grid, i+1, j, vis);
    dfs(grid, i-1, j, vis);
    dfs(grid, i, j+1, vis);
    dfs(grid, i, j-1, vis);
}
def dfs(grid, i, j, vis):
    if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]):
        return

    if vis[i][j] or grid[i][j] == 0:
        return

    vis[i][j] = True

    dfs(grid, i + 1, j, vis)
    dfs(grid, i - 1, j, vis)
    dfs(grid, i, j + 1, vis)
    dfs(grid, i, j - 1, vis)
void dfs(vector<vector<int>>& grid, int i, int j, vector<vector<bool>>& vis) {
    if (i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size())
        return;

    if (vis[i][j] || grid[i][j] == 0)
        return;

    vis[i][j] = true;

    dfs(grid, i + 1, j, vis);
    dfs(grid, i - 1, j, vis);
    dfs(grid, i, j + 1, vis);
    dfs(grid, i, j - 1, vis);
}
function dfs(grid, i, j, vis) {
    if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length)
        return;

    if (vis[i][j] || grid[i][j] === 0)
        return;

    vis[i][j] = true;

    dfs(grid, i + 1, j, vis);
    dfs(grid, i - 1, j, vis);
    dfs(grid, i, j + 1, vis);
    dfs(grid, i, j - 1, vis);
}

5 String Recursion (Partition / Split Problems)

function solve(start):
    if start == n:
        add result
        return

    for end from start to n:
        substring = s[start:end]
        solve(end + 1)

Input: String Core Idea: Split at every position Used in: Palindrome partitioning, IP restore

public void partition(String s, int start, List<String> path, List<List<String>> res) {
    if (start == s.length()) {
        res.add(new ArrayList<>(path));
        return;
    }

    for (int end = start; end < s.length(); end++) {
        String part = s.substring(start, end + 1);

        path.add(part);
        partition(s, end + 1, path, res);
        path.remove(path.size() - 1);
    }
}
def partition(s, start, path, res):
    if start == len(s):
        res.append(path[:])
        return

    for end in range(start, len(s)):
        part = s[start:end + 1]

        path.append(part)
        partition(s, end + 1, path, res)
        path.pop()
void partition(string& s, int start, vector<string>& path, vector<vector<string>>& res) {
    if (start == s.size()) {
        res.push_back(path);
        return;
    }

    for (int end = start; end < s.size(); end++) {
        string part = s.substr(start, end - start + 1);

        path.push_back(part);
        partition(s, end + 1, path, res);
        path.pop_back();
    }
}
function partition(s, start, path, res) {
    if (start === s.length) {
        res.push([...path]);
        return;
    }

    for (let end = start; end < s.length; end++) {
        const part = s.slice(start, end + 1);

        path.push(part);
        partition(s, end + 1, path, res);
        path.pop();
    }
}

6 Optimization Recursion (Min / Max Problems)

function solve(state):
    if base_case:
        return value

    result = worst/best_init

    for each choice:
        result = min/max(result, solve(new_state))

    return result

Input: Array / graph / DP state Core Idea: Try all paths → return best Used in: Knapsack, Min path, Coin change

public int minPath(int[][] grid, int i, int j) {
    if (i == 0 && j == 0) return grid[i][j];
    if (i < 0 || j < 0) return Integer.MAX_VALUE;

    int up = minPath(grid, i - 1, j);
    int left = minPath(grid, i, j - 1);

    return grid[i][j] + Math.min(up, left);
}
def min_path(grid, i, j):
    if i == 0 and j == 0:
        return grid[i][j]
    if i < 0 or j < 0:
        return float('inf')

    up = min_path(grid, i - 1, j)
    left = min_path(grid, i, j - 1)

    return grid[i][j] + min(up, left)
int minPath(vector<vector<int>>& grid, int i, int j) {
    if (i == 0 && j == 0) return grid[i][j];
    if (i < 0 || j < 0) return INT_MAX;

    int up = minPath(grid, i - 1, j);
    int left = minPath(grid, i, j - 1);

    return grid[i][j] + min(up, left);
}
function minPath(grid, i, j) {
    if (i === 0 && j === 0) return grid[i][j];
    if (i < 0 || j < 0) return Infinity;

    const up = minPath(grid, i - 1, j);
    const left = minPath(grid, i, j - 1);

    return grid[i][j] + Math.min(up, left);
}

My Private Notes

Notes are auto-saved locally to this device.