双尾递归需要解释

Question

我被两个 return 语句卡在了这个递归中。有人可以一步步给我结果吗？

caos(9);

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

Answer 1

我想，你首先要明白的是return语句。

作为参考，来自 C99 标准文档，第 6.8.6.4 章，第 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.

因此，当遇到 return caos(n-2) + caos(n-4); 语句时，将调用 caos() [再次，这就是递归]，并以 n-2 和 n-4 作为参数.

现在，对于 caos() 函数本身，

如果n的值为< 4，则会执行return 4
否则执行return caos(n-2) + caos(n-4);

后者的作用上面已经解释过了。希望这可以帮助。

Answer 2

按照我的评论，我不会给你一个完整的解决方案，但我会尽力帮助你做一些你可以开始的事情。

我们取 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

双尾递归需要解释

Explanation needed for double tail recursion

c

recursion

return

return-value