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

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.

Answer 2

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 3

You got at least one answer which helpfully explains the behaviour of your code.

I want to provide help via a different, additional path here. Both together provide different view points for you.
For that purpose I provide a version of your code augmented by instrumentation, which tells you more verbosely what happens.
This allows you to play with the code and observe, that will give you the really helpful answer.

Note:

• the for(c lines are only for suggestive indentation;
  I chose not to use a function for this, feeling that it keeps the interesting function calls more prominent
• I added a parameter "nesting", it is for
  • making a part of the (hopefully useful) output
  • show that usually the recursive nesting has some influence
• I introduced a local variable "j",
  to show what happens with the reutrn values in most cases

Code:

#include <stdio.h>

int     recur(int i, int nesting)
{   int c;
    for(c=0;c<nesting;c++) { printf(" ");}
    printf("recur[%d](%i)", nesting, i);
    if (i < 3)
    {   printf("i <3, calling recur[%d](%d)\n", nesting+1, i+1);
        recur(i + 1, nesting+1);
        for(c=0;c<nesting;c++) { printf(" ");}
        printf("returning 10 from recur[%d], with i==%d\n", nesting, i);
        return 10;
    }
    else if (i < 5)
    {
        int j=0;
        printf("i <5, calling recur[%d](%d)\n", nesting+1, i +1);
        j=recur(i + 1, nesting+1);
        for(c=0;c<nesting;c++) { printf(" ");}
        printf("ignored return value from recur[%d](%d) is %d", nesting+1, i+1, j);
    }

    printf("\n");
    for(c=0;c<nesting;c++) { printf(" ");}
    printf("returning i from recur[%d], with i==%d\n", nesting, i);
    return i;
}

int     main(void)
{
    int     i = 0;
    i = recur(i, 0);
    printf("the last return value did not get ignored: i = %d\n", i);
    return 0;
}

Output:

recur[0](0)i <3, calling recur[1](1)
  recur[1](1)i <3, calling recur[2](2)
    recur[2](2)i <3, calling recur[3](3)
      recur[3](3)i <5, calling recur[4](4)
        recur[4](4)i <5, calling recur[5](5)
          recur[5](5)
          returning i from recur[5], with i==5
        ignored return value from recur[5](5) is 5
        returning i from recur[4], with i==4
      ignored return value from recur[4](4) is 4
      returning i from recur[3], with i==3
    returning 10 from recur[2], with i==2
  returning 10 from recur[1], with i==1
returning 10 from recur[0], with i==0
the last return value did not get ignored: i = 10

Note:
The recur[n](m) is of course no C syntax.
It just indicates a call to the function "recur" on nesting level "n" with parameter "m".
(Especially do not confuse the "[]" with arrays, they are not present.)

Answer 4

return 0 is the return from the main function, not from your recursive code.