| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1400 人关注过本帖
标题:[求助] 递归函数不太明白
只看楼主 加入收藏
野比
Rank: 7Rank: 7Rank: 7
等 级:贵宾
威 望:24
帖 子:1627
专家分:516
注 册:2007-5-24
收藏
得分:0 
一起学习..
老费的数列实在是太NB了.. 连股市都要用到它...传说的黄金分割数列...
正如我所了解的: fib的原本定义是迭代式的while(n<N)型, 不断相加就可以了
对于它的递归定义(我上面的那个等式), 纯粹是一个"完美的教学范例".. 适合学习..
(当初学PASCAL的第一个递归例子.. 第二个是Hanoi..)
由于有NOI这类比赛(我就是初中参加培训才接触PASCAL的), 强调的是解题而非效率, 重思路重结果却不在乎过程..
造就出许多追求"美丽代码"的递归型选手...
..
学无止境...cheers..

女侠,约吗?
2007-06-17 20:25
蛙蛙
Rank: 1
等 级:新手上路
帖 子:19
专家分:0
注 册:2007-6-14
收藏
得分:0 
以下是引用aipb2007在2007-6-17 18:14:35的发言:

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

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


呵呵,欢迎探讨哈!

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


2007-06-18 14:30
aipb2007
Rank: 8Rank: 8
来 自:CQU
等 级:贵宾
威 望:40
帖 子:2879
专家分:7
注 册:2007-3-18
收藏
得分:0 
回复:(蛙蛙)以下是引用aipb2007在2007-6-17 18:14:...
我不知道是怎么证明的,可能实际操作有难度,但是理论上绝对可行!

递归分“尾部递归”和“非尾部递归”
前者,直接转换为迭代,因为这样的递归没有压栈过程(因编译器不同,最多也是一次)。
后者,因为递归的栈操作,栈中存储当前的局部变量。所以转换为迭代时要人为使用栈。


哪里有证明,你给我看看,我也很想学习下!

Fight  to win  or  die...
2007-06-18 15:26
HJin
Rank: 6Rank: 6
等 级:贵宾
威 望:27
帖 子:401
专家分:0
注 册:2007-6-9
收藏
得分:0 
以下是引用aipb2007在2007-6-17 20:06:58的发言:
呵呵~

递归确实如你所说,是一炙枷搿2⑶沂呛苡心ЯΦ摹@鲜邓担?曳浅O不兜莨椤?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;
}


I am working on a system which has no Chinese input. Please don\'t blame me for typing English.
2007-06-18 18:04
xq0714
Rank: 1
等 级:新手上路
帖 子:34
专家分:0
注 册:2007-5-25
收藏
得分:0 

个人愚见,递归注重的是开始条件和结果,至于过程可能自己都不知道!有点像数学归纳法!缺点是过程不清晰!
迭代注重的是个过程,清晰明朗!
我们老师说最好是用迭代!大概也看出迭代的优点,而且迭代速度快!
递归能做到的迭代也一定能做到,在数学上两种方法是等价的!

2007-06-18 18:44
野比
Rank: 7Rank: 7Rank: 7
等 级:贵宾
威 望:24
帖 子:1627
专家分:516
注 册:2007-5-24
收藏
得分:0 
蛙蛙兄, Hanoi可以用迭代完成.. 目前我见过的版本是老外写的一个...
不过写得并不好, 只是完成功能, 效率上有了看不出来的提高, 而算法的清晰度上输的一塌糊涂...
最恶心的是它的第一个盘子的移动居然是人工设置N为奇数, N为偶数的情况...
我看到这里, 心里只有两个字.."我...靠"...
这个例子完全是"为了迭代而迭代"...跟fib数列"为了递归而递归"简直有异曲同工之妙..

女侠,约吗?
2007-06-18 19:46
野比
Rank: 7Rank: 7Rank: 7
等 级:贵宾
威 望:24
帖 子:1627
专家分:516
注 册:2007-5-24
收藏
得分:0 
另外, to xq0714, 你的话我完全同意... 除了最后一句的前半句..
有一点迭代做不到, 就是取代循环..

比如(经典例子):
sum = 0;
for (int i = 0; i < n; i++) sum += a[i];

可以用递归方式实现:
float sum (float a[], const int n)
{
if (n <= 0) return 0;
else return sum(a, n – 1) + a[n – 1];
}

所以准确来说, 编程的三大结构之一的"循环"可以用递归代替....
不过...没有哪个语言会这么做..原因大家前面已经讨论的相当深入了..

女侠,约吗?
2007-06-18 20:03
aipb2007
Rank: 8Rank: 8
来 自:CQU
等 级:贵宾
威 望:40
帖 子:2879
专家分:7
注 册:2007-3-18
收藏
得分:0 


c++板块如今是人才辈出啊!!!

Fight  to win  or  die...
2007-06-18 20:20
蛙蛙
Rank: 1
等 级:新手上路
帖 子:19
专家分:0
注 册:2007-6-14
收藏
得分:0 
哦 哦 哦
晚生才疏学浅,其中定是受了老师蒙骗,嘿嘿,妄言之处大家见谅啊!
不过老师好像真的说过这句话,当时茅塞顿开整个肌肤为之一阵。嘿嘿!

2007-06-18 20:44
快速回复:[求助] 递归函数不太明白
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.061047 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved