Recursive Functions

Recursion refers to the property of some concepts to be defined in terms of themselves.

In C++, recursion is achieved through functions that can call themselves. Recall that a function must be defined and then can be called. Recursion consists of the fact that in the definition of a function, the function itself is called. This call, which appears in the very definition of the function, is called a self-call. The first call, made in another function, is called the main call.

Example:

Let's write a C++ function that returns the factorial of a natural number passed as a parameter. The non-recursive (iterative) version is as follows:

int fact(int n)
{
    int p = 1;
    for(int i = 1 ; i <= n ; i ++)
        p = p * i;
    return p;
}

We observe that this function determines the correct result for values of n greater than or equal to 0 (small values, practically n <= 12). The function also correctly determines the result for n == 0.

A recursive version for determining n!, which uses the observations above, is:

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

Observations:

• it is mandatory that the definition of a recursive function includes a base case (where the self-call does not occur). Otherwise, the self-calls will occur "endlessly". In fact, after too many self-calls, the stack will be completely filled and the program execution will be interrupted.
• it is mandatory that, for non-base cases, the values passed in the self-call of the parameters approach the values in the base case. Otherwise, the situation described above will occur: the stack will be completely filled and the program will stop, without determining/displaying the desired results.

How to perform a self-call?

The self-call is made according to the header of the recursive function. Thus:

• if the recursive function is non-void, the self-call will be made in an expression;
• if the recursive function is void, the self-call will be made in a standalone statement; if the function returns values, output parameters will be used.

Examples:

Void function

void fact(int n, int &r)
{
    if(n == 0)
        r = 1;
    else{
        fact(n - 1 , r);
        r = r * n;
    }
}
int main()
{
    int a;
    fact(4, a);
    cout << a;
    return 0;
}

Non-void function

int fact(int n)
{
    int r;
    if(n == 0)
        r = 1;
    else
        r = n * fact(n - 1);
    return r;
}
int main()
{
    int a;
    a = fact(4);
    cout << a;
    return 0;
}