以下是引用aipb2007在2007-6-17 20:06:58的发言：呵呵~
递归确实如你所说，是一炙枷搿２⑶沂呛苡心ЯΦ摹＠鲜邓担?曳浅Ｏ不兜莨椤?lt;BR>递归处理很多问题时，可以很直接，很简单。有时说迭代是人的自然思维，但是我觉得递归才是，很多问题我很容易就想到递归，但是用迭代就很困难，无论思维上还是代码上。
我也不排斥递归，但是递归思想广泛用于实际问题和算法，提到这个，就不得不考虑效率。所以就出现了一个选择：究竟是递归还是迭代？
比如fibnacci数列，其实很容易想到递归，但是代码写出来了，再头脑里运行一下：
计算f5吧:
f5
f3 f4
f1 f2 f2
f3 ……………………………………
这就是递归树一部分，发现了：总有f(n)在重复计算，兰色的f3能用红色的f3吗？no,不行，寄存器不会为你保留。
光递归压栈这个众所周知的降低时间效率不说，这样的重复也大大降低了空间效率。
所以我认为fib的递归解实在只能是个反面教材。
在实际运用中，前几天有个数60头牛的帖子，就用fib数列为基础设计算法。产生了两个版本，一个递归，一个迭代，肯定迭代版更优秀吧！
递归是个好东东，把递归剖开就是 “栈”，这个看似简单的东西作用太大了。要深刻的了解递归一定要搞清楚它的本质。
我也是在学习中。
There is a technique called memoization, which can let you calculate each case only once. Say f3().
#include <iostream>
using namespace std;
int f1(int n); // recursive
int f2(int n); // dynamic programming #1
int f3(int n); // memoization
int memoize(int*f, int i); // called by f3, i>=2
int* f4(int n); // dynamic programming #2
int main(int argc, char** argv)
{
int i;
int size=20;
int *f;
f = f4(size);
for(i=1; i<=size; ++i)
cout<<f1(i)<<"\t"<<f2(i)<<"\t"<<f3(i)<<"\t"<<f[i-1]<<endl;
delete [] f;
return 0;
}
int f1(int n)
{
if(n<3)
return 1;
else
return f1(n-1)+f1(n-2);
}
int f2(int n)
{
int i;
int* c = new int[2];
int f = 1;
c[0] = 1;
c[1] = 1;
for(i=2; i<n; ++i)
{
f = c[0] + c[1];
c[0] = c[1];
c[1] = f;
}
delete [] c;
return f;
}
int f3(int n)
{
if(n<3)
return 1;
int *f = new int[n];
int i;
f[0]=1;
f[1]=1;
for(i=2; i<n; ++i)
f[i] = -1;
int f_n = memoize(f, n-1);
delete [] f;
return f_n;
}
int memoize(int*f, int i) // called by f3, i>=2
{
if( f[i] > 0) // already computed
return f[i];
return memoize(f, i-1) + memoize(f, i-2);;
}
int* f4(int n)
{
int* f = new int[n];
int i;
f[0]=1;
f[1]=1;
for(i=2; i<n; ++i)
f[i] = f[i-2] +f[i-1];
return f;
}
