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

Question

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

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

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？

Answer 1

最后一次返回

return 0;

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

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

因此，0与1以及递归的任何先前结果相加。

PS：只要函数return语句再次调用函数，递归就会继续。只有当返回只是返回一些东西时（不需要再次调用函数），递归才会停止。

这里有一个更简单的例子，它计算所有整数的和，直到N：

int calcSum(int N){
    if ( N == 1 ) return 1;          // recursion stops here
    return N + calcSum( N-1 );       // otherwise continue to add up 
}

一个函数中的多个返回语句对于递归来说并不是特别的。函数只在遇到第一个返回时返回。

Answer 2

那么，它如何知道何时停止

当不再从递归调用函数的特定分支添加递归调用时，它将停止，调用堆栈将被清除，返回值的顺序与发出调用的顺序相反（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;
}

Answer 3

将递归调用视为函数调用的堆栈。在某个时刻，它可能会达到return 0;。这意味着堆栈上的一个函数调用已完成。因此，堆栈上的一个元素被弹出。当堆栈为空时，函数的最终返回。