了解给定递归函数的目的和区别

Question

下面是两段代码。我无法理解第一个代码中的预递减运算符是如何工作的。我也无法理解这两个代码的功能有何不同。

代码 1：

int foo (int val) { 
int x = 0; 
while (val > 0) {
x = x + foo(--val);
}
return val;
}

---

代码 2：

int bar (int val) {
int x = 0;
while (val > 0) {
x = x + bar(val - 1);
}
return val;
}

Answer 1

考虑原始代码：

int foo(int val) {
int x = 0;
while (val > 0) {
x = x + foo(val--);  // Post-decrement
}
return val;
}

当foo()递归调用自身时，传递给递归调用的值与传递给当前调用的值相同，因此程序最终将超过堆栈限制并崩溃。 它不会正常终止。

现在考虑修订后的代码：

int foo(int val) {
int x = 0;
while (val > 0) {
x = x + foo(--val);  // Pre-decrement
}
return val;
}

现在递归是有限的;如果val是正的，那么递归调用的值较小，因此递归停止。 当然，如果val是负数，则没有递归。

但是，由于代码返回val，它将始终返回 0(对于非负输入，因为循环倒计时直到val == 0(或提供的内容(对于负输入;循环体永远不会执行(。 递归不断向x添加0，所以x也保持0(但它是一个"已设置但未读"的变量，因此可以消除，并且写x += foo(val--);会更惯用的 C(。 准确地说，修订后的代码等同于：

int foo(int val) { return (val < 0) ? val : 0; }

即使返回x也不能解决所有问题。 对于非负输入，它返回 0，对于负输入返回 0(但它不会崩溃(：

int foo(int val) {
int x = 0;
while (val > 0) {
x += foo(--val);  // Pre-decrement
}
return x;
}