What is recursion?

Recursion in C++ is a programming technique where a function calls itself to solve a problem. Instead of solving the entire problem at once, recursion breaks it into smaller, similar subproblems until it reaches a condition where no further recursive calls are needed.

Imagine standing in front of two mirrors facing each other. Each mirror reflects the other repeatedly. Similarly, a recursive function keeps calling itself until it reaches a stopping point known as the base case.

Recursion exists because many problems have a naturally repetitive structure. Rather than using loops, recursion provides a clean and elegant way to solve problems by dividing them into smaller tasks.

Real-world use cases

• Traversing directory structures (folders within folders)
• Tree and graph algorithms
• Binary search
• Divide-and-conquer algorithms (Merge Sort, Quick Sort)
• Dynamic programming
• Mathematical computations (factorial, Fibonacci)
• Parsing expressions and compilers

Prerequisites

• Variables and data types
• Functions
• Function parameters and return values
• Conditional statements (if, else)
• Loops (for, while)
• Basic problem-solving skills

General syntax

A recursive function is a function that calls itself until a specific condition is met.

returnType functionName(parameters)
{
    // Base case
    if (condition)
        return value;

    // Recursive case
    return functionName(modifiedParameters);
}

Every recursive function has two essential parts: a base case, which stops recursion, and a recursive case, which calls the function again with a smaller or simpler problem. Without a base case, recursion continues indefinitely, causing a stack overflow.

How recursion works

Suppose we calculate the factorial of 4. The calls proceed as factorial(4), factorial(3), factorial(2), factorial(1), which returns 1. Then the function returns back step by step: 1, 2 × 1 = 2, 3 × 2 = 6, 4 × 6 = 24. This process is known as unwinding the recursion stack.

The call stack

Every time a recursive function is called, the system stores information about that call in a memory area called the call stack. Each function call waits until the next recursive call finishes before continuing execution.

Types of recursion

Direct recursion is when a function directly calls itself.

void print()
{
    print();
}

Indirect recursion is when two or more functions call each other, such as A() calling B() which calls A() again.

Tail recursion is when the recursive call is the last operation performed. Tail recursion can sometimes be optimized by compilers.

return function(n - 1);

Head recursion is when the recursive call occurs before other operations.

function(n - 1);

cout << n;

Recursion vs iteration

• Recursion: uses function calls, uses the call stack, higher memory usage, often simpler code, slightly slower performance
• Iteration: doesn't use function calls, doesn't use the call stack, lower memory usage, sometimes longer code, usually faster performance

Example 1: Print numbers

#include <iostream>
using namespace std;

void printNumbers(int n)
{
    if (n == 0)
        return;

    cout << n << " ";

    printNumbers(n - 1);
}

int main()
{
    printNumbers(5);

    return 0;
}

// Output: 5 4 3 2 1

Example 2: Factorial

#include <iostream>
using namespace std;

int factorial(int n)
{
    if (n <= 1)
        return 1;

    return n * factorial(n - 1);
}

int main()
{
    cout << factorial(5);

    return 0;
}

// Output: 120

Example 3: Fibonacci

#include <iostream>
using namespace std;

int fibonacci(int n)
{
    if (n <= 1)
        return n;

    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main()
{
    cout << fibonacci(6);

    return 0;
}

// Output: 8

Example 4: Sum of array elements

#include <iostream>
using namespace std;

int sumArray(int arr[], int size)
{
    if (size == 0)
        return 0;

    return arr[size - 1] + sumArray(arr, size - 1);
}

int main()
{
    int numbers[] = {2, 4, 6, 8, 10};

    int size = sizeof(numbers) / sizeof(numbers[0]);

    cout << sumArray(numbers, size);

    return 0;
}

// Output: 30

Example 5: Binary search using recursion

#include <iostream>
using namespace std;

int binarySearch(int arr[], int left, int right, int target)
{
    if (left > right)
        return -1;

    int mid = left + (right - left) / 2;

    if (arr[mid] == target)
        return mid;

    if (target < arr[mid])
        return binarySearch(arr, left, mid - 1, target);

    return binarySearch(arr, mid + 1, right, target);
}

int main()
{
    int arr[] = {5, 10, 15, 20, 25, 30};

    int size = sizeof(arr) / sizeof(arr[0]);

    cout << binarySearch(arr, 0, size - 1, 20);

    return 0;
}

// Output: 3

Common mistakes and pitfalls

• Missing base case. Fix: always define a base case
• Recursive call never reduces problem size. Fix: pass a smaller input each time
• Infinite recursion. Fix: ensure recursion eventually stops
• Using recursion for very deep problems. Fix: consider iteration or optimized algorithms
• Ignoring stack overflow. Fix: test with large inputs

// Wrong
void count(int n)
{
    cout << n << endl;

    count(n + 1);
}

// Correct
void count(int n)
{
    if (n == 0)
        return;

    cout << n << endl;

    count(n - 1);
}

Best practices

• Always define a clear base case
• Ensure every recursive call moves closer to the base case
• Keep recursive functions small and focused
• Use meaningful function names
• Avoid unnecessary recursive calls
• Consider memoization for expensive recursive algorithms like Fibonacci
• Use iteration instead of recursion when the recursion depth may become very large
• Test edge cases such as 0, 1, and empty inputs

When not to use this

• The recursion depth may exceed the call stack limit
• A simple loop provides a clearer solution
• Performance is critical and recursive overhead is unnecessary
• The problem does not naturally divide into smaller subproblems
• Memory usage from the call stack could become excessive

Examples include printing numbers in a simple sequence, processing very large arrays sequentially, and deep recursive calls without compiler optimization.

Summary

• Recursion in C++ is a technique where a function calls itself
• Every recursive function requires a base case and a recursive case
• The call stack stores each function call until recursion completes
• Recursive solutions are often shorter and easier to understand for divide-and-conquer problems
• Tail recursion may be optimized by some compilers
• Poorly designed recursion can cause stack overflow
• Recursion is widely used in tree traversal, searching, sorting, and mathematical algorithms
• Always ensure recursive calls make progress toward the base case

Frequently asked questions

What is recursion in C++?

Recursion is a programming technique where a function calls itself repeatedly until a base condition is satisfied.

What is a base case?

A base case is the condition that stops further recursive calls, preventing infinite recursion.

Is recursion better than loops?

Not always. Recursion often produces cleaner code for naturally recursive problems, while loops are generally faster and use less memory for simple repetitive tasks.

What is stack overflow in recursion?

A stack overflow occurs when too many recursive function calls fill the call stack because the recursion never ends or is too deep.

Where is recursion commonly used?

Recursion is commonly used in tree traversals, graph algorithms, binary search, divide-and-conquer algorithms, backtracking, dynamic programming, and mathematical computations like factorial and Fibonacci.