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

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

General Recursive Structure

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

    return recursiveFunction(smaller input);
}

Classic Examples of Recursion

These examples show three different recursion shapes: one smaller call, two overlapping calls, and a divide-move-combine sequence.

Factorial Recursion

Factorial follows n! = n * (n - 1)! with 0! = 1. Each call reduces n by one, so the algorithm reaches its base case after n stack frames and runs in O(n) time.

Factorial Example

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));
    }
}

Output

Fibonacci Recursion

Fibonacci follows F(n) = F(n - 1) + F(n - 2), with F(0) = 0 and F(1) = 1. The direct recursive form is easy to read but recomputes overlapping subproblems, giving exponential time without memoization.

Naive Fibonacci Example

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));
    }
}

Output

Tower of Hanoi

To move n disks, first move n - 1 disks to the auxiliary rod, move the largest disk to the destination, and then move the n - 1 disks onto it. The recurrence T(n) = 2T(n - 1) + O(1) gives O(2^n) moves.

Tower of Hanoi Example

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.

Step	Current Call	What Happens
1	factorial(4)	Needs factorial(3)
2	factorial(3)	Needs factorial(2)
3	factorial(2)	Needs factorial(1)
4	factorial(1)	Base case returns 1
5	factorial(2)	Returns 2 * 1 = 2
6	factorial(3)	Returns 3 * 2 = 6
7	factorial(4)	Returns 4 * 6 = 24

Recurrence Relations

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

Algorithm	Recurrence	Time Complexity
Factorial	T(n) = T(n - 1) + O(1)	O(n)
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)
Naive Fibonacci	T(n) = T(n - 1) + T(n - 2) + O(1)	O(2^n) roughly
Tower of Hanoi	T(n) = 2T(n - 1) + O(1)	O(2^n)

Direct and Indirect Recursion

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

Type	Meaning	Example
Direct recursion	A function calls itself directly	factorial(n) calling factorial(n - 1)
Indirect recursion	Function A calls B, and B calls A	isEven() and isOdd()

Indirect Recursion

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.

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

Tail Recursion - Java Example

public class TailRecursion {

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

Recursion vs Iteration

Aspect	Recursion	Iteration
Readability	Often cleaner for recursive structures	Often clearer for simple loops
Memory	Uses call stack	Usually uses constant stack space
Performance	May have function call overhead	Often slightly faster
Best for	Trees, divide and conquer, backtracking	Simple counting and traversal

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

Recursion Failure Cases

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.

Recursion Rules

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.

Before you move on