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 of itself is not uncommon, and we have come across it several times in school math, for instance.

Factorial of a number

Let’s take an example. A factorial of a number N, denoted by N!, is a 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 is 1.

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

Press + to interact
#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.

Let’s step through what happens in our function when we call num = factorial(4). ...