优化以下递归函数

Question

试图解决作业问题...

我拥有的信息是：

foo(0)=0
foo(1)=1
foo(2)=2

下面的代码最多可以处理大约 30 个数字...但它需要流畅地工作到 100，所以我需要优化它。我试图创建一个连接每个连续数字的方程，但它没有奏效。任何想法如何优化它？

#include <stdio.h>
#include<stdlib.h>
long foo(int n) {
long a;
if (n==0)
{
return 0;
}
else if(n==1)
{
return 1;
}
else if(n==2)
{
return 2;
}
else
{
return foo(n-1)-2*foo(n-2)+foo(n-3)-2;
}
}
int main(void) {
long b=foo(7);
printf("%ld",b);
}

Answer 1

对于这么简单的问题，你可以使函数迭代。

#include <stdint.h>
uint64_t foo (int n)
{
if (n == 0)
return 0;
else if (n == 1)
return 1;
else if (n == 2)
return 2;
else
{
uint64_t a = 0, b = 1, c = 2;
uint64_t ret;
for (int i = 2; i<n; i++)
{
ret = a + 2*b + c - 2;
a = b;
b = c;
c = ret;
}
return (ret);
}
}

如果必须使用递归，则可以通过记忆显著提高运行时间。在这种情况下，您需要一个额外的数组来存储已计算值的结果。

uint64_t memo[101];  // size this array to the maximum value of n needed to be calculated.
uint64_t foo(int n) {
uint64_t a;
if (n==0)
{
return 0;
}
else if(n==1)
{
return 1;
}
else if(n==2)
{
return 2;
}
else
{
if (memo[n] == 0)
{
a = foo(n-1)-2*foo(n-2)+foo(n-3)-2;
memo[n] = a;
}
else
{
a = memo[n];
}
return a;    
}
}