Recursive Functions in C++ Tutorial

In this C ++ tutorial, we will learn about the famous and important art of recursion, and you will understand the programmers joke: "To know recursion, you have to know recursion."

Recursive Function

In the programs we did during our tutorials, we have repeatedly called one function inside another. Recursion has to do with calling a function.

But it calls a particular function. The recursive function is nothing more than the calling function itself.

Let's create a function that displays a message on the screen and then invokes itself:

#include <iostream>
using namespace std;

void recur()
{
    cout<<"Progressive C++ course"<<endl;
    recur();
}

int main()
{
    recur();
    return 0;
}

The following happens:

Recursivity in C++

And it's quite simple to understand ... we invoke recur(), it displays a message on the screen and ... calls it again, which when called, displays a message on the screen ... then calls it again, which displays a message ... and so it goes indefinitely into infinity and beyond.

To stop, I had to give a Control + C, otherwise it was running forever.

Using recursion with functions

Thus, recursive functions are not so useful.
To learn how to use them correctly, we need a kind of counter, just as we did with loopings.

Let's make recur() receive an integer, and will only call it if that integer is greater than 0:

#include <iostream>
using namespace std;

void recur(int counter)
{
    if(counter>0){
        cout<<"Progressive C++ course"<<endl;
        recur(counter-1);
    }
}

int main()
{
    recur(5);
    return 0;
}

If the received number is greater than 0, we display the message and call recur() again, but we will pass a smaller argument, subtracted from 1, because this function has already executed once.

Thus, if you do recur (5), it will run the function 5 times only:

First we called recur (5), displayed the message and called recur (4).
recur (4) displays the message and calls recur (3).
recur (3) displays the message and calls recur (2).
recur (2) displays the message and calls recur (1)
recur (1) displays the message and calls recur (0).

When we call recur (0), nothing is done and no function is called anymore, ending the recursion.

recur(0) is the base case where it should stop.
Let's practice and see how to apply the function recursion technique in C ++?

Sum with recursion

Let's call sum(n) the sum of the value n.

For example:
sum (5) = 5 + 4 + 3 + 2 + 1

But sum(4) = 4 + 3 + 2 + 1

That is: sum (5) = 5 + sum (4)

We can generalize by doing:
sum (n) = n + sum (n-1)

See there's a recursion there. sum() is calling sum(), with an argument decremented by 1, but it is. When the argument is 1, it must return 1 (since sum of 1 is 1) and stop calling the summation function.

Our code is:

#include <iostream>
using namespace std;

int sum(int num)
{
    if(num==1)
        return 1;
    else
        return num+sum(num-1);
}

int main()
{
    int num;

    cout<<"Summation of: ";
    cin>> num;

    cout<<"It's: "<<sum(num)<<endl;
}

sum (1) is the base case, where we solve things manually, without using recursion, only returning 1.
Cool. huh?

Factorial with recursion

Let's call fat(n) the factorial of the value n.
fat(n) = n * (n-1) * (n-2) * ... 3 * 2 * 1

That is:
fat(n) = n * fat(n-1)

Do you agree?
We have a logic with recursion. The fat() function calling fat().
It should call until it gets to argument 1, and factorial 1 is 1.

See how our code looks:

#include <iostream>
using namespace std;

int fat(int num)
{
    if(num==1)
        return 1;
    else
        return num*fat(num-1);
}

int main()
{
    int num;

    cout<<"Factorial of: ";
    cin>> num;

    cout<<"It's: "<<fat(num)<<endl;
}

fat(1) is the base case, where we do not invoke recursion, but directly return a value.

Recursive Fibonacci Sequence

Finally, our good and old Fibonacci.
Recall here what the Fibonacci series is.

Basically, the first two terms are 0 and 1. These are our base cases.
The third term, onwards, is the sum of the previous two. That is:
F (1) = 0
F (2) = 1
F (3) = F (2) + F (1) = 1 + 0 = 1
F (4) = F (3) + F (2) = 1 + 1 = 2
F (5) = F (4) + F (3) = 2 + 1 = 3
F (6) = F (5) + F (4) = 3 + 2 = 5
F (7) = F (6) + F (5) = 5 + 3 = 8
...

That is, the formula for finding the term 'n' is:
F(n) = F n-1) + F(n-2)

Do you agree ?

When the argument of our function receives the value 2, that is, when we want to know the value of F (2), the function must return 1. And when we want to know the value of F (1), the function must return 1.

We should not calculate using the recursion formula because it would be calculated:
F (2) = F (1) + F (0)
F (1) = F (0) + F (-1)

And there is no need to calculate F (0) when more F (1).

So our code looks like this:

#include <iostream>
using namespace std;

int fibo(int num)
{
    if(num==1)
        return 0;
    else
        if(num==2)
            return 1;
        else
            return fibo(num-1)+fibo(num-2);
}

int main()
{
    int num;

    cout<<"Term: ";
    cin>> num;

    cout<<"It's: "<<fibo(num)<<endl;
}

Test. Calculate 19th term of the sequence, it's 2584. Did it work?

Recursion x Iteration

Recursion is a tool that can save our lives as a programmer often because the idea behind 'a function call itself' is very simple, useful and can be employed in a variety of repetitive problems that follow certain standards, such as the above examples.

But it is important to note that everything that is done with recursion is possible without.
More specifically, all you can do with recursion, you can use iteration, with loopings in C++.

When we invoke a function, much happens under the cloth. A lot of memory is allocated to the parameters and arguments, the address and function code are allocated, stored and accessed at predefined locations in memory, the place where it was invoked is also saved, to return there when execution is finished, and so on.

This results in one thing: recursion is slower than iteration. In general.
So why use recursion? Simple, some repetitive logic problems are much simpler to solve using recursion.

Although it is slower and less efficient, you can compensate for this by solving / building an algorithm in less time using recursion. You can easily figure out how to solve a problem by applying recursion, and sometimes iteration can be trickier to program.

The secret of recursion is that it makes a problem a smaller one but similar problem.

Instead of solving func(n), you just need to solve for func(n-1), then func(n-2) .... func(3) ... func(2) ... and usually to solve things with small arguments, we know how to solve easily. Recursiveness does this: It makes a problem a little problem, with the exact same logic.

We will again use recursion to calculate, for example, characters in the string section and also with lists.

C++ Exercise

Create a function to calculate the factorial of a number using recursion. Choose a very large number that takes a few seconds from your machine. See how long it took to do the operation.
Now create another function to calculate the same factorial, but using iteration (factorial with C++ loopings), calculate the same number. Write down the time.

Now share with us in the comments: what number did you calculate and how long did each function take to calculate?

Progressive C++