Recursion

Posted on June 17, 2023  •  4 minutes  • 779 words

Recursion is a programming concept where a function calls itself during its execution. In C++, recursion allows you to solve complex problems by breaking them down into smaller, simpler versions of the same problem.

To implement recursion in C++, you typically define a function that calls itself until it reaches a base case, which is a condition that terminates the recursive calls.

For Example, in order to print n numbers, the base concept is output the a given number and the condition is to print the number is less than or equal to the given limit say n. This is achieved by a basic for loop.

void printNNumbers(int n)
{
    for(int i=n; i >=1 ; i--)
    {
        std::cout << i << " ";
    }
}

Here we can simply divide the problem into simple way

1. Create a function that simply accept the number and print the given number.

void printNumber(int n)
{
    std::cout << n << " ";
}

2. We need to print the number only if the given number is greater than One.

void printNumber(int n)
{
    if(n > 1)
    {
        std::cout << n << " ";
    }
}

3. if we pass the number 10 to this function it is simply print the number and if the number is 0 then it will not print the number

4. So we can simply call the same function after the print statement with n-1

void printNumber(int n)
{
    if(n > 1)
    {
        std::cout << n << " ";
        printNumber(n-1);
    }
}

Then the Ouput of printNumber(10) will be

10 9 8 7 6 5 4 3 2 1 

Each recursive call works on a smaller subset of the problem, bringing it closer to the base case. Once the base case is reached, the function starts returning values to the previous recursive calls, eventually leading to the final result.

Then if we want to reverse the result we need to call the function before print statement.

void printNumber(int n)
{
    if(n > 1)
    {
        printNumber(n-1);
        std::cout << n << " ";
    }
}

1 2 3 4 5 6 7 8 9 10 

Example 2:

Here’s a secoond example to illustrate recursion in C++. Let’s consider the factorial function, which calculates the product of all positive integers from 1 to a given number n. The factorial of n is denoted as n!.

Solution with forloop

int factorial(int n)
{
    int fact =1;
    for(int i = n; i >=1; i--)
    {
        fact = fact *i;
    }
    return fact;
}

Solution with recursion

Base condition is 1! = 1 and 0! = 1 then

1. Create a simple function called fact

int fact(int n)
{
    if(n == 1)
    {
        return 1;
    }
    // logic
}

2. Simply return the multiplied result of given number (n) and (n-1)

int fact(int n)
{
    if(n == 1)
    {
        return 1;
    }
    // logic
    int ret = n * fact(n-1);
    return ret;
}

int main() {
  int num = 5;
  int result = fact(num);
  std::cout << "Factorial of " << num << " is " << result << std::endl;
  return 0;
}

In this example, the factorial function takes an integer n as input. It checks if n is either 0 or 1, which are the base cases where the factorial is known to be 1. Otherwise, it makes a recursive call to itself with n - 1, multiplying the current value of n with the factorial of (n-1). The recursive calls continue until the base case is reached, and then the results are returned back to the previous calls until the final result is obtained.

When you run the program, it will output:

Factorial of 5 is 120

This example demonstrates how recursion can be used to solve the factorial problem by dividing it into smaller subproblems and leveraging the results of previous recursive calls.

Full Code

#include<iostream>
void printNumber(int n)
{
    if(n > 1)
    {
        printNumber(n-1);
    }

    std::cout << n << " ";
}

void printNumbers(int n)
{
    for(int i=n; i >=1 ; i--)
    {
        std::cout << i << " ";
    }
}

int fact(int n)
{
    if(n == 1)
    {
        return 1;
    }
    int ret = n * fact(n-1);
    return ret;
}

int factorial(int n)
{
    int fact =1;
    for(int i = n; i >=1; i--)
    {
        fact = fact *i;
    }
    return fact;
}

int main()
{
    int n = 5;
    printNumbers(n);
    std::cout << std::endl;
    printNumber(n);
    std::cout << "\nFactorial of " << n << " is :" << factorial(n) << std::endl;
    std::cout << "Factorial of " << n << " is :" << fact(n);
    return 0;
}

5 4 3 2 1
1 2 3 4 5
Factorial of 5 is 120
Factorial of 5 is 120