Function Recursion

Procedural recursive functions

Let's analyze the following program:

#include <iostream>
using namespace std;
void show(int n) {
    if (n != 0) {
        cout << n;
display(n - 1);
    }
}
int main () {
    display(3);
    return 0;
}

We notice that when defining the function, in its body, it calls itself. This is the main way in which achieves recusivity. We'll see another way later, when a function ends up calling itself not directly but through another function (indirect recursion).

Let's analyze the effect of this program. Most people give the correct answer: 321 is displayed

We also analyze the following example:

void show(int n) {
if (n != 0) {
    cout << n;
    display(n - 1);
    cout << n;
    }
}

The above context remains, I only modified the function by adding a display statement after the autocall.

In this case, most people don't give the correct answer :D . Here's a detailed, step-by-step analysis step, of what happens:

A symmetry is therefore observed, i.e. first 321 is displayed, then 123, these being the values ​​of the parameters that they arrive on the stack, first in the order they were passed, then in the reverse order. We will also add the else branch to the function, where we print n. That is:

void display(int n) {
	if (n!=0) {
		cout << n;
		display(n-1);
		cout << n;
	} else
		cout << n;
}

Taking into account the detailed analysis above, it also ends up printing something on the else branch, i.e. 0. This this is done after the ascent in the stack is finished and before the descent begins, i.e. after the traverse the parameters in one order and before starting to traverse them in reverse. Thus we have: 3210123.

We can draw the conclusion from now on: through recursion we have the possibility of traversing a data set of two times: once through the instructions on the branch with the autocall, found before the autocall, then through those on the branch with the autocall located after the autocall, in reverse order of parameter values ​​compared to the first one browsing. Between the two traversals, what is on the else branch is executed only once.

Before drawing further conclusions, let's analyze what also happens when the function looks like below:

void display(int n) {
	cout << n;
	display(n-1);
}

It prints: 3210 - 1 - 2 - 3 - 4 - 5 ...

Most people say it cycles endlessly, and in a way it's true. On closer inspection, holding taking into account that new memory is allocated on the stack with each autocall, and noting that no autocall ever does not end, we conclude that memory is never freed and is always allocated. Then when the space reserved for the stack area runs out the program ends with an error during execution (Stack overflow error).

Care must therefore be taken to condition the autocall and ensure that we arrive at some point where the parameters make autocall is no longer executed, at which point the return, descent into the stack begins.

There is even a theorem that states that every recursive writing corresponds to a repetitive one and vice versa.

Thus, we can say that, in general, a recursive function is of the form:

function (parameters) {
if (condition) {
	Instructions 1
	Function (next parameter values)
	Instructions2
} else
	Instructions3
}

• Therefore, only instructions1 are executed several times, as long as the parameter values ​​do the true condition.
• It then executes statement3 only once, when the parameter values ​​do the false condition
• Statement2 is then executed, the same number of times as statement1, but in order inverse of the parameter values ​​as in the case of executions of instructions1.

In other words, linearizing, we have:

Instructions 1
Instructions 1
...
Instructions 1
Instructions3
Instructions2
Instructions2
...
Instructions2

We introduced the key elements from a recursive function: that the self-call must be conditional, that we can put instructions on the branch with the autocall (before and after it) or on the other branch. But we can we add instructions right before or after the decision. A good exercise in understanding recursion is to now consider what effect a display(3) call has on the function below:

void display(int n) {
cout << n;
if (n != 0) {
cout << n; //2
display(n - 1);
cout << n;//3
} else
cout << n; //4
cout << n; //5
} 

The effect is to display the following string of values: 3 3 2 2 1 1 0 0 0 1 1 2 2 3 3.

So, the statement 1 being before the if it will be executed at each entry in the so function and in the event that continue on the branch with the self-call but also in the case of going to the other branch. Therefore, if the before the self-call on the branch with the self-call is executed three times, the one before the if is executed once in addition. The values ​​in bold are what she displays: 3 3 2 2 1 1 0 0 0 1 1 2 2 3 3.

Symmetrically, statement 5 is executed at each exit from the function, regardless of the branch on which the code was executed, so it is also executed 4 times. The values ​​in bold are what she displays: 3 3 2 2 1 1 0 0 0 1 1 2 2 3 3.

Exercises and solved problems

1. Write a recursive function that displays the digits of a number in the order they appear, separated by a space-bar. For example, a call to f(352) will have the effect of displaying: 3 5 2.

void f(int n) {
	if (n != 0) {
		f(n / 10);
	cout << n % 10 << " ";
	}
}

Digit by digit traversal is done by self-call with the value obtained by removing the last digit. Since the algorithm standard scrolling digits of a number get them from the right, we decide to display after autocall the current (last) digit, thus printing them in order from left to right.

2. Write a recursive function with parameter a number n that displays the even values ​​first in descending order less than or equal to n, on the same line, separated by a space, then display ascending, on next row odd values ​​less than or equal to n. Only nonzero nautal values ​​are printed. Of for example, an f(8) call should have the effect:

8 6 4 2
1 3 5 7

void f(int n) {
if (n != 0) {
	if (n % 2 == 0)
		cout << n << " ";
	f(n - 1);
	if (n % 2 != 0)
		cout << n << " ";
} else
	cout << "\n";
}

We first traverse the numbers from n to 1 in descending order but decide to display only the even ones, with spaces between them. On return we display the odd ones, also with space between them, so we get them in order breeding On the else branch, whose code is executed only once, in the middle, we will print an enter.

3. Consider the following code sequence:

cin >> n;
i = 1;
while (i <= n) {
	cout << i;
	i++;
}

Write a program that accomplishes the same thing through a recursive function.

#include <iostream>
using namespace std;
int n;
void f(int i) {
	if (i <= n){
	cout << i;
	f(i + 1);
	}
}
int main () {
	cin >> n;
	f(1);
return 0;
}

The purpose of this exercise is to show a way of "translating" from a repetitive code, easier to write, into a recursive one.

We notice that:

• The repetition counter - i - is parameter to recursion (variable whose value value changes from one autocall to another);
• The update mode for the counter is related to the self-call mode:

  i++ f(i + 1);

• Condiția de la repetiție este aceeași cu cea de la condiționarea autoapelului;
• The initialization of the counter (i = 1) corresponds to the initial call mode ( f(1) ).
• The statement subordinate to the repetition is the one that is intended to be executed at each autocall (cout << i).

When teaching recursion people ask the question: why do I have to learn how to do recursive if do i have the equivalent repetitive variant? In addition, it is observed that the recursion also consumes some time with stack memory allocation/deallocation.

The main (and decisive) reason why recursion is extremely important is given by the ease with which we can deal with problems that require non-linear structures such as trees, graphs. The code to visit repetitively like this of structures is infinitely more difficult to write than by recursion.