问如何在递归函数中计算返回结果？
EN

Stack Overflow用户

提问于 2016-05-18 11:22:26

回答 3查看 2.3K关注 0票数 1

到目前为止，我认为我理解了返回是如何工作的，但是一旦我进入递归，我想我会比最初的想法更加迷失。

假设，我有一个用于计数的函数，一个字符在字符串中弹出多少次。

int frequency(char ch, string input, int pos) {
   if (pos == inputString.length()) {
      return 0;
   }

   if (inputString[pos] == ch) {
      return 1 + frequency(ch, inputString, pos + 1);
   }
   else {
      return frequency(ch, inputString, pos+1);
   }
}

如果我要传递给它，字符串"Jeff“并查找"f"，它将返回一个2值。

那么，它怎么知道什么时候停止呢？

return 0是否结束任何返回类型为int的方法？
如果是这样的话，为什么它仍然返回2的值，而最后的返回是返回0

c++

recursion

return

有奖征集｜云上CPU玩转AIGC挑战赛

参加活动赢取洛斐键盘、小米电纸书、智能音响等鹅厂周边！

回答 3

Stack Overflow用户

回答已采纳

发布于 2016-05-18 11:25:47

最后的回报

return 0;

是在递归期间调用该函数的最后一次。这是在某个时候停止递归所必需的。对于执行最后一个返回语句之前的调用，例如：

return 1 + frequency(ch, inputString, pos + 1);

因此，0被加到递归的1和以前的任何结果中。

PS:只要函数返回语句再次调用该函数，递归就会继续。只有当返回只是返回某项内容(而不再次调用函数)时，递归才停止。

下面是一个更简单的例子，它计算到N的所有整数的和：

int calcSum(int N){

    if ( N == 1 ) return 1;          // recursion stops here

    return N + calcSum( N-1 );       // otherwise continue to add up 

}

一个函数中的多个返回语句并不是递归所特有的。该函数只在遇到的第一次返回时返回。

票数 3

Stack Overflow用户

发布于 2016-05-18 11:47:28

那么，它怎么知道什么时候停止呢？

当不再从递归调用函数中的特定分支添加更多递归调用时，它将停止，调用堆栈将被清除，返回值与发出调用的顺序相反(LIFO )。就在这里完成了：

if (pos == inputString.length()) {
    return 0;
}

任何其他分支都递归地调用该函数，并在调用堆栈中迈出一步：

if (inputString[pos] == ch) {
    return 1 + frequency(ch, inputString, pos + 1);
            // ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 
}
else {
    return frequency(ch, inputString, pos+1);
        // ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 
}

return 0;结束任何返回类型为int的方法吗？

是的，它适用于任何可以用0初始化的返回类型。

如果是这样的话，为什么它仍然返回2的值，而最后的返回是返回0

因为递归调用结果的结果是在堆栈上累积的：

   return 1 + frequency(ch, inputString, pos + 1);
//          ^ the result of the operation will be saved on the stack when the call returns

..。并在驱动程序函数中看到(第一次)递归调用的最终结果。

顺便说一句，通过性能和内存使用来实现成本低得多的实现将是一个简单的循环。不管怎么说，线性时间行为没有任何缺点：

int frequency(char ch, string input) {
   int result = 0;
   for(int pos = 0; pos < input.size(); ++pos) {
        if (input[pos] == ch) {
           ++result;
        }
    }
    return result;
}