由于大输入的堆栈溢出，将通用递归转换为尾递归

Question

我发现该算法适用于返回特定周长的可能三角形的数量的程序。我知道这个问题还有其他方法，但是使用它们时，我得到大量时间限制错误，可能是因为它们没有经过优化。这似乎更优化了，但是我得到了堆栈溢出，以便对大输入进行递归。有人可以通过将其转换为尾递归来帮助我优化它，或者对此问题进行其他处理吗？

这是我找到的算法：

#include<iostream>
using namespace std;
int foo(int);
int main(){
    int n;
    cin>>n;
    cout<<foo(n);
    return 0;
}
int foo(int n){
    int p=n/2-2;
    int t;
    if(p%6<5&&p%6>0)
        t=(p+6-p%6)/6;
    else if(p%6==5)
        t=(p+6-p%6)/6+1;
    else
        t=p/6;
    if(n==3||n==5||n==6)
        return 1;
    else if(n==4)
        return 0;
    else{
        if(n%2==0)
            return foo(n-3);
        else
            return foo(n+1)+t;
    }
}

Answer 1

问题在这里：

return foo(n+1) + t;
//              ^^^

该加法使对foo的递归调用不是该函数中发生的最后一件事情。因此，您需要将该加法into函数：

return foo(n + 1, t);

为了使其他递归调用兼容，您只需提供加法的中立元素：

return foo(n-3, 0);

新功能的签名：

int foo(int n, int offset = 0); // default parameter allows for calling just as before.

剩下的最后一个问题：在哪里进行加法？

嗯，两个地方很明显：

if(n==3||n==5||n==6)
    return 1 + offset;
else if(n==4)
    return /*0 +*/ offset;

offset是先前所有递归调用的累积偏移量！因此，您必须将其添加到添加到下一个函数的递归调用中的任何内容中，因此：

// ...
else if(n % 2 == 0)
    return foo(n-3, /*0 +*/ offset);
else
    return foo(n+1, t + offset);

附带说明：您的算法似乎不适用于负数。用这些调用（未修改的）foo会重复发生，直到堆栈溢出为止（如果堆栈足够大，则由于有符号整数溢出而可能导致未定义的行为）。如果您不打算在负数上使用它，则absolutely应该使用unsigned int作为数据类型！否则，需要进行适当的修复。

值0、1和2也需要特殊处理，它们会导致负数n（对于未修改的foo，请参见上文）。

并且您可以将p和t的计算移到前两个停止条件之后，无论如何您都不要在其中使用t ...