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;
}
...