Different kinds of recursion¶

We can divide recursive functions in groups based on their characteristics and, for your general education, it is good to know them.

Direct recursion happens when a function calls itself in its own body. For instance, factorial in the previous example uses direct recursion.
Indirect recursion or mutual recursion means that the function func_a calls the function func_b which, in turn, calls func_a, et cetera:

The knot that is created can include even more functions, i.e. the ”circle of calls” can be longer.

You should avoid using indirect recursion, because it is often difficult to understand.
Tail recursion, which we will get into this below.

Tail recursion¶

A function is tail-recursive, if the recursive call is located in such a point in the function that after the call, there are no statements to execute or expressions to evaluate. In other words, when the recursions ”unwind”, there are no actions left in the called function.

The function factorial of the previous example is not tail-recursive, because you first need to multiply the return value of the recursive call by n in order to receive a result that can be used as a return value:

return n * factorial(n - 1);

However, factorial can be created as tail-recursive:

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

and you should give 1 as its last parameter in the call:

cout << factorial(5, 1) << endl;

In this case, the result of a tail-recursive function is gathered bit by bit in an additional parameter (result), and the gathered value can be returned as such when the finishing condition is fulfilled. The consequence of this is that the initial value of the additional parameter must be the final result of the trivial case. Why?

Tail recursion is an important concept, because you can mechanically move it to a loop structure. That way, you achieve the benefits of recursion but simultaneously get rid of its downsides.

Try it out yourself: In the previous assignment, you calculated the sum of integers, which is also easy to implement tail-recursively. If you want to try it, add a new function sum_tail_recursive into your file. This function has the same definition as the function sum_recursive, except that it also has an additional int type parameter, into which you begin calculating the sum.