Recursion

Recursive programming is a procedure in which a method calls itself, so that a problem is solved more and more with each method call. This continues until the problem is reduced to a very simple case.

Some tasks in computer science can be solved well by reducing a large problem step by step to smaller and smaller problems of the same kind until simple (trivial) solutions arise . From this finally the solution of the original large problem is put together.

Syntax

return_type function_name(type parameter) { 
    // code to be executed 
    return function_name(type parameter)
}

Example: factorial

This is a simple C++ program that implements a recursive function factorial to calculate the factorial of a given positive integer number.

The function factorial takes an integer number as an argument and returns the factorial of that number. If the number is less than 2, the function returns 1, which is the base case of the recursion. Otherwise, the function returns the number multiplied by the result of the factorial function called with number - 1. This causes the function to be called repeatedly with smaller values of number until the base case is reached.

In the main function, the factorial of 8 is calculated by calling the factorial function with the argument 8 and the result is printed to the console using the cout statement.

#include <iostream>
using namespace std;

int factorial(int number) {
    if (number < 2) {
        return 1;
    } else {
        return number * factorial(number - 1);
    }
}

int main() {
    cout << "factorial of 8 is " << factorial(8);

    return 0;
}

Output

factorial of 8 is 40320

Example: fibonacci

This is a simple C++ program that implements a recursive function fibonacciAlgorithm to calculate the n-th number in the Fibonacci sequence.

The function fibonacciAlgorithm takes an integer number as an argument and returns the n-th number in the Fibonacci sequence. If the number is 0 or 1, the function returns number, which is the base case of the recursion. Otherwise, the function returns the sum of the results of two recursive calls to fibonacciAlgorithm with the arguments number - 1 and number - 2. This causes the function to be called repeatedly with smaller values of number until the base case is reached.

In the main function, the 10th number in the Fibonacci sequence is calculated by calling the fibonacciAlgorithm function with the argument 10 and the result is printed to the console using the cout statement.

##include <iostream>
using namespace std;

int fibonacciAlgorithm(int number) {
    if (number == 0 || number == 1) {
        return number;
    } else {
        return fibonacciAlgorithm(number - 1) + fibonacciAlgorithm(number - 2);
    }
}

int main() {
    cout << "fibonacci number of the number 10 is " << fibonacciAlgorithm(10);

    return 0;
}

Output

fibonacci number of the number 10 is 55