the5fire

关注Python、Django、Vim、Linux、Web开发、团队管理和互联网--Life is short, we need Python.


递归和迭代

作者:the5fire | 标签: | 发布:2010-11-03 10:02 p.m. | 阅读量: 9036, 8932
第一、什么是递归,什么是迭代
递归:就是自身调用自身;迭代是根据旧值推出新值。
第二、优缺点
递归可读性强,方便理解,不过效率低一点,因为要频繁的进行函数调用。迭代具有更高的时空效率。
代码示例:
求斐波那契数列
1、递归法
这种方法的优点是简洁和容易理解,缺点是时间复杂度太大,随着n的增大,运算时间将会急剧增加。因此在很多场合这种方法是不可取的。
使用这种方法的关键代码是:
[cc lang="C"]
if(n == 1|| n== 2)
{
  return 1;
}
else
{
  return fib(n - 1) + fib(n - 2);
}

2、迭代法
这种方法相对于递归法来说在时间复杂度上减小了不少,但代码相对就要复杂些了。它的思想是这样的,假设开始时f0=1,f1=1,cFib表示当前斐波那契数,则:
[cc lang="C"]
for(i = 1;i < n;i++)
{
  cFib = f0 + f1;
  f0 = f1;
  f1 = cFib;
}

这样迭代结束和cFib就是fib(n)了。

参考:http://topic.csdn.net/u/20091209/14/c6d236e3-d6c1-45f6-92f1-3bbea75320ea.html
- from the5fire.com
----EOF-----

微信公众号:Python程序员杂谈


其他分类: