TutorialKart.comIn this C++ tutorial, you will learn how recursion works, how to write a recursive function with a base case, and how recursive calls are evaluated. The examples include factorial, the sum of the first N natural numbers, and Fibonacci numbers.
What is Recursion in C++?
Recursion is a programming technique in which a function calls itself to solve a smaller version of the same problem. C++ supports recursive function calls in the same way it supports normal function calls.
A recursive function normally has two essential parts: a base case that stops further calls, and a recursive case that calls the function again with input that moves toward the base case.
return_type function_name(parameters) {
if (base_condition) {
return base_value;
}
return expression_using(function_name(smaller_input));
}Without a reachable base case, the function keeps creating new calls until the program runs out of stack space or otherwise fails.
How Recursive Function Calls Work in C++
Each recursive call gets its own function-call context. The current call waits while the next call is evaluated. Once the base case returns a value, the pending calls complete in reverse order.
For example, evaluating factorial(4) creates progressively smaller calls until factorial(0) reaches the base case. The returned values then flow back through the earlier calls.
C++ Recursion Examples
1. Factorial using Recursion
In the following example, we shall write recursion function instead of looping techniques, to find the factorial of a number.
C++ Program
#include <iostream>
using namespace std;
/*
* Recursion function to calculate factorial of a number
*/
int factorial(int n) {
if (n==0) {
return 1;
} else {
return n * factorial(n - 1);
}
}
int main() {
cout << factorial(4) << "\
";
cout << factorial(5) << "\
";
cout << factorial(6) << "\
";
}Output
24
120
720Explanation
factorial(4) = 4 * factorial(3)
\
factorial(3) = 3 * factorial(2)
\
factorial(2) = 2 * factorial(1)
\
factorial(1) = 1 * factorial(0)
|
(1)The condition n == 0 is the base case. It returns 1 and stops the recursion. For any larger value, the function multiplies n by the factorial of n - 1.
2. Find sum of first N numbers using recursion technique
In this example, we shall find the find the sum of first N natural numbers using recursion function.
C++ Program
#include <iostream>
using namespace std;
/*
* Recursion function to calculate
* sum of first n natural numbers
*/
int sumOfN(int n) {
if (n==1) {
return 1;
} else {
return n + sumOfN(n - 1);
}
}
int main() {
cout << sumOfN(4) << "\
";
cout << sumOfN(6) << "\
";
}Output
10
21Here, sumOfN(1) is the base case. For values greater than 1, the function adds the current value of n to the result of sumOfN(n - 1). For example, sumOfN(4) becomes 4 + 3 + 2 + 1.
3. Fibonacci Series using C++ Recursion
A recursive Fibonacci function is a common example because each result depends on two smaller subproblems. With the convention F(0) = 0 and F(1) = 1, every later value is F(n - 1) + F(n - 2).
#include <iostream>
using namespace std;
int fibonacci(int n) {
if (n <= 1) {
return n;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
int main() {
for (int i = 0; i < 7; i++) {
cout << fibonacci(i) << " ";
}
}Output
0 1 1 2 3 5 8This direct recursive version is useful for understanding recursion, but it repeats many calculations for larger inputs. In performance-sensitive code, an iterative solution or a method that stores previously computed values is usually more efficient.
Direct and Indirect Recursion in C++
The examples above use direct recursion, where a function calls itself directly. C++ can also use indirect recursion, where one function calls another function that eventually calls the first function again.
void functionA(int n);
void functionB(int n);
void functionA(int n) {
if (n > 0) {
functionB(n - 1);
}
}
void functionB(int n) {
if (n > 0) {
functionA(n - 1);
}
}Other descriptions, such as tail recursion or tree recursion, classify recursion by the position or number of recursive calls. These are useful patterns, but the central rule is the same: recursive calls must eventually reach a stopping condition.
Recursion vs Loop in C++
Many problems can be solved with either recursion or iteration. Recursion can make code easier to express when a problem is naturally defined in terms of smaller versions of itself, such as tree traversal or divide-and-conquer algorithms. A loop is often simpler when the task is a straightforward repetition.
Recursive calls also use stack space for each active function call. For very deep recursion, this extra stack usage can become a practical limitation. Choose recursion when it improves the structure of the solution, not simply as a replacement for every loop.
Common C++ Recursion Errors
- No base case: the function keeps calling itself without a defined stopping point.
- Base case is never reached: the recursive argument moves in the wrong direction or does not change.
- Incorrect boundary value: for example, a function may handle
n == 1but receive0or a negative number that it was not designed to process. - Excessive recursion depth: a very long chain of calls may exhaust available stack space.
- Repeated work: some recursive solutions, such as the basic Fibonacci example, recompute the same subproblems many times.
C++ Recursion Review Checklist
- Verify that every recursive path can reach a clear base case.
- Check that each recursive call moves the input closer to that base case.
- Test boundary inputs such as zero, one, and the smallest accepted value.
- Confirm that the return expression combines recursive results correctly.
- Consider whether recursion depth or repeated calculations could make the implementation inefficient.
Summary of Recursive Functions in C++
In this C++ Tutorial, we learned how to use recursion technique with functions in C++. A recursive function calls itself with a smaller problem, stops at a base case, and returns through the pending calls. We also examined factorial, summation, Fibonacci recursion, common recursion patterns, and mistakes to avoid.