Returns in a recursive function

nounoursnoir picture nounoursnoir · May 29, 2017 · Viewed 10.3k times · Source

I am trying to understand how to use recursion in C, and I can't get how return works in it.

Please consider the following code:

int     recur(int i)
{
    printf("recur: i = %d\n", i);
    if (i < 3)
    {
        recur(i + 1);
        return 10;
    }
    else if (i < 5)
        recur(i + 1);
    return i;
}

int     main(void)
{
    int     i = 0;
    i = recur(i);
    printf("i = %d\n", i);
    return 0;
}

The output is:

recur: i = 0
recur: i = 1
recur: i = 2
recur: i = 3
recur: i = 4
recur: i = 5
i = 10

What does the last return, return i, do? Does this code even make sense?

Answer

Vlad from Moscow picture Vlad from Moscow · May 29, 2017

The recursive calls of the function do not influence on the returned value. Only the first return met in the first instance of your recursive function will return a value to the parent function. Any other return met will just stop the function's instance the program is currently in.

Thus as the function was called in main with the argument 0

int     i = 0;
i = recur(i);

The first return met is located inside of an if statement:

if (i < 3)
{
    recur(i + 1);
    return 10;
}

In this case, the recur function is called before returning a value to main. It will create another instance of recur which will do some stuff, but after this instance of recur has ended, the main instance of recur will continue and, in this case, will return 10 to the function main.

To know what your recursive function will return to the main function, you can simply comment all calls to a new instance of the function:

int     recur(int i)
{
    if (i < 3)
    {
        //recur(i + 1);
        return 10;
    }
    else if (i < 5)
    {
        //recur(i + 1);
    }
    return i;
}

In this case, this is what the program will read:

int     recur(int i)
{
    if (i < 3)
        return 10;
    return i;
}