Recursion in C++ Programming

The process of calling a function by itself is called recursion. Recursion is frequently used in mathematics to solve a complex problem by dividing it into simpler problem of same type. Similarly in programming, it can be used to divide a larger problem many simpler problem and solving them individually. The general format of a recursive function is:

returntype recursive_func ([argument list])
{
    statements;
    ... ... ...
    recursive_func ([actual argument])
    ... ... ...
}

Flowchart for recursion

flowchart of recursion in c++ programming

While using recursion, we need to define a proper exit condition to prevent infinite recursive call. Recursion uses a stack to save the content of current function before making a recursive call.

Types of recursion

Direct Recursion
Indirect Recursion

Direct Recursion

A function when it calls itself directly is known as Direct Recursion.

For example,

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

Here, inside factorial(int n), it directly calls itself as n*factorial(n-1). This is direct recursion.

Indirect Recursion

A function is said to be indirect recursive if it calls another function and the new function calls the first calling function again.

For example,

int func1(int n)
{
    if (n<=1)
        return 1;
    else
        return func2(n);
}

int func2(int n)
{
    return func1(n-1);
}

Here, recursion takes place in 2 steps, unlike direct recursion.

First, func1 calls func2
Then, func2 calls back the first calling function func1.

Example #1: C++ program print first n fibonacci number using recursion.

#include<iostream>
using namespace std;

int fibo(int num)
{
    if(num==1||num==2)
        return 1;
    else
        return (fibo(num-1)+fibo(num-2));  // recursive call
}

int main()
{
    int i,n;
    cout<<"Enter the required term: ";
    cin>>n;
    cout<<"First "<<n<<" fibonacci numbers are"<<endl;
    for (i=1; i<=n; i++)
        cout<<fibo(i)<<endl;
    return 0;
}

In this program, concept of recursion is used to generate fibonacci series since a term is represented as the sum of two smaller terms. Fibonacci series is a series where a term is generated by adding two previous term of that series. Mathematically,

t_n = t_n-1 + t_n-2

Here,

The number of fibonacci terms to be generated is taken from the user and stored in variable n.
A for loop is used to loop through the number to be generated which is sent to the function fibo. This function is used to calculate and return fibonacci series.
Inside fibo, if the term-number is 1 or 2, it returns 1. This is because, the first two terms of fibonacci series are both 1. The printed values are 1,1.
Then the next term-number 3 is passed onto fibo function, since it’s not 1 or 2, the next term in the series is calculated by taking fibo(n – 1) + fibo(n – 2), where n = 3. This calculates the last two terms in the fibonacci series. This is equivalent to fibo(2) + fibo(1), which results in 1 + 1 = 2.
This recursive loop goes on finally printing the series as 1, 1, 2, 3, 5…

Output

Enter the required term: 7
First 7 fibonacci numbers are
1
1
2
3
5
8
13

Disadvantages of Recursion

Recursive programs are generally slower than non recursive programs. This is because, recursive function needs to store the previous function call addresses for the correct program jump to take place.
Requires more memory to hold intermediate states. It is because, recursive program requires the allocation of a new stack frame and each state needs to be placed into the stack frame, unlike non-recursive(iterative) programs.