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

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 3

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