C++ Basics · Chapter 10
Recursion in C++: Structure With Examples
Learn how functions can call themselves to solve complex problems elegantly. Master the base case, recursive case, and call stack with practical examples.
What you'll learn
- What recursion is and how it works in C++
- The concepts of base case and recursive case
- How to write recursive functions for common problems
- How the call stack works during recursion
- Common pitfalls and when to use recursion
1What 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.
The recursive mindset
Think of recursion like Russian nesting dolls. You open one doll to find a smaller one inside, and you keep going until you reach the smallest doll – the base case. Then you close them all back up, returning values along the way.
2Structure of a recursive function
Every recursive function must have two essential parts:
- Base Case: A condition that ends the recursion (stops the function from calling itself forever)
- Recursive Case: The part where the function calls itself with a smaller or simpler version of the problem
General pattern:
cpp
returnType functionName(parameters) { if (base_case_condition) return base_value; else return functionName(smaller_problem); }
The base case is mandatory
Without a base case, the function will call itself indefinitely, leading to a stack overflow crash. Every recursive function must have at least one base case.
3Example 1: Factorial (n!)
The factorial of a number n is defined as: n! = n × (n-1) × (n-2) × ... × 1, and 0! = 1 (base case).
cpp
int factorial(int n) { if (n == 0) return 1; // base case else return n * factorial(n - 1); // recursive case }
Usage:
cpp
int main() { int n = 5; cout << "Factorial of " << n << " is " << factorial(n); return 0; }
OutputFactorial of 5 is 120
4How recursion works: the 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, in reverse order.
For factorial(3):
factorial(3)
-> 3 * factorial(2)
-> 2 * factorial(1)
-> 1 * factorial(0)
-> 1 (base case)
<- returns 1 * 1 = 1
<- returns 2 * 1 = 2
<- returns 3 * 2 = 6
-> 3 * factorial(2)
-> 2 * factorial(1)
-> 1 * factorial(0)
-> 1 (base case)
<- returns 1 * 1 = 1
<- returns 2 * 1 = 2
<- returns 3 * 2 = 6
Stack overflow danger
Each recursive call uses memory on the stack. If recursion goes too deep (thousands of calls), the stack can overflow. This is a common limitation of recursion.
5Example 2: Fibonacci sequence
The Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, ...
fib(0) = 0fib(1) = 1fib(n) = fib(n-1) + fib(n-2)for n > 1
cpp
int fib(int n) { if (n == 0) return 0; if (n == 1) return 1; return fib(n - 1) + fib(n - 2); }
cpp
cout << fib(7) << endl;
Output13
Inefficiency warning
This recursive Fibonacci implementation is not efficient for large n due to repeated calculations. fib(5) calls fib(3) multiple times. We will discuss optimizations like memoization in later chapters.
6Example 3: Sum of digits
This function recursively calculates the sum of digits of a number. For n = 123, it returns 1 + 2 + 3 = 6.
cpp
int sumOfDigits(int n) { if (n == 0) return 0; return n % 10 + sumOfDigits(n / 10); }
cpp
cout << sumOfDigits(123) << endl;
Output6
7Example 4: Power function
Compute a^b (a raised to the power b) using recursion.
cpp
int power(int a, int b) { if (b == 0) return 1; return a * power(a, b - 1); }
cpp
cout << power(2, 5) << endl;
Output32
8Example 5: Tower of Hanoi
The Tower of Hanoi is a classic recursion problem. Move n disks from rod A to rod C using rod B as auxiliary.
cpp
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); }
cpp
hanoi(3, 'A', 'B', 'C');
OutputMove 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
9When should you use recursion?
Use recursion when
- The problem can be broken into smaller, similar subproblems
- You can define a clear base case
- The problem involves tree traversal, divide-and-conquer, backtracking, or combinatorics
- The recursive solution is more elegant and readable than the iterative one
Avoid recursion when
- The iterative solution is simpler and more efficient
- The recursion depth could be very large (risk of stack overflow)
- Performance is critical and recursion adds unnecessary overhead
10Common mistakes to avoid
1. Missing a base case
This leads to infinite recursion and eventually a stack overflow crash. Always define at least one base case.
2. Not making progress toward the base case
Each recursive call must bring the problem closer to the base case. If the problem does not get smaller, recursion never ends.
3. Not returning the recursive result
If your function returns a value, make sure the recursive case returns the result of the recursive call.
4. Using recursion when iteration is better
Problems like Fibonacci without memoization are better solved with loops or optimized algorithms.
11Mini exercises
Try these yourself
- Write a recursive function to calculate the sum of the first n natural numbers.
- Create a recursive function to check if a string is a palindrome.
- Implement
gcd(a, b)using recursion (Hint: use Euclid's algorithm:gcd(a, b) = gcd(b, a % b)). - Use recursion to reverse an array in place.
Hint: For the palindrome check, compare the first and last characters, then recurse on the substring between them.
12Quiz yourself
Recursion Quiz
Question 1 of 10
Coming up next
Structures in C++
Learn how to group related data using struct, and how this leads to more advanced data types like linked lists and objects.
