Recursive Function

0 finlaybogner685 November 13, 2020

Recursion in programming is a technique for defining a problem in terms of one or smaller versions of the same problem. The solution to the problem is built on the results from the smaller versions. A recursive function is one that calls itself directly or indirectly to solve a smaller version of its tasks until a final call which does not require a self-call. Thus, the function is called a recursive function if it calls to itself and recursion is a process by which a function calls itself repeatedly until some specified condition will be satisfied. This process is used for repetitive computations in which each action is stated in terms of the previous results.

Let’s look at one example to make clear concepts on recursive function.

#include <iostream>
using namespace std;

long int factorial(int n){
    if(n==1)
        return 1;
    else
        return (n * factorial(n - 1));
}

int main(){

    int num;
    cout << "Enter a number : ";
    cin >> num;

    cout << "The factorial is " << factorial(num) << endl;

    return 0;
}

The output of the above program is:

Enter a number : 5
The factorial is 120

Here, when 5 is passed in functionfactorial(), the control goes to function definition. Within the body of function definition of factorial, the same function is again called by using the statement n*factorial(n-1) i.e. to find the factorial of 5, it is expressed in terms of 5*4!. Its logic is as

5!
5 * 4!
5 * 4 * 3!
5 * 4 * 3 * 2!
5 * 4 * 3 * 2 * 1!
5 * 4 * 3 * 2 * 1

When factorial() receives argument 1, it returns 1 such thta the value of 2! is calculated as 2 * 1! = 2 * 1 = 2.

When the factorial of 2 is calculated of , then factorial of 3 is calculated as 3 * 2! = 3 * 2 = 6. Then 4! = 4 * 3! = 4 * 6 = 24 and finally 5! = 5 * 4! = 5 * 24 = 120 is calculated.

Here the arguments are passed in order 5, 4, 3, 2, 1 in function factorial() but the calculation is done in reverse order i.e 1! is computed first and 5! is computed at last. This process Last In First Out is called stack operation. Thus, recursive functions use stack operations.

Let’s look at another program to generate the Fibonacci series.

#include <iostream>
using namespace std;

long int fib(int n){
    if(n==1)
        return 0;
    else if(n==2)
        return 1;
    else
        return (fib(n-1)+fib(n-2));
}

int main(){

    int terms,i;
    cout << "How many terms do you want? : ";
    cin >> terms;

    for (i = 1; i <= terms; i++)
        cout << "\t" << fib(i);

    return 0;
}

The output of the above program is:

How many terms do you want? : 10
        0       1       1       2       3       5       8       13      21      34