|
发表于 2010-3-30 20:20:41
|
显示全部楼层
我把这个递归函数用两种方法各写了一遍:
int func1(int n)
{
if (n <= 1) return n;
return func1(n - 1) + func1(n - 2);
}
__int64 func2(__int64 n, __int64 *a1 = NULL)
{
if (n == 0) return 0;
else if (n == 1)
{
if (a1) *a1 = 0;
return 1;
}
else if (n == 2)
{
if (a1) *a1 = 1;
return 1;
}
__int64 p, q;
__int64 k = func2(n - 1, &p);
if (a1) *a1 = k;
return p + k;
}
然后调用:
DWORD tick1 = GetTickCount();
int w = func1(40);
DWORD tick2 = GetTickCount();
int x = func1(41);
DWORD tick3 = GetTickCount();
int y = func1(42);
DWORD tick4 = GetTickCount();
__int64 z = func2(50);
DWORD tick5 = GetTickCount();
结果:
tick2 - tick1 = 11047
tick3 - tick2 = 17834
tick4 - tick3 = 28938
tick5 - tick4 = 0
再调用:
DWORD tick4 = GetTickCount();
__int64 z = func2(100);
DWORD tick5 = GetTickCount();
结果:
tick5 - tick4 = 0
高效递归函数的关键,在于处理递归函数里面的历史计算结果。f(n)被多次调用,如果每次调用的结果都是相同的,那么就要把f(n)的值记录下来,这样就可以迅速的完成计算。
第一种方法之所以慢,是因为计算f(n),n加1,f(0)就要多调用62%那么多次,可见冗余的计算量是相当可观的。 |
|