Recursion in C++ | Structure With Examples

What You’ll Learn

By the end of this post, you will:

• Understand what recursion is and how it works in C++
• Learn the concepts of base case and recursive case
• Write recursive functions to solve common problems
• Understand when and why to use recursion
• Avoid common recursion pitfalls like infinite recursion and stack overflow

---

What is Recursion?

Recursion is a programming technique where a function calls itself to solve a smaller version of the original problem.

In simpler terms:
A function solves a problem by solving a smaller part of it repeatedly until it reaches a stopping condition.

---

Structure of a Recursive Function

Every recursive function must have:

1. Base Case: A condition that ends the recursion
2. Recursive Case: The part where the function calls itself

General Pattern:

returnType functionName(parameters) {
    if (base_case_condition)
        return base_value;
    else
        return functionName(smaller_problem);
}

---

Example 1: Factorial (n!)

The factorial of a number n is defined as:
n! = n × (n - 1) × (n - 2) × ... × 1
And 0! = 1 (base case)

Recursive Solution:

int factorial(int n) {
    if (n == 0)
        return 1;              // base case
    else
        return n * factorial(n - 1); // recursive case
}

Usage:

int main() {
    int n = 5;
    cout << "Factorial of " << n << " is " << factorial(n);
    return 0;
}

How Recursion Works (Call Stack)

When you call a recursive function, each call is placed on the call stack. Once the base case is reached, the calls start returning one by one.

For factorial(3):

factorial(3)
  -> 3 * factorial(2)
    -> 2 * factorial(1)
      -> 1 * factorial(0)
        -> 1
      <- returns 1 * 1 = 1
    <- returns 2 * 1 = 2
  <- returns 3 * 2 = 6

---

Example 2: Fibonacci Sequence

Fibonacci numbers:

0, 1, 1, 2, 3, 5, 8, 13, ...

• fib(0) = 0
• fib(1) = 1
• fib(n) = fib(n - 1) + fib(n - 2) for n > 1

Recursive Code:

int fib(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fib(n - 1) + fib(n - 2);
}

Warning:

This is not efficient for large n due to repeated calculations. We’ll discuss optimizations like memoization later.

---

Example 3: Sum of Digits

int sumOfDigits(int n) {
    if (n == 0) return 0;
    return n % 10 + sumOfDigits(n / 10);
}

For n = 123, it returns 1 + 2 + 3 = 6.

---

Example 4: Power Function

Compute a^b (a raised to the power b):

int power(int a, int b) {
    if (b == 0)
        return 1;
    return a * power(a, b - 1);
}

---

Example 5: Tower of Hanoi (Classic Recursion Problem)

Move n disks from rod A to rod C using rod B as auxiliary.

void hanoi(int n, char source, char helper, char destination) {
    if (n == 1) {
        cout << "Move disk 1 from " << source << " to " << destination << endl;
        return;
    }
    hanoi(n - 1, source, destination, helper);
    cout << "Move disk " << n << " from " << source << " to " << destination << endl;
    hanoi(n - 1, helper, source, destination);
}

---

When Should You Use Recursion?

Use recursion when:

• The problem can be broken into smaller, similar subproblems
• You can define a clear base case
• Problems involve tree traversal, divide-and-conquer, backtracking, or combinatorics

---

Common Mistakes to Avoid

• Missing a base case → infinite recursion → stack overflow
• Changing the problem incorrectly in the recursive call
• Not returning the recursive result when needed
• Using recursion for problems that can be solved more efficiently with loops (e.g., Fibonacci without memoization)

---

Mini Exercises

1. Write a recursive function to calculate the sum of the first n natural numbers.
2. Create a recursive function to check if a string is a palindrome.
3. Implement gcd(a, b) using recursion (Hint: use Euclid’s algorithm).
4. Use recursion to reverse an array in place.

---

Summary

In this post, you learned:

• The basic structure of recursive functions
• How recursion uses the call stack
• How to write recursive solutions for factorial, Fibonacci, sum of digits, power, and Tower of Hanoi
• When recursion is appropriate, and common mistakes to avoid

---

What’s Next?

In the next post, we’ll explore Structures in C++ — how to group related data using struct, and how it leads to more advanced data types like linked lists and objects.