[求助] 递归函数不太明白

递归就是"自己调用自己".
形如:
int func(int a){
a=func(a);
return a;
}
在递归中必须有结果递归的条件, 以及达成这个条件的语句.
阶乘应该算最经典的递归了.
N! = 1 * 2 * ... * N
你试着做下

[此贴子已经被作者于2007-6-17 16:58:36编辑过]

真不好意思，我又要反驳你了！
如果你说fib数列是经典递归，那完全错了，那是个失败的不恩能够再失败的递归。
你画个递归树就发现，那个增长完全是比几何还几何的。

所以fib数列最好的仍然是迭代！hanoi tower我同意。但是并不是只能用递归。
所有的的递归和迭代都可以相互转换。
但是有的递归转换为迭代要用到栈存贮数据，这样效率等同于直接用递归了。


呵呵，欢迎探讨哈！

不好意思呀反驳你一下，汉诺塔只能用递归做，用迭代是实现不了的。这一点已经被证明，所以不是所有的递归都可以用迭代来做。

以下是引用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;
}