Returns in a recursive function

Question

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 1

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;
}

Answer 2

I think this is one of the easiest recursive function to understand.

int pow(int n, int x)
{
    if (n != 1)
        return x * pow(n - 1, x)
    else 
        return x;
} 

Let's study pow(3, 2) : 2^3 = 2 * 2 * 2 = 8

First iteration : pow(3, 2) returns 2 * pow(2, 2)
Second iteration : pow(2, 2) returns 2 * 2* pow(1, 2)
Third iteration : n == 1 so pow(1, 2) returns x = 2 * 2 * 2 = 8

A recursive function returns a call to itself at the i + 1 step of the process. In order to avoid an infinite loop, you have to make sur you have a break condition, which leads to a return to something different from a self-call.