A function that calls itself to solve a smaller version of the same problem.

Essential Components

Base Case - When to stop (prevents stack overflow)

Recursive Call - Function calling itself with modified parameters

Processing - Optional work done before or after recursive call

Key Points

Provides compact approach to problems

Iterative approach generally consumes less time and space

Every recursive call uses stack memory. If base case is not applied, it will consume all the stack memory and the function call stack will overflow

Types of Recursion

Type Description Processing Location
Head Recursion Processing before recursive call Above recursive call
Tail Recursion Processing after recursive call Below recursive call

Basic Examples

Sum of Natural Numbers

Logic: sum(n) = n + sum(n-1)

int getSum(int n) {
    //base case
    if(n == 1) 
        return 1;
    //recursive relation
    //sum(n) = sum(n-1) + n;
    int ans = getSum(n-1) + n;
    return ans;
    //processing
}

Fibonacci Sequence

Logic: fib(n) = fib(n-1) + fib(n-2)