RECURSION VS
ITERATION PATTERNS.

What is Recursion?

A function that calls itself to solve a smaller subproblem.

Components of a Recursive Function

• Base Case – stops recursion, provides answer for smallest input
• Recursive Case – reduces problem size, calls itself
• Return – combines results from recursive calls

int factorial(int n) {
    // Base case
    if (n <= 1) return 1;
    // Recursive case
    return n * factorial(n - 1);
}

What is Iteration?

A loop that repeats a block of code until a condition is met.

Common Loop Types

• for – known number of iterations
• while – condition‑based, unknown count
• do‑while – executes at least once
• for‑each – iterates over collection

int factorial(int n) {
    int result = 1;
    for (int i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

Comparison Table

When to Use Recursion

When to Use Iteration

Recursion Patterns

1. Direct Recursion

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

2. Tail Recursion (Optimized)

int factorialTail(int n, int acc) {
    if (n <= 1) return acc;
    return factorialTail(n - 1, n * acc);
}
// Call: factorialTail(5, 1) → 120

3. Mutual Recursion

boolean isEven(int n) {
    if (n == 0) return true;
    return isOdd(n - 1);
}
boolean isOdd(int n) {
    if (n == 0) return false;
    return isEven(n - 1);
}

4. Multiple Recursion (Branching)

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

5. Nested Recursion

int ackermann(int m, int n) {
    if (m == 0) return n + 1;
    if (n == 0) return ackermann(m - 1, 1);
    return ackermann(m - 1, ackermann(m, n - 1));
}

Conversion: Recursion → Iteration

Method 1: Use a Stack (Manual Call Stack)

// Recursive DFS
void dfs(TreeNode root) {
    if (root == null) return;
    System.out.print(root.val);
    dfs(root.left);
    dfs(root.right);
}

// Iterative DFS (using Stack)
void dfsIterative(TreeNode root) {
    if (root == null) return;
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode curr = stack.pop();
        System.out.print(curr.val);
        if (curr.right != null) stack.push(curr.right);
        if (curr.left != null) stack.push(curr.left);
    }
}

Method 2: Use a Queue (for BFS)

// Recursive BFS (usually done iteratively)
// Iterative BFS (Queue)
void bfs(TreeNode root) {
    if (root == null) return;
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    while (!q.isEmpty()) {
        TreeNode curr = q.poll();
        System.out.print(curr.val);
        if (curr.left != null) q.offer(curr.left);
        if (curr.right != null) q.offer(curr.right);
    }
}

Method 3: Tail Recursion Elimination

// Tail recursive
int sumTail(int n, int acc) {
    if (n == 0) return acc;
    return sumTail(n - 1, acc + n);
}

// Iterative (no stack)
int sumIterative(int n) {
    int acc = 0;
    while (n > 0) {
        acc += n;
        n--;
    }
    return acc;
}

Common Problems – Recursive vs Iterative

Factorial

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

int fact(int n) {
    int r = 1;
    for (int i = 2; i <= n; i++) r *= i;
    return r;
}

Fibonacci

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

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

Reverse Linked List

ListNode reverse(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode newHead = reverse(head.next);
    head.next.next = head;
    head.next = null;
    return newHead;
}

ListNode reverse(ListNode head) {
    ListNode prev = null, curr = head;
    while (curr != null) {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

Binary Tree Traversal (In‑order)

void inorder(TreeNode root) {
    if (root == null) return;
    inorder(root.left);
    System.out.print(root.val);
    inorder(root.right);
}

void inorder(TreeNode root) {
    Stack<TreeNode> st = new Stack<>();
    TreeNode curr = root;
    while (curr != null || !st.isEmpty()) {
        while (curr != null) {
            st.push(curr);
            curr = curr.left;
        }
        curr = st.pop();
        System.out.print(curr.val);
        curr = curr.right;
    }
}

Tail Recursion Optimization

• Tail recursion – recursive call is the last operation
• Compiler optimises – eliminates call stack (TCO)
• Supported in: Scala, Kotlin, Clojure, Erlang, Haskell, and some C/C++ compilers
• Not supported in: Java, Python (by default), JavaScript (limited)

Tail Recursive Example

// Non‑tail recursive (multiply after recursion)
int fact1(int n) {
    if (n <= 1) return 1;
    return n * fact1(n - 1);  // not tail – multiplication after
}

// Tail recursive (no operation after recursion)
int fact2(int n, int acc) {
    if (n <= 1) return acc;
    return fact2(n - 1, n * acc);  // tail – last operation is call
}

Recursion Pitfalls

• Stack Overflow – deep recursion exceeds call stack limit
• Exponential Time – naive recursion (e.g., Fibonacci) recomputes subproblems
• Infinite Recursion – missing or incorrect base case
• Debugging Difficult – multiple nested calls make tracing hard
• Memory Overhead – each call uses stack space

Iteration Pitfalls

• Infinite Loops – incorrect loop condition
• Off‑by‑One Errors – index boundaries
• Complex State – need to manage multiple variables
• Less Readable – for deeply recursive problems

Choosing Between Recursion and Iteration

Common Recursive Problem Categories

Memoization (Recursive + Caching)

int fibMemo(int n, int[] memo) {
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n];
    memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
    return memo[n];
}

// Time: O(n) – Space: O(n) (similar to iterative DP)
// Best of both worlds – recursive clarity + iterative performance

Summary

• Use recursion – for tree/graph traversal, backtracking, divide and conquer
• Use iteration – for simple loops, performance‑critical code, large inputs
• Consider memoization – to optimise recursive problems with overlapping subproblems
• Consider tail recursion – if supported, gives O(1) stack
• Convert when needed – use stack/queue to convert recursion to iteration