Learn C++ from Scratch/

...

/

Recursion

Recursion

Learn about recursion using different examples.

We'll cover the following...

Introduction

Recursion is a programming technique in which a function calls itself. If the problem can be divided into smaller versions, the function can call itself with these smaller subproblems.

The concept of dividing a problem into smaller versions is not uncommon. We have encountered it several times in school math, for instance, when calculating the factorial.

Factorial of a number

Let’s take an example. A factorial of a number N, denoted by N!, is the product of all positive integers less than or equal to N. 4! would be 4 x 3 x 2 x 1.

Can we represent factorial in terms of a smaller version of itself? Yes! because 4! is simply 4 x 3!

Each recursive call tackles a simpler version of the original problem. This process continues until a base case is reached, which is a simple condition that can be solved directly without further recursion. What do you think is the base case of factorial? A factorial of 1 and 0 is 1.

Let’s look at the following code that calculates the factorial of the number 4.

Press + to interact
C++
#include <iostream>
using namespace std;
int factorial(int n)
{
   if(n == 1 || n == 0)      // If n equals 1 or 0 we return 1 
   {
      return 1;
   }
   else
   {
      return n*factorial(n-1);    // Recursively calling the function if n is other then 1 or 0
   }
}
int main() {
  int temp = factorial(4);    // Computing the factorial of 4
  cout << "The value of the factorial computed is: "<< temp << endl;
  return 0;
}

Explanation

In the above code, we calculate the factorial of a given number, i.e., 4 using recursion. The factorial function takes an integer n as an argument and returns the factorial of n. If n is 1 or 0, the function returns 1, which is the base case. Otherwise, it recursively calls itself (the function) with n-1 as a parameter and multiplies the result received by n. In the main function, we call the factorial function, and then print the result. ...