时间戳

首页 > 解决方案 > 了解给定递归函数的目的和区别

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

问题描述

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

代码 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;
}

标签： c

解决方案

考虑原始代码：

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;
}

推荐阅读