C++ Recursion

In this C++ tutorial, you will learn how to write a recursion function with the help of example C++ programs.

C++ Recursion Function

A function is called a recursion function if a call is made to the same function from within the body of the function.

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) << "\n";
   cout << factorial(5) << "\n";
   cout << factorial(6) << "\n";
}

Output

24
120
720

Explanation

factorial(4) = 4 * factorial(3)
                                 \
                   factorial(3) = 3 * factorial(2)
                                                    \
                                      factorial(2) = 2 * factorial(1)
                                                                      \
                                                         factorial(1) = 1 * factorial(0)
                                                                            |
                                                                           (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) << "\n";
   cout << sumOfN(6) << "\n";
}

Output

10
21

Conclusion

In this C++ Tutorial, we learned how to use recursion technique with functions in C++.