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.

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

Example – 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)

Example – Find sum of first N numbers

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++.