C++ course menu

C++ Recursion: Base Cases, Recursive Calls and Examples

Learn recursion in C++: functions that call themselves, base cases and recursive cases, factorial, Fibonacci, power, binary search and string reversal, how the call stack works, stack overflow, and when to use a loop instead.

Beginner11 min readUpdated October 23, 2026

On this page

The two parts of every recursive function
Factorial
How it runs: the call stack
More examples
Power
Sum of digits
Reversing a string
Binary search
Fibonacci and repeated work
Stack overflow
Recursion or a loop?
Common mistakes
Practice
Key takeaway

A recursive function is a function that calls itself. Recursion solves a problem by reducing it to a smaller version of the same problem, until the problem is so small that the answer is obvious.

The two parts of every recursive function#

A base case: the simplest input, answered directly without recursion.
A recursive case: the function calls itself with a smaller input, moving towards the base case.

Factorial#

The factorial of n (written n!) is n × (n−1) × … × 1. Notice that 5! = 5 × 4!, which is a smaller factorial:

C++

#include <iostream>

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

int main() {
    std::cout << factorial(5) << '\n';
    std::cout << factorial(20) << '\n';
}

Output

120
2432902008176640000

long long is needed because factorials grow very fast: 13! already overflows a 32-bit int.

How it runs: the call stack#

Each call gets its own copy of n, stored in a stack frame. The calls pile up until the base case, then the results flow back:

Text

factorial(4)
= 4 * factorial(3)
= 4 * (3 * factorial(2))
= 4 * (3 * (2 * factorial(1)))
= 4 * (3 * (2 * 1))
= 24

You can see the order by printing on the way in and on the way out:

C++

#include <iostream>

void countdown(int n) {
    if (n == 0) {
        std::cout << "Lift off!\n";
        return;
    }
    std::cout << "going down " << n << '\n';
    countdown(n - 1);
    std::cout << "coming back " << n << '\n';
}

int main() {
    countdown(3);
}

Output

going down 3
going down 2
going down 1
Lift off!
coming back 1
coming back 2
coming back 3

More examples#

Power#

C++

#include <iostream>

double power(double base, int exp) {
    if (exp == 0) return 1;
    return base * power(base, exp - 1);
}

int main() {
    std::cout << power(2, 10) << ' ' << power(1.5, 3) << '\n';
}

Output

1024 3.375

Sum of digits#

C++

#include <iostream>

int digit_sum(int n) {
    if (n < 10) return n;
    return n % 10 + digit_sum(n / 10);
}

int main() {
    std::cout << digit_sum(4096) << '\n';
}

Output

Reversing a string#

C++

#include <iostream>
#include <string>

std::string reverse(const std::string& s) {
    if (s.size() <= 1) return s;
    return reverse(s.substr(1)) + s[0];
}

int main() {
    std::cout << reverse("recursion") << '\n';
}

Output

noisrucer

Binary search#

Recursion is natural when a problem splits into halves. Binary search looks at the middle of a sorted range and continues in only one half:

C++

#include <iostream>
#include <vector>

int binary_search(const std::vector<int>& v, int target, int low, int high) {
    if (low > high) return -1;                 // not found
    int mid = low + (high - low) / 2;
    if (v[mid] == target) return mid;
    if (v[mid] < target) return binary_search(v, target, mid + 1, high);
    return binary_search(v, target, low, mid - 1);
}

int main() {
    std::vector<int> nums = {3, 8, 15, 23, 42, 57, 91};
    std::cout << binary_search(nums, 42, 0, nums.size() - 1) << '\n';
    std::cout << binary_search(nums, 5, 0, nums.size() - 1) << '\n';
}

Output

4
-1

low + (high - low) / 2 computes the middle without the overflow that (low + high) / 2 can cause for very large indexes.

Fibonacci and repeated work#

The Fibonacci numbers are defined recursively: fib(n) = fib(n−1) + fib(n−2). A direct translation is short but very slow, because it recomputes the same values again and again:

C++

#include <iostream>

long long fib_slow(int n) {
    if (n < 2) return n;
    return fib_slow(n - 1) + fib_slow(n - 2);
}

long long fib_fast(int n) {
    long long a = 0;
    long long b = 1;
    for (int i = 0; i < n; ++i) {
        long long next = a + b;
        a = b;
        b = next;
    }
    return a;
}

int main() {
    std::cout << fib_slow(20) << ' ' << fib_fast(20) << '\n';
    std::cout << fib_fast(80) << '\n';
}

Output

6765 6765
23416728348467685

fib_slow(40) makes over 300 million calls; fib_fast(80) makes 80 loop steps. Recursion with repeated sub-problems can be fixed by remembering results (memoization), or by using a loop.

Stack overflow#

Every call uses some stack memory, and the stack is limited (often 1–8 MB). A recursion that goes too deep, or never reaches its base case, crashes with a stack overflow:

C++

int forever(int n) {
    return forever(n + 1);   // no base case
}

Make sure every recursive call moves towards the base case, and prefer a loop when the depth could be very large, for example walking a list of a million elements.

Recursion or a loop?#

Prefer recursion when	Prefer a loop when
The data is naturally recursive (trees, nested folders)	You are just counting or walking a sequence
The problem splits into halves (binary search, merge sort)	The depth could be very large
The recursive version is much clearer	Performance matters and sub-problems repeat

Common mistakes#

Practice#

Practice exercise

Write a recursive function int count_char(const std::string& s, char c, std::size_t i = 0) that counts how many times c appears in s, starting from position i. Print the count of 's' in "mississippi".

Show solution

C++

#include <iostream>
#include <string>

int count_char(const std::string& s, char c, std::size_t i = 0) {
    if (i == s.size()) return 0;
    return (s[i] == c ? 1 : 0) + count_char(s, c, i + 1);
}

int main() {
    std::cout << count_char("mississippi", 's') << '\n';
}

Output

Passing an index avoids creating a new substring at every step.

Practice exercise

Write a recursive int gcd(int a, int b) using Euclid's algorithm: gcd(a, 0) = a, otherwise gcd(a, b) = gcd(b, a % b). Print gcd(84, 36).

Show solution

C++

#include <iostream>

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

int main() {
    std::cout << gcd(84, 36) << '\n';
}

Output

The standard library has std::gcd in <numeric> (C++17).

Key takeaway#

Finished this lesson?

C++C++ Functions: Defining, Calling, Returning Values and DeclarationsLearn C++ functions: defining and calling them, parameters and return values, void functions, function declarations (prototypes), splitting code into header and source files, and writing small, single-purpose functions.Beginner10 min read C++C++ Scope and Lifetime: Local, Global and static VariablesUnderstand scope and lifetime in C++: block scope, local variables, shadowing, global variables and why to avoid them, static local variables that keep their value between calls, and dangling references to local variables.Beginner8 min read C++C++ std::vector: Dynamic Arrays Explained with ExamplesLearn std::vector, C++'s most used container: creating vectors, push_back and emplace_back, accessing with [] and at(), size and capacity, inserting and erasing, sorting, removing elements safely, vectors of strings and objects, and passing vectors to functions.Beginner12 min read

Practice: C++ functions exercises →

The two parts of every recursive function#

Factorial#

How it runs: the call stack#

More examples#

Power#

Sum of digits#

Reversing a string#

Binary search#

Fibonacci and repeated work#

Stack overflow#

Recursion or a loop?#

Common mistakes#

Practice#

Key takeaway#

Related lessons