Recursion in Algorithms

What is Recursion?

Recursion is a technique where a function calls itself to solve a smaller version of the same problem. Every recursive solution has two parts:

Base case â€” the condition that stops the recursion (prevents infinite loop).
Recursive case â€” the function calls itself with a simpler/smaller input.

Recursion is the foundation of many important algorithms: merge sort, quick sort, tree traversals, DFS, backtracking, and dynamic programming.

Recurrence Relations

A recurrence relation expresses the time complexity of a recursive algorithm in terms of smaller inputs. Solving it gives the closed-form Big-O.

Algorithm	Recurrence	Solution
Binary Search	T(n) = T(n/2) + O(1)	O(log n)
Merge Sort	T(n) = 2T(n/2) + O(n)	O(n log n)
Fibonacci (naive)	T(n) = T(n-1) + T(n-2) + O(1)	O(2â¿)
Factorial	T(n) = T(n-1) + O(1)	O(n)
Tower of Hanoi	T(n) = 2T(n-1) + O(1)	O(2â¿)

Recursion Examples â€” Factorial, Fibonacci, Tower of Hanoi

public class Recursion {

    // Factorial: n! = n * (n-1)!
    // T(n) = T(n-1) + O(1) â†’ O(n)
    static long factorial(int n) {
        if (n <= 1) return 1;          // base case
        return n * factorial(n - 1);   // recursive case
    }

    // Fibonacci: F(n) = F(n-1) + F(n-2)
    // T(n) = T(n-1) + T(n-2) + O(1) â†’ O(2^n) â€” very slow!
    static long fibNaive(int n) {
        if (n <= 1) return n;
        return fibNaive(n - 1) + fibNaive(n - 2);
    }

    // Tower of Hanoi: move n disks from src to dest via aux
    // T(n) = 2T(n-1) + O(1) â†’ O(2^n)
    static void hanoi(int n, char src, char dest, char aux) {
        if (n == 1) {
            System.out.println("Move disk 1: " + src + " â†’ " + dest);
            return;
        }
        hanoi(n - 1, src, aux, dest);   // move n-1 disks to aux
        System.out.println("Move disk " + n + ": " + src + " â†’ " + dest);
        hanoi(n - 1, aux, dest, src);   // move n-1 disks from aux to dest
    }

    // Power: x^n using divide and conquer
    // T(n) = T(n/2) + O(1) â†’ O(log n)
    static double power(double x, int n) {
        if (n == 0) return 1;
        if (n % 2 == 0) {
            double half = power(x, n / 2);
            return half * half;          // reuse result â€” O(log n)
        }
        return x * power(x, n - 1);
    }

    public static void main(String[] args) {
        System.out.println("5! = " + factorial(5));       // 120
        System.out.println("fib(8) = " + fibNaive(8));    // 21
        System.out.println("2^10 = " + (int)power(2, 10)); // 1024
        System.out.println("\nTower of Hanoi (3 disks):");
        hanoi(3, 'A', 'C', 'B');
    }
}

How the Call Stack Works

Each recursive call pushes a new stack frame onto the call stack. When the base case is reached, frames are popped and results propagate back up. This is why deep recursion can cause a StackOverflowError.

Step	Call Stack (top = current)	Action
1	factorial(4)	4 ≠ 1, call factorial(3)
2	factorial(3) ← factorial(4)	3 ≠ 1, call factorial(2)
3	factorial(2) ← factorial(3) ← factorial(4)	2 ≠ 1, call factorial(1)
4	factorial(1) ← factorial(2) ← ...	Base case! return 1
5	factorial(2) ← factorial(3) ← factorial(4)	return 2 × 1 = 2
6	factorial(3) ← factorial(4)	return 3 × 2 = 6
7	factorial(4)	return 4 × 6 = 24

Direct vs Indirect Recursion

Direct recursion â€” a function calls itself directly: f() { ... f() ... }
Indirect recursion â€” function A calls function B which calls function A: f() { g() } g() { f() }

Indirect Recursion â€” Even/Odd Check

public class IndirectRecursion {

    // isEven calls isOdd, isOdd calls isEven â€” indirect recursion
    static boolean isEven(int n) {
        if (n == 0) return true;
        return isOdd(n - 1);   // calls isOdd
    }

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

    public static void main(String[] args) {
        System.out.println("isEven(4) = " + isEven(4));  // true
        System.out.println("isOdd(7)  = " + isOdd(7));   // true
        System.out.println("isEven(3) = " + isEven(3));  // false
    }
}

Recursion vs Iteration

Aspect	Recursion	Iteration
Code clarity	Cleaner for tree/graph problems	Cleaner for simple loops
Performance	Slower (function call overhead)	Faster
Memory	Uses call stack (risk of overflow)	Uses constant stack space
Best for	Tree traversal, divide & conquer, backtracking	Simple counting, array traversal
Debugging	Harder to trace	Easier to trace

Tail Recursion

A recursive call is tail recursive if it is the last operation in the function. Tail-recursive functions can be optimized by the compiler into iteration (tail call optimization), avoiding stack overflow for large inputs.

Tail Recursion vs Regular Recursion

public class TailRecursion {

    // Regular recursion â€” NOT tail recursive
    // Must wait for recursive call to return before multiplying
    static long factorial(int n) {
        if (n <= 1) return 1;
        return n * factorial(n - 1);  // multiplication happens AFTER return
    }

    // Tail recursive factorial â€” accumulator carries the result
    // The recursive call is the LAST operation
    static long factTail(int n, long acc) {
        if (n <= 1) return acc;
        return factTail(n - 1, n * acc);  // last operation = recursive call
    }

    // Sum of array â€” tail recursive
    static int sumTail(int[] arr, int i, int acc) {
        if (i == arr.length) return acc;
        return sumTail(arr, i + 1, acc + arr[i]);
    }

    public static void main(String[] args) {
        System.out.println("5! = " + factorial(5));          // 120
        System.out.println("5! tail = " + factTail(5, 1));   // 120

        int[] arr = {1, 2, 3, 4, 5};
        System.out.println("Sum = " + sumTail(arr, 0, 0));   // 15
    }
}