C++: Recursion

Last updated: 2026-08-26

Recursion is a function calling itself.

Sounds strange — how can a function call itself? Won't it loop forever?

As long as you write a proper "exit condition," recursion works correctly — and can solve many problems that are hard to write with loops.

1. What is Recursion?

(1) 1.1 Recursion in Everyday Life

Core idea of recursion: Break a big problem down into smaller problems of the same type, until the problem is small enough to solve directly.

(2) 1.2 Two Conditions for Recursion

Every recursive function must have:

1. Base Case: The condition for exiting recursion (the simplest case)
2. Recursive Case: Breaking the problem into smaller problems of the same type

2. Recursion Example: Factorial

(1) 2.1 Definition of Factorial

n! = n × (n-1) × (n-2) × ... × 1

Recursive definition:

n! = n × (n-1)! （recursive case）
0! = 1 （base case）

▶ Example 1: Calculating Factorial with Recursion (Difficulty ⭐⭐)

#include <iostream>

// Recursive function：Calculate n factorial
long long factorial(int n) {
 // Base case
 if (n == 0) {
 return 1;
 }
 // Recursive case
 return n * factorial(n - 1);
}

int main() {
 int n;
 std::cout << "Please enter a non-negative integer: ";
 std::cin >> n;
 
 std::cout << n << "! = " << factorial(n) << std::endl;
 
 return 0;
}

Output:

Please enter a non-negative integer: 
! = 

Running result:

Please enter a non-negative integer: 5
5! = 120

(2) 2.2 Recursive Call Process (n=5)

factorial(5)
= 5 × factorial(4)
= 5 × 4 × factorial(3)
= 5 × 4 × 3 × factorial(2)
= 5 × 4 × 3 × 2 × factorial(1)
= 5 × 4 × 3 × 2 × 1 × factorial(0)
= 5 × 4 × 3 × 2 × 1 × 1 ← base case reached, starts returning
= 5 × 4 × 3 × 2 × 1
= 5 × 4 × 3 × 2
= 5 × 4 × 6
= 5 × 24
= 120

💡 Key point: During a recursive call, the function pauses at the line return n * factorial(n-1);, waiting for factorial(n-1) to return its result, then calculates n * result.

3. Recursion Example: Fibonacci Sequence

(1) 3.1 Definition of the Fibonacci Sequence

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2) （n ≥ 2）

Sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

▶ Example 2: Calculating Fibonacci Numbers with Recursion (Difficulty ⭐⭐)

#include <iostream>

int fibonacci(int n) {
 // Base case
 if (n == 0) {
 return 0;
 }
 if (n == 1) {
 return 1;
 }
 // Recursive case
 return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
 int n;
 std::cout << "Please enter a non-negative integer: ";
 std::cin >> n;
 
 std::cout << "F(" << n << ") = " << fibonacci(n) << std::endl;
 
 return 0;
}

Output:

Please enter a non-negative integer: 
F() = 

Running result:

Please enter a non-negative integer: 10
F(10) = 55

💡 Tip: This recursive implementation is very inefficient (it recalculates many values repeatedly). Later you'll learn how to optimize it with loops or memoization.

4. Recursion vs Loops

(1) 4.1 Comparison

(2) 4.2 Rewriting Factorial with a Loop

#include <iostream>

long long factorial(int n) {
 long long result = 1;
 for (int i = 1; i <= n; i++) {
 result *= i;
 }
 return result;
}

int main() {
 int n;
 std::cout << "Please enter a non-negative integer: ";
 std::cin >> n;
 
 std::cout << n << "! = " << factorial(n) << std::endl;
 
 return 0;
}

💡 Advice: If a problem can be easily solved with a loop, prefer loops. Recursion is suited for problems that are "naturally recursive" (e.g., tree traversal, quicksort).

5. The Pitfall of Recursion: Stack Overflow

(1) 5.1 What is Stack Overflow?

Every function call takes up space on the call stack. If recursion goes too deep (e.g., tens of thousands of levels), the call stack runs out, causing a Stack Overflow.

#include <iostream>

void infiniteRecursion() {
 infiniteRecursion(); // ❌ No base case, infinite recursion
}

int main() {
 infiniteRecursion();
 return 0;
}

Running result:

Segmentation fault (core dumped) // Linux

Or

Process finished with exit code -1073741571 // Windows: stack overflow

(2) 5.2 How to Avoid Stack Overflow?

1. Ensure there is a base case, and that the base case can definitely be reached
2. Control recursion depth (e.g., rewrite with a loop)
3. Use tail recursion optimization (covered later, but not all compilers support it)

6. Practice: Tower of Hanoi

▶ Example 3: Tower of Hanoi Recursive Solution (Difficulty ⭐⭐⭐)

Problem: There are 3 pegs (A, B, C) and n disks. Initially, all disks are on peg A (smaller ones on top, larger ones on bottom). Move all disks to peg C, moving only one disk at a time, and never placing a larger disk on top of a smaller one. Output the steps.

Recursive approach:

1. Move n-1 disks from A to B (using C)
2. Move the nth disk from A to C
3. Move n-1 disks from B to C (using A)

#include <iostream>

void hanoi(int n, char from, char to, char aux) {
 if (n == 1) { // Base case：Only one disk
 std::cout << "Move disk 1 from " << from << " to " << to << std::endl;
 return;
 }
 // Recursive case
 hanoi(n - 1, from, aux, to); // Move n-1 disks from source to auxiliary
 std::cout << "Move disk " << n << " from " << from << " to " << to << std::endl;
 hanoi(n - 1, aux, to, from); // Move n-1 disks from auxiliary to target
}

int main() {
 int n;
 std::cout << "Please enter number of disks: ";
 std::cin >> n;
 
 std::cout << "========== Tower of Hanoi Steps ==========\n";
 hanoi(n, 'A', 'C', 'B');
 
 return 0;
}

Output:

Move disk 1 from  to 
Move disk  from  to 
Please enter number of disks: 
========== Tower of Hanoi Steps ==========

Running result (n=3):

========== Tower of Hanoi Steps ==========
Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

💡 Tip: The recursive solution for the Tower of Hanoi is very elegant, but if you try to write it with loops, you'll find it very difficult. That's the power of recursion.

7. Optimizing Recursion: Memoization

(1) 7.1 The Problem: Naive Recursion is Inefficient

The earlier Fibonacci recursive function recalculates many values:

fibonacci(5)
= fibonacci(4) + fibonacci(3)
= (fibonacci(3) + fibonacci(2)) + (fibonacci(2) + fibonacci(1))
= ...

fibonacci(2) is calculated 5 times! When n is large, efficiency is extremely low.

(2) 7.2 Solution: Memoization

Store previously calculated results and look them up directly next time.

#include <iostream>
#include <vector>

std::vector<long long> memo; // Memoization array

long long fibonacci(int n) {
 if (n == 0) return 0;
 if (n == 1) return 1;
 
 if (memo[n] != -1) { // If already calculated, return directly
 return memo[n];
 }
 
 memo[n] = fibonacci(n - 1) + fibonacci(n - 2); // Calculate and store
 return memo[n];
}

int main() {
 int n;
 std::cout << "Please enter a non-negative integer: ";
 std::cin >> n;
 
 memo.resize(n + 1, -1); // Initialize memoization array
 
 std::cout << "F(" << n << ") = " << fibonacci(n) << std::endl;
 
 return 0;
}

💡 Tip: C++11 introduced std::unordered_map, which can make memoization even more convenient.

❓ FAQ

📖 Summary

• Recursion is a function calling itself
• Recursion must have two conditions: a base case (exit) and a recursive case (continue)
• The advantage of recursion is concise code; the disadvantages are low efficiency and potential stack overflow
• For problems easily solved with loops, prefer loops
• Recursion is suited for problems that are "naturally recursive"

📝 Exercises

1. Basic (Difficulty ⭐): Write a recursive function int sumDigits(int n) that calculates the sum of the digits of an integer.

Input: 123
Output: 1 + 2 + 3 = 6

(Hint: recursive case sumDigits(n) = n % 10 + sumDigits(n / 10), base case n == 0)

2. Intermediate (Difficulty ⭐⭐): Write a recursive function int power(int base, int exp) that calculates base raised to the power of exp.

Input: power(2, 5)
Output: 32

(Hint: recursive case power(b, e) = b * power(b, e-1), base case returns 1 when e == 0)

3. Challenge (Difficulty ⭐⭐⭐): Use recursion to solve the "climbing stairs" problem:
4. Suppose you need to climb n stairs, and you can climb 1 or 2 stairs at a time
5. How many different ways are there to climb?
6. (Hint: This is another version of the Fibonacci sequence — f(n) = f(n-1) + f(n-2))
7. Optimize your recursive function with memoization

• Recursive function: calls itself, decomposes problems then combines results
• Three elements of recursion: termination condition, recursive call, combining results
• Fibonacci recursion is a classic beginner example
• Recursion vs loops: recursion has concise code, loops have better performance
• Tail recursion can be optimized by the compiler into a loop

12. 🚀 Next Step

Now that you've learned recursion, let's move on to Function Overloading and Default Parameters (Lesson 13) — techniques to make functions more flexible and easier to use!

Web-Tutorial Tech Team

A team of developers maintaining programming tutorials. Each tutorial is written and reviewed by developers with expertise in that field. We work to keep our content accurate and reliable — if you spot an issue, please let us know.

About Us