Explanation needed for double tail recursion

Question

I am stuck in this recursion with two return statement. Can somebody give me the results step by step?

caos(9);

int caos( int n ) {
    if (n < 4) {
        return n;
    } else return caos(n-2) + caos(n-4);
}

Answer 1

Following my comment, I won't give you a full solution but I'll try to help you with something you can begin with.

Let's take caos(9):

                         caos(9)    9 < 4? no
                       /         \   
                      /           \
      7 < 4? no  caos(7)          caos(5)  5 < 4? no
                 /    \           /     \
                /      \         /       \
   5 < 4? no caos(5)   caos(3)  caos(3)  caos(1)
             /   \          ↑        ↑        ↑
           ..    ..      all are < 4, let's go up!
                       remember the stop condition. It returns n

Answer 2

I think, what you need to understand first is the return statement.

As reference, from C99 standard document, chapter 6.8.6.4, paragraph 3,

If a return statement with an expression is executed, the value of the expression is returned to the caller as the value of the function call expression.

So, when return caos(n-2) + caos(n-4); statement will be encountered, caos() will be called [again, that's the recursion] with a value of n-2 and n-4 as argument.

Now, for the caos() function itself,

• if n value is < 4, it will execute return 4
• otherwise, it'll execute return caos(n-2) + caos(n-4);

The effect of the later is explained above. Hope this helps.