How To Solve ANY Recursion Problem - Step By Step Guide Along With Problem Examples
Rochak Vyas
325
RecursionCareerInterview

Recursion broke my brain for months.

The problem was I kept trying to trace every call in my head.
That never works. There is a better way to think about it.

Here is the complete guide.

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
THE CORE IDEA — HOW TO ACTUALLY THINK RECURSIVELY
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Stop trying to trace every call. That kills you.
Instead, ask THREE questions:

  1. WHAT IS THE BASE CASE?
    The simplest input where you know the answer directly.
    (empty array, n == 0, single node, null pointer)

  2. WHAT DOES ONE RECURSIVE CALL DO?
    Assume it works perfectly on a smaller version of the problem.
    This is called the Leap of Faith.

  3. HOW DO I USE THAT RESULT TO SOLVE THE CURRENT PROBLEM?
    Combine the recursive result with the current element.

Answer these three and the code writes itself.

EXAMPLE — Sum of Array

// What is the base? Empty array → sum is 0.
// What does recurse(arr, i+1) do? Returns sum from i+1 to end.
// How do I combine? Add arr[i] to that sum.

int sum(vector<int>& arr, int i) {
    if (i == arr.size()) return 0;       // base case
    return arr[i] + sum(arr, i + 1);    // trust + combine
}

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
THERE ARE 3 TYPES OF RECURSION ON LEETCODE
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

TYPE 1 — LINEAR RECURSION → one call per level (arrays, linked lists)
TYPE 2 — TREE RECURSION → two or more calls per level (binary trees)
TYPE 3 — DIVIDE & CONQUER → split in half, solve each, merge results

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
TYPE 1 — LINEAR RECURSION
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

When to use:
→ Process one element, then recurse on the rest
→ Works on arrays, strings, and linked lists

Pattern: solve(n) uses solve(n-1) or solve(rest of list)

There are two sub-patterns based on WHERE the work happens:

HEAD RECURSION — do the work BEFORE the recursive call.
Process current element first, then recurse.
Result: works in forward order.

void printForward(ListNode* node) {
    if (!node) return;
    cout << node->val;       // work first
    printForward(node->next);
}

TAIL RECURSION — do the work AFTER the recursive call returns.
Recurse first, then process current element on the way back up.
Result: works in reverse order.

void printReverse(ListNode* node) {
    if (!node) return;
    printReverse(node->next);
    cout << node->val;       // work after
}

This difference — before or after — is the key insight for many problems.

EXAMPLE — Reverse a String
https://leetcode.com/problems/reverse-string

Swap the outermost characters, then recurse on the inner part.

void reverseString(vector<char>& s, int l, int r) {
    if (l >= r) return;
    swap(s[l], s[r]);
    reverseString(s, l + 1, r - 1);
}

EXAMPLE — Power(x, n)
https://leetcode.com/problems/powx-n

x^n = x * x^(n-1) → but that is O(n).
Better: x^n = x^(n/2) * x^(n/2) → O(log n).
One recursive call does half the work.

double myPow(double x, long long n) {
    if (n == 0) return 1;
    if (n < 0)  return 1.0 / myPow(x, -n);
    double half = myPow(x, n / 2);
    if (n % 2 == 0) return half * half;
    else return half * half * x;
}

EXAMPLE — Swap Nodes in Pairs
https://leetcode.com/problems/swap-nodes-in-pairs

Swap the first two nodes. Then recursively fix the rest.
Assume swapPairs(node->next->next) correctly fixes everything after.

ListNode* swapPairs(ListNode* head) {
    if (!head || !head->next) return head;    // base case
    ListNode* second = head->next;
    head->next = swapPairs(second->next);     // trust the recursion
    second->next = head;
    return second;
}

EXAMPLE — Reverse Linked List (recursive)
https://leetcode.com/problems/reverse-linked-list

Assume reverseList(head->next) reverses the rest of the list.
The head of the reversed list is the last node.
You just need to append head to the tail of the reversed list.

ListNode* reverseList(ListNode* head) {
    if (!head || !head->next) return head;
    ListNode* newHead = reverseList(head->next);
    head->next->next = head;   // attach head to the back
    head->next = nullptr;
    return newHead;
}

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
TYPE 2 — TREE RECURSION
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

When to use:
→ Almost every binary tree problem
→ Two or more recursive calls at each level
→ The answer depends on results from BOTH subtrees

Pattern: solve(node) = combine(solve(node->left), solve(node->right))

Most tree problems are solved by asking one question:
"What do I need from each subtree to compute the answer at this node?"

TEMPLATE:

ReturnType solve(TreeNode* node) {
    if (!node) return <base value>;   // null node

    auto left  = solve(node->left);   // get answer from left subtree
    auto right = solve(node->right);  // get answer from right subtree

    return <combine left, right, and node->val>;
}

EXAMPLE — Maximum Depth of Binary Tree
https://leetcode.com/problems/maximum-depth-of-binary-tree

Depth at null = 0.
Depth at node = 1 + max(depth of left, depth of right).

int maxDepth(TreeNode* root) {
    if (!root) return 0;
    return 1 + max(maxDepth(root->left), maxDepth(root->right));
}

EXAMPLE — Invert Binary Tree
https://leetcode.com/problems/invert-binary-tree

Invert left subtree. Invert right subtree. Then swap them.

TreeNode* invertTree(TreeNode* root) {
    if (!root) return nullptr;
    TreeNode* left  = invertTree(root->left);
    TreeNode* right = invertTree(root->right);
    root->left  = right;
    root->right = left;
    return root;
}

EXAMPLE — Diameter of Binary Tree
https://leetcode.com/problems/diameter-of-binary-tree

Diameter at each node = height(left) + height(right).
But the widest diameter might not pass through the root.
Track the global max while computing heights recursively.

int ans = 0;

int height(TreeNode* node) {
    if (!node) return 0;
    int l = height(node->left);
    int r = height(node->right);
    ans = max(ans, l + r);   // update diameter at this node
    return 1 + max(l, r);   // return height to parent
}

EXAMPLE — Path Sum II
https://leetcode.com/problems/path-sum-ii

At each node, subtract its value from the remaining target.
At a leaf, check if remaining == 0.
This is tree recursion with a running state passed down.

void dfs(TreeNode* node, int remaining, vector<int>& path,
         vector<vector<int>>& res) {
    if (!node) return;
    path.push_back(node->val);
    if (!node->left && !node->right && remaining == node->val)
        res.push_back(path);
    dfs(node->left,  remaining - node->val, path, res);
    dfs(node->right, remaining - node->val, path, res);
    path.pop_back();
}

EXAMPLE — Lowest Common Ancestor of BST
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree

If both p and q are smaller than root → LCA is in left subtree.
If both are larger → LCA is in right subtree.
Otherwise root is the LCA.

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (p->val < root->val && q->val < root->val)
        return lowestCommonAncestor(root->left, p, q);
    if (p->val > root->val && q->val > root->val)
        return lowestCommonAncestor(root->right, p, q);
    return root;
}

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
TYPE 3 — DIVIDE AND CONQUER
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

When to use:
→ Problem can be split into two independent halves
→ Solve each half, then merge the results
→ Works on arrays where mid-split makes sense

Pattern:

  1. Split: divide the problem at the midpoint
  2. Conquer: solve left half and right half recursively
  3. Merge: combine the two results

TEMPLATE:

ReturnType solve(array, lo, hi) {
    if (lo == hi) return <base answer for single element>;

    int mid = lo + (hi - lo) / 2;
    auto left  = solve(array, lo, mid);
    auto right = solve(array, mid+1, hi);
    return merge(left, right);
}

EXAMPLE — Sort an Array (Merge Sort)
https://leetcode.com/problems/sort-an-array

Split in half. Sort each half. Merge the two sorted halves.

void mergeSort(vector<int>& nums, int lo, int hi) {
    if (lo >= hi) return;
    int mid = lo + (hi - lo) / 2;
    mergeSort(nums, lo, mid);
    mergeSort(nums, mid+1, hi);
    merge(nums, lo, mid, hi);   // standard merge of two sorted halves
}

EXAMPLE — Maximum Subarray
https://leetcode.com/problems/maximum-subarray

Divide at mid. Max subarray is either:
- Entirely in the left half
- Entirely in the right half
- Crossing the midpoint (extends left from mid AND right from mid+1)

int maxCrossing(vector<int>& nums, int lo, int mid, int hi) {
      int leftMax = INT_MIN, sum = 0;
      for (int i = mid; i >= lo; i--) {
          sum += nums[i];
          leftMax = max(leftMax, sum);
      }
      int rightMax = INT_MIN; sum = 0;
      for (int i = mid+1; i <= hi; i++) {
          sum += nums[i];
          rightMax = max(rightMax, sum);
      }
      return leftMax + rightMax;
  }


  
int solve(vector<int>& nums, int lo, int hi) {
      if (lo == hi) return nums[lo];
      int mid = lo + (hi - lo) / 2;
      return max({solve(nums, lo, mid),
                  solve(nums, mid+1, hi),
                  maxCrossing(nums, lo, mid, hi)});
  }

EXAMPLE — Majority Element
https://leetcode.com/problems/majority-element

Majority element of the full array must be the majority in
at least one half. Find majority of each half, return the one
that appears more in the current range.

int majority(vector<int>& nums, int lo, int hi) {
    if (lo == hi) return nums[lo];
    int mid = lo + (hi - lo) / 2;
    int left  = majority(nums, lo, mid);
    int right = majority(nums, mid+1, hi);
    if (left == right) return left;
    int lCount = count(nums.begin()+lo, nums.begin()+hi+1, left);
    int rCount = count(nums.begin()+lo, nums.begin()+hi+1, right);
    return lCount > rCount ? left : right;
}

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
HOW TO IDENTIFY WHICH TYPE — DECISION GUIDE
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Read the problem. Ask these questions in order:

Is the input a binary tree?
→ YES → Type 2 (Tree Recursion)
Ask: "what do I need from each child to answer at this node?"

Can the problem be split at a midpoint into two independent halves?
→ YES → Type 3 (Divide and Conquer)

Is it processing a list/string one element at a time?
→ YES → Type 1 (Linear Recursion)
Ask: do I need to go forward (head) or backward (tail)?

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
COMMON MISTAKES AND HOW TO AVOID THEM
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

  • MISTAKE 1 — Trying to trace every recursive call in your head
    You will always get lost beyond 3-4 levels.
    Instead: trust the leap of faith. Assume the call on the smaller
    input works correctly. Your only job is the current level.

  • MISTAKE 2 — Missing or wrong base case
    No base case = infinite recursion = stack overflow.
    Always handle: null, empty, n == 0, single element.
    Test your base case manually before worrying about the rest.

  • MISTAKE 3 — Base case that is too general
    If base case swallows inputs it should not handle,
    you return the wrong answer for those.
    Be precise: if (!root) not if (root == someSpecificNode).

  • MISTAKE 4 — Returning too early (missing the combine step)
    You recurse into both subtrees but forget to merge.
    Return the combined result, not just the left or right alone.

  • MISTAKE 5 — Not thinking about what the function returns
    Before writing code, decide: does this function return a value?
    Or does it modify a global/reference variable?
    Both are valid. Mixing them up silently gives wrong answers.

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
PRACTICE PROBLEMS — IN ORDER
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
THE RECURSION CHEAT SHEET — ONE LINE EACH
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Every recursion → base case + trust the smaller call
Work before recursive call → head recursion (forward order)
Work after recursive call → tail recursion (reverse order)
Binary tree → combine answers from left and right child
Global max across tree → update global in the recursion, return height
Divide and conquer → split at mid, solve each half, merge
Linked list reversal → recurse to end, fix pointers coming back up

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Drop a comment if anything is unclear.
I will write a dedicated post on any type you want.

Comments (2)