Essential Recursive Algorithms and Backtracking Techniques

Posted on Nov 8, 2025 in Computers

1) Factorial of n

Question


Compute n!.

Explain question


Return the product 1 * 2 * ... * n. The problem is naturally defined in terms of a smaller n.

Approach (in-depth)


If n is 0 (or 1) the answer is 1. Otherwise the factorial of n = n * factorial(n-1). The recursion reduces n by 1 on every call until the base case. No branching — just a single recursive call. This is linear recursion.

Recurrence relation


fact(n) = n * fact(n-1), with fact(0)=1.

Pseudocode

function fact(n):
    if n == 0: return 1return n * fact(n-1)

2) Print numbers from 1 to n (increasing)

Question


Print 1 2 ... N using recursion.

Explain question


You must produce an ordered sequence; recursion controls order by when you print relative to the recursive call.

Approach (in-depth)


If n == 0 stop. For increasing order: first recurse to print 1..(n-1), then print n. So recursion builds a stack of calls down to 0; printing happens during stack unwinding. For decreasing order, print before recursing.

Recurrence relation


printUp(n) : printUp(n-1); print n with base printUp(0) → no-op.

Pseudocode

function printUp(n):
    if n == 0: 
return    printUp(n-1)
    print(n)

3) Print numbers from n to 1 (decreasing)

Question


Print n (n-1) ... 1 with recursion.

Explain question


Similar to above but reverse order — print first, recurse next.

Approach (in-depth)


If n == 0 stop. Print n first, then call printDown(n-1). This prints the current number before deeper calls.

Recurrence relation


printDown(n) : print n; printDown(n-1).

Pseudocode

function printDown(n):
    if n == 0: returnprint(n)
    printDown(n-1)

4) Reverse a string using recursion

Question


Return the reverse of string s recursively.

Explain question


Reverse is defined by taking first char and placing it at the end of the reversed remainder.

Approach (in-depth)


Base case: empty or length 1 returns itself. Recursive step: reverse(s) = reverse(s[1:]) + s[0]. Note: naive substring-based implementation costs O(n²) due to string concatenation; for performance use a char[] and two-pointer swaps via recursion (swap left and right indices and recurse inward).

Recurrence relation


rev(s[0..N-1]) = rev(s[1..N-1]) + s[0]; base rev("") = "".

Pseudocode (simple)


function reverse(s):
    if length(s) <= 1: return s
    return reverse(s[1:]) + s[0]

Pseudocode (efficient in-place style)

function reverseChars(arr, L, R):
    if L >= R: return    swap arr[L], arr[R]
    reverseChars(arr, L+1, R-1)

5) Check if an array is sorted (recursive)

Question


Return true if array A is strictly increasing.

Explain question


Check that every consecutive pair satisfies A[i] <= A[i+1]. Recursively reduce the array by one index.

Approach (in-depth)
Use an index i. Base case: i >= n-1 → true. At each step, compare A[i] and A[i+1]; if A[i] > A[i+1] return false; else recurse with i+1. This allows short-circuiting on first violation.

Recurrence relation


isSorted(i) = (A[i] <= A[i+1]) AND isSorted(i+1); base at i = n-1 → true.

Pseudocode

function isSorted(A, i):
    if i >= len(A)-1: return trueif A[i] > A[i+1]: return falsereturn isSorted(A, i+1)

6) Linear search in array (recursive)

Question


Return true/index if target exists in arr using recursion.

Explain question


Search linearly but via recursion. Each call checks one index and either returns or recurses.

Approach (in-depth)


Start at index i=0. If i == n return not found. If arr[i] == target, return found. Else recurse with i+1. Variants: find first index, all indices, or last index via unwinding.

Recurrence relation


search(i) = (arr[i]==target) OR search(i+1), base i == n → false.

Pseudocode

function search(arr, i, target):
    if i == len(arr): return falseif arr[i] == target: return truereturn search(arr, i+1, target)

7) First & last occurrence of an element (recursive)

Question


Find first index and last index of x in arr.

Explain question


First occurrence: search left-to-right; return upon first match. Last occurrence: use recursion to go to the end then choose deeper result when unwinding.

Approach (in-depth)


First:


if i==n return -1. If arr[i]==x return i else return first(i+1).

Last:


if i==n return -1. Recurse res = last(i+1); if res != -1 return res else if arr[i]==x return i else -1. This uses stack unwinding to prefer later indices.

Recurrence relation


First: first(i) = if arr[i]==x then i else first(i+1).
Last: last(i) = let r = last(i+1); if r!=-1 return r; else if arr[i]==x return i else -1.

Pseudocode

function first(arr, i, x):
    if i == len(arr): return -1if arr[i] == x: return i
    return first(arr, i+1, x)
function last(arr, i, x):
    if i == len(arr): return -1    r = last(arr, i+1, x)
    if r != -1: return r
    if arr[i] == x: return i
    return -1

8) Power function x^n (recursive, fast)

Question


Compute x^n.

Explain question


Use recursion to reduce exponent quickly via divide & conquer.

Approach (in-depth)


Naive recursion is x * x^(n-1) (linear depth). Fast exponentiation uses halving: compute half = power(x, n/2). If n even, result = half * half. If odd, result = half * half * x. Handle n==0 base. For negative exponents use reciprocals (if float/double).

Recurrence relation


power(n) = power(n/2)^2 (even); = x * power(n/2)^2 (odd); base power(0)=1.

Pseudocode

function power(x, n):
    if n == 0: return 1    half = power(x, n // 2)if n % 2 == 0: return half * half
    else: return x * half * half

9) Tower of Hanoi

Question


Move n disks from peg A to peg C using B with legal moves.

Explain question


To move the largest disk you must first move the top n-1 off the source to the helper, move largest to destination, then move n-1 onto it.

Approach (in-depth)


Base: n==1 — move disk from A→C. Recursively: move(n-1, A, B, C), print move n A→C, then move(n-1, B, C, A). This yields minimal 2^n - 1 moves. Connects directly to recurrence T(n)=2T(n-1)+1.

Recurrence relation


T(n)=2*T(n-1)+1, with T(1)=1; so T(n)=2^n - 1.

Pseudocode

function hanoi(n, from, to, aux):
    if n == 1:
        print(move disk 1 from from to to)
        return    hanoi(n-1, from, aux, to)
    print(move disk n from from to to)
    hanoi(n-1, aux, to, from)

10) Generate all permutations of a string/array (distinct)

Question


Return all permutations of nums or characters.

Explain question


We must generate every ordering without duplicates. The recursion explores positions one-by-one and fills them with unused elements.

Approach (in-depth)


Two common patterns:

  • Swap-based:


    For index i from 0..N-1, swap arr[i] with arr[start], recurse start+1, then swap back. This does in-place generation, O(1) extra per level.

  • Used array Pattern:

    Maintain used[] and path[]; loop all indices, pick unused, mark used, recurse, unmark. When path.Length==n add a copy.

Backtracking step removes the last choice (or swaps back) to try other numbers.

Recurrence relation


perm(k) generates (n-k) branches where k is current position: f(k) = sum_{for each unused i} f(k+1); base k==n → output.

Pseudocode (swap)


function permute(arr, start):
    if start == n:
        add copy of arr as a permutation
        returnfor i = start..N-1:
        swap(arr, start, i)
        permute(arr, start+1)
        swap(arr, start, i)  // backtrack

11) Generate all subsequences (subsets)

Question


Return all subsets (power set).

Explain question


Each element can be present or absent, independent of order — total 2^n subsets. Must preserve inclusion decisions.

Approach (in-depth)


Classic include/exclude recursion: define function backtrack(index, path). For each index you do:

  • Exclude: call backtrack(index+1, path).
  • Include: path.Add(nums[index]), call backtrack(index+1, path), then path.RemoveLast().

Add path (copy) to result at each call if you want all subsets incrementally, or only at base index==n.

Recurrence relation


f(i) = f(i+1) [exclude] + f(i+1) with nums[i] included.

Pseudocode

function subsets(nums):
    backtrack(0, [])function backtrack(i, path)
:
    if i == n: add copy(path); return    backtrack(i+1, path)          // excludepath.Add(nums[i])
    backtrack(i+1, path)          // includepath.RemoveLast()

12) Print all paths in a maze/grid (Right & Down only)

Question


From (0,0) to (m-1,n-1) move only Right (R) or Down (D) and print all valid paths (with obstacles optionally).

Explain question


Because moves only progress right/down, no cycles; each path has (m-1) downs and (n-1) rights. Backtracking is simpler (no visited[] required).

Approach (in-depth)


Define dfs(i,j,path). If (i,j)==(m-1,n-1) print path. Else:

  • If j+1 < n and cell open: dfs(i, j+1, path + "R").
  • If i+1 < m and cell open: dfs(i+1, j, path + "D").

With obstacles, check cell value. The recursion branches until bounds.

Recurrence relation


paths(i,j) = paths(i+1,j) + paths(i,j+1) constrained by obstacles.

Pseudocode

function dfs(i, j, path):
    if i == m-1 and j == n-1:
        print pathreturnif j+1 < n and open(i, j+1): dfs(i, j+1, path + "R")
    if i+1 < m and open(i+1, j): dfs(i+1, j, path + "D")

13) N-Queens

Question


Place n queens on an n×n board so none attack one another; return all valid placements.

Explain question


We place queens row-by-row. Each placement restricts columns and diagonals for lower rows.

Approach (in-depth)


Backtrack by row:

  • backtrack(row):
    • If row == n, construct board from queen positions and add to results.
    • For each col 0..N-1:
      • If col, row-col diagonal, and row+col diagonal are free, place queen (mark column & diagonals), call backtrack(row+1), then unmark.

Optimizations: maintain boolean arrays cols[n], diag1[2n] (row-col offset), diag2[2n] (row+col) for O(1) safety checks.

Recurrence relation


solutions(row) = sum_{col valid} solutions(row+1).

Pseudocode

function solveNQueens(n):
    backtrack(0)function backtrack(row):
    if row == n: add board; returnfor col in 0..N-1:
        if safe(row, col):
            place queen at (row,col)
            backtrack(row+1)
            remove queen at (row,col)

14) Sudoku solver (9×9)

Question


Fill a partially filled 9×9 board so every row, column, and 3×3 block contains digits 1..9 exactly once.

Explain question


Each empty cell is a choice point: choose a number 1–9 that doesn’t conflict with row, column, block constraints. Backtrack when no valid number leads to a solution.

Approach (in-depth)


  • Choose an empty cell (heuristic: choose one with fewest possibilities to speed up).
  • For num in 1..9:
    • If num not in that row, col, and 3x3 block → place it and recurse to next empty.
    • If recursion returns false, remove (0) and try next number.
  • If no number works → return false (trigger backtracking)
    .

Maintain rows[9][10], cols[9][10], boxes[9][10] boolean arrays to check validity in O(1). When placing, set flags; when removing, clear them.

Recurrence relation


solve(k) where k is number of empty cells filled so far; solve(k) = try each allowed digit for next empty cell and recurse.

Pseudocode

function solveSudoku(board):
    if no empty cell: return true    (r,c) = pick empty
    for num in 1..9:
        if safe to place num:
            place num
            if solveSudoku(board): return true            remove num
    return false

15) Rat in a Maze (4-directional with obstacles)

Question


Print all paths from (0,0) to (n-1,n-1) moving U/D/L/R through cells marked 1, not revisiting cells.

Explain question


This is a typical DFS with visited tracking to avoid cycles. Each step can move to 4 neighbors if inside and not visited and cell is open.

Approach (in-depth)


  • Use a visited[][] boolean set; mark starting cell visited.
  • dfs(x,y,path): if (x,y) is target print path. Else iterate four directions (D,R,L,U):
    • Compute nx,ny. If valid and open and not visited: mark visited, dfs(nx,ny,path+dir), then visited[nx][ny]=false (backtrack).
  • Ordering of directions changes printed order but not correctness.

Recurrence relation


paths(x,y) = sum_{neighbors valid} paths(nx,ny) with visited preventing repeat.

Pseudocode

function dfs(x,y):
    if x==n-1 and y==n-1: print path; returnfor dir in [D,R,L,U]:
        nx, ny = x+dx, y+dy
        if valid and maze[nx][ny]==1 and not visited[nx][ny]:
            visited[nx][ny]=true            dfs(nx,ny)
            visited[nx][ny]=false

16) Word Search in a grid (single word)

Question


Given board of chars and a word, does the word exist by sequentially adjacent (vertical/horizontal) characters, no reuse of cell.

Explain question


Start DFS from any cell matching the first char. Walk neighbors matching the next character, marking visited to avoid reusing cells. If you reach full word length, success.

Approach (in-depth)


For every cell (i,j):

  • If board[i][j] == word[0], call dfs(i,j, idx=0).
    dfs(x,y,idx):
  • If idx == word.Length return true.
  • If out of bounds or char mismatch or visited → return false.
  • Mark visited, explore 4 directions with idx+1. If any returns true, propagate true; otherwise unmark visited and return false.

Recurrence relation


dfs(idx,x,y) = OR_{neighbors} dfs(idx+1,nx,ny) if board[x][y] == word[idx].

Pseudocode

function exist(board, word):
    for each cell:
        if dfs(cell, 0): return truereturn false
function dfs(x,y,idx):
    if idx == len(word): return trueif out of bounds or board[x][y] != word[idx] or visited: return false    visited[x][y]=truefor each neighbor:
        if dfs(nx,ny,idx+1): return true    visited[x][y]=falsereturn false

17) Combination Sum

Question


Given distinct candidates[] and target, return all unique combinations where numbers sum to target; numbers may be reused.

Explain question


Each candidate can be chosen multiple times. Order of numbers in a combination doesn’t matter (use index to avoid duplicates). This is a classic unbounded knapsack via backtracking.

Approach (in-depth)


Backtrack with parameters (index, remaining, path):

  • Base: if remaining == 0, add copy of path.
  • If index == len(candidates) or remaining < 0 return.
  • Two choices at each index:

    • Take current


      path.Add(candidates[index]), recurse with same index and remaining - candidates[index] (because reuse is allowed); then path.RemoveLast().

    • Skip current

      Recurse with index+1 and same remaining.

Sort candidates optionally (not required) and prune early when candidate > remaining.

Recurrence relation


f(index, rem) = f(index, rem - candidates[index]) [choose] + f(index+1, rem) [skip].

Pseudocode

function backtrack(index, rem):
    if rem == 0: add copy(path); returnif index == n or rem < 0: return    // choose
    path.Add(candidates[index])
    backtrack(index, rem - candidates[index])
    path.RemoveLast()
    // skip
    backtrack(index+1, rem)

18) Permutations of an array (distinct)

(duplicate of #10 but listed separately)

Question


Return all permutations of nums.

Explain question


Same as #10.

Approach (in-depth)


Either use swap-in-place or used[]+path; both already described. Swap-based is often compact and avoids used[].

Recurrence relation


Same as #10.

Pseudocode (swap)


permute(start):
    if start == n: add copy(arr)
    for i = start..N-1:
        swap(arr[start], arr[i])
        permute(start+1)
        swap(arr[start], arr[i])

19) Permutations II (with duplicates)

Question


Return unique permutations when nums may contain duplicates.

Explain question


Naive permutations will generate duplicates because identical elements at different indices produce same orderings; we must avoid duplicate branches.

Approach (in-depth)


Sort the array first. Use used[] boolean. In the loop:

  • Skip i if used[i] is true.

  • Crucial rule:

    if i>0 && nums[i] == nums[i-1] && !Used[i-1] then continue. This ensures at the same recursion depth you only use the first of equal values to start a branch. After choosing nums[i], mark used[i]=true, recurse, then unmark.

This rule prevents sibling branches from starting with equal numbers in different orders.

Recurrence relation


permUnique(path) = for each i not used and not skipped due to duplicate rule: choose i and permUnique(path + nums[i]).

Pseudocode

sort(nums)
backtrack(path):
    if path.Size == n: add copy(path); returnfor i in 0..N-1:
        if used[i]: continueif i>0 and nums[i]==nums[i-1] and not used[i-1]: continue        used[i]=true; path.Add(nums[i])
        backtrack(path)
        used[i]=false; path.RemoveLast()

20) Palindrome Partitioning

Question


Return all possible partitions of s such that every substring in partition is a palindrome.

Explain question


You must cut the string into contiguous pieces; each piece must be a palindrome. Explore all cut positions, pruning when substring is not a palindrome.

Approach (in-depth)


Backtrack by start index:

  • backtrack(start, path):
    • If start == len(s): add copy of path to results.
    • For end from start to len(s)-1:
      • Check if s[start..End] is palindrome (use helper or DP table).
      • If palindrome: add substring to path, recurse backtrack(end+1, path), then removeLast() (backtrack).

Optimization: precompute isPal[start][end] with DP for O(1) palindrome checks (O(n²) precompute) to speed repeated checks.

Recurrence relation


part(start) = for end in start..N-1 if palindrome(start,end) then part(end+1); base part(n) = [[]].

Pseudocode

function partition(s):
    precompute isPal[][] or use check    backtrack(0, [])function backtrack(start, path):
    if start == n: add copy(path); returnfor end in start..N-1:
        if isPalindrome(s, start, end):
            path.Add(s[start..End])
            backtrack(end+1, path)
            path.RemoveLast()

Final notes & quick reminders

  • For all backtracking problems: always push a copy (new list) into results (e.G., new ArrayList<>(path)), not the mutable path reference.
  • For grid DFS tasks (Word Search, Rat in Maze): use visited[][] or temporarily alter the board (e.G., set board[x][y] = '#') and restore it after recursion.
  • For duplicate-handling (subsets II, permutations II): sort first and skip duplicates at the same recursion level.
  • For performance: use memoization where the recursion recomputes the same state (Fibonacci), or precompute tables (palindrome DP), or use specialized structures (Trie for Word Search II).
  • Convert pseudocode blocks to Java by replacing removeLast() with path.Remove(path.Size()-1), using List<List<...>> and copying with new ArrayList<>(path).