c++ - 将递归函数转换为尾递归函数

Question

连续到this问题:

我有一个 C++ 函数，它会一遍又一遍地调用自己。就是这样:

#include <iostream>
#include <math.h>
#include <stdio.h>
#include <cmath>
using namespace std;
double g( double a, double x){
    if (x>=a) return (g(a,x-1)+g(a,x-a));
    else if (x<a) return 1;
    return 0; //Never Reached
}
int main(){
    cout << (unsigned long)g(sqrt(90),90) <<endl; // outputs 7564511
    cout << (unsigned long)g(sqrt(10000019),10000019)<<endl; // Signal: SIGSEGV (Segmentation fault)
}

我想知道如何将此函数转换为某种迭代或尾循环(或任何停止段错误的方法)，但更重要的是我需要知道如何自己实际执行此操作。

---

注意:如果这是一个微不足道的问题，我提前道歉。

注意 2: 有类似的问题(如 this 或 this )，但我发现没有一个解决我的函数调用自身两次的事实每次迭代。

Answer 1

Memorization可以是限制计算所需的递归调用次数的有效方法。尝试针对一些简单的输入(例如 g(2, 8))评估该函数，您会发现您最终会针对相同的值一遍又一遍地评估该函数。通过在第一次计算时缓存每组输入的结果，您可以缩短递归并显着减小问题的大小。

要使函数迭代而不是递归，您可以使用的一种策略是尝试翻转定义并自下而上迭代。考虑斐波那契函数:

fib(n) = fib(n-1) + fib(n-2)

为了迭代计算 fib(n)，我们从基本情况 fib(1) + fib(0) 开始，迭代到 fib(n)。这样一来，您就可以边走边积累值(value)，而不必在计算中间值时记住自己的位置(一遍又一遍)。所以 fib() 的迭代定义如下:

fib(n) {
    a = 1;
    b = 0;
    fib = 0;
    i = 1;
    while (i < n) {
        fib = a + b;
        b = a;
        a = fib;
        i++;
    }
    return fib;
}

您应该能够使用 g() 函数执行类似的操作。我没有时间玩它，但我敢打赌，如果你尝试手动评估它的几个 a, x 对，你会注意到一个模式，可以让你重写函数以迭代形式，就像我上面为 fib() 所做的那样。