c - 理解给定递归函数的目的和区别

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)或提供的内容(对于负输入；循环体永远不会执行)。递归不断将 0 添加到 x，因此 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;
}