Recursion in Algorithms — Recurrence Relations

Recursion

Recursion is a programming technique in which a function solves a problem by calling itself on a smaller version of the same problem.

It is one of the most important ideas in algorithms because many problems naturally break into smaller subproblems. Sorting, tree traversal, divide and conquer, backtracking, and dynamic programming all rely heavily on recursive thinking.

Basic Idea of Recursion

Every recursive solution must contain two essential parts:

• Base case: The stopping condition that prevents infinite recursion.
• Recursive case: The part where the function calls itself with a smaller or simpler input.

How Recursion Works

When a recursive function is called:

• The current function call is pushed onto the call stack.
• The function keeps calling itself until the base case is reached.
• After the base case returns, the pending calls are completed one by one in reverse order.

Structure of a Recursive Function

int recursiveFunction(int n) {
    if (base condition) {
        return base value;
    }

    return recursiveFunction(smaller input);
}

A correct recursive solution must always move toward the base case. If it does not, the recursion will never stop.

Classic Examples of Recursion

1. Factorial

The factorial of a number is defined as:

n! = n * (n - 1)!, with 0! = 1 and 1! = 1.

public class Factorial {

    static long factorial(int n) {
        if (n <= 1) {
            return 1;
        }
        return n * factorial(n - 1);
    }

    public static void main(String[] args) {
        System.out.println(factorial(5));
    }
}

This works because the problem size decreases from n to n - 1 until the base case is reached.

2. Fibonacci

The Fibonacci sequence is defined as:

F(n) = F(n - 1) + F(n - 2), with F(0) = 0 and F(1) = 1.

public class Fibonacci {

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

    public static void main(String[] args) {
        System.out.println(fib(8));
    }
}

Although this definition is simple, naive recursive Fibonacci is inefficient because it recomputes the same subproblems many times.

3. Tower of Hanoi

This is a classic recursive problem where we move n disks from one rod to another using an auxiliary rod.

public class TowerOfHanoi {

    static void solve(int n, char source, char destination, char auxiliary) {
        if (n == 1) {
            System.out.println("Move disk 1 from " + source + " to " + destination);
            return;
        }

        solve(n - 1, source, auxiliary, destination);
        System.out.println("Move disk " + n + " from " + source + " to " + destination);
        solve(n - 1, auxiliary, destination, source);
    }
}

Call Stack in Recursion

Every recursive call creates a new stack frame on the call stack. That frame stores local variables, parameters, and the return address.

This is why recursion uses extra memory. Deep recursion may cause a stack overflow if the call depth becomes too large.

Recurrence Relations

A recurrence relation expresses the running time of a recursive algorithm in terms of smaller inputs.

Direct and Indirect Recursion

Recursion can be classified based on how functions call each other.

public class IndirectRecursion {

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

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

Tail Recursion

A recursive function is called tail recursive when the recursive call is the last operation in the function. No extra work remains after the recursive call returns.

public class TailRecursion {

    static long factorialTail(int n, long acc) {
        if (n <= 1) {
            return acc;
        }
        return factorialTail(n - 1, n * acc);
    }
}

Some languages or compilers can optimize tail recursion into iteration, but you should not assume that every language always does this.

Recursion vs Iteration

Where Recursion Is Commonly Used

• Divide and conquer: Merge Sort, Quick Sort, Binary Search
• Tree problems: preorder, inorder, postorder traversal
• Graph traversal: depth-first search
• Backtracking: N-Queens, Sudoku, permutations
• Dynamic programming: top-down memoization

Common Mistakes in Recursion

• Forgetting to write a base case.
• Writing a base case that never gets reached.
• Not reducing the problem size correctly.
• Ignoring repeated subproblems, as in naive Fibonacci.
• Using recursion when an iterative solution is simpler and safer.

Key Takeaways

• Recursion solves a problem by reducing it to smaller instances of the same problem.
• Every recursive function needs a base case and a recursive case.
• Recursive calls use the call stack, so memory usage depends on recursion depth.
• Recurrence relations help analyze recursive time complexity.
• Recursion is powerful, but it must be used carefully to avoid inefficiency and stack overflow.