Recursion in C, understand recursion example

Question

i am having trouble understanding this example. I cant figure out what actually happens after a certain point.

Here is the code, the result is supposed to be 4.

I can see that it calls itself several times but how it actually comes to the result of 4 eludes me entirely. Any help would be greatly appreciated.

#include <stdio.h>

int recursion(int i) 
{ 
  return (i>1 ? i - recursion(i/2) : 3);
} 

int main() 
{ 
  int number = 9; 
  printf("The result is %d\n", recursion(number)); 
  return 0;
}

edit: Thanks so much, that clears it up!

Answer 1

Here from code, recursion(1) = 3 and i/2 when i>1 , 9/2 = 4 (since int as parameter)

The base condition of this recursive function is when i = 1

Answer 2

You should look at how the calls are chained. Debug output helps:

int recursion(int i) 
{ 
   int result;
   printf( "called with i=%d\n", i );
   result = (i>1 ? i - recursion(i/2) : 3);
   printf( "call with i=%d will return %d\n", i, result );
   return result;
} 

The basic idea is that when a recursive call is done the original call is suspended until the recursive one ends.

Answer 3

The recursion function can be written in a less compact fashion this way:

int recursion(int i) 
{ 
    if(i>1)
    {
        int j;
        j = i - recursion(i/2); // note here that the function recall itself
                                // note also that as i is integer the function
                                // will be invoked with i/2 rounded to the lower int value
        return j;
    }
    else
    {
        return 3;
    }
}

hope this helps...

Answer 4

You can reason about this problem by substituting and simplifying.

You start off calling recursion(9), lets substitute 9 for i and reduce

recursion(9)
->  9 > 1 ? 9 - recursion(9/2) : 3
->  true ? 9 - recursion(4) : 3
->  9  - recursion(4)

now you do recursion(4), to simplify this you can repeat the process...

recursion(4)
->  4 > 1 ? 4 - recursion(4/2) : 3
->  true  ? 4 - recursion(2) : 3
-> 4 - recursion(2)

recursion(2)
-> 2 > 1 ? 2 - recursion(2/2) : 3
-> true ? 2 - recursion(1) : 3
-> 2 - recursion(1)

recursion(1)
-> 1 > 1 ? ... : 3
-> false ? ... : 3
-> 3

Here you got a final result, so substitute it back in to recursion(1)

2 - 3 -> -1

and recursion(2)

4 - -1 -> 5

and recursion(4)

9 - 5 -> 4

Answer 5

Recursion is the process of repeating itself several times until the condition is true.

Here the function recursion returns the value 3 if i>1 is false and if true it calls recursively.

As i=9, first time it checks 9>1 is true. so, the function returns 9 - recursion(9/2=4) as i is int.

then it calls recursion(4) 4>1 hence, returns 4 - recursion(4/2=2)

again 2>1, returns 2 - recursion(1)

again 1>1 is false, it returns 3 which should substitute in above value i.e., 2-3 = -1.

then 4 - (-1) = 5

9 - 5 = 4.

Answer 6

I think the best way to understand this would be just stepping through it in debugger.