我开发了一个基于 Beancount 的账本托管服务 HostedBeans,欢迎大家来了解纯文本复式记账并试用我的服务。
标签 #计算机科学

笔记: 循环, 递归, 迭代, 遍历

本文首发于SegmentFault, http://segmentfault.com/q/1010000000199577#a-1020000000199630

表示”重复”这个含义的词有很多, 比如循环(loop), 递归(recursion), 遍历(traversal), 迭代(iterate).

循环

循环算是最基础的概念, 凡是重复执行一段代码, 都可以称之为循环. 大部分的递归, 遍历, 迭代, 都是循环.

递归

递归的定义是, 根据一种(几种)基本情况定义的算法, 其他复杂情况都可以被逐步还原为基本情况.

在编程中的特征就是, 在函数定义内重复调用该函数.

例如斐波那契数列, 定义F(0)=1, F(1)=1, 所有其他情况: F(x)=F(x-1)+F(x-2).

所有大于1的整数经过有限次的反推之后都可以转换到两种基本情况. 而在编程中, 算法则是这样的:

int F(x)
{
    if(x==0 || x==1)
        return 1;    //这里是退出递归的条件, 以保证在有限次递归后能够得到结果
    return F(x-1)+F(x-2);    //转化为更为基本的情况, 重复调用自身进行计算
}

迭代(数学)

迭代在数学和编程中有不同的含义.

数学方面是指在循环的基础上, 每一次循环, 都比上一次更为接近结果.

例如下面是一个迭代的例子.

int result = 0;
for(int i=0; i>10; i++)
    result += i;    //每一次循环之后, result都更加接近结果45

有很多数学问题, 都是迭代算法, 如牛顿迭代法(求平方根).

迭代(编程)

按顺序访问一个列表中的每一项, 这在很多编程语言中表现为foreach语句:

$arr = [1, 2, 3, 4];
foreach($arr as $i)
    echo $i;

遍历

按一定规则访问一个非线性的结构中的每一项, 强调非线性结构(树, 图). 而迭代一般适用于线性结构(数组, 队列).

结论

  • 循环(loop) – 最基础的概念, 所有重复的行为
  • 递归(recursion) – 在函数内调用自身, 将复杂情况逐步转化成基本情况
  • (数学)迭代(iterate) – 在多次循环中逐步接近结果
  • (编程)迭代(iterate) – 按顺序访问线性结构中的每一项
  • 遍历(traversal) – 按规则访问非线性结构中的每一项

这些概念都表示“重复”的含义, 彼此互相交叉, 在上下文清晰的情况下, 不必做过于细致的区分.

参考

精子生于 1995 年,英文 ID jysperm.

订阅推送

通过 Telegram Channel 订阅我的博客日志、产品和项目的动态:

王子亭的博客 @ Telegram


通过邮件订阅订阅我的博客日志、产品和项目的动态(历史邮件):

该博客使用基于  Hexo  的  simpleblock  主题。博客内容使用  CC BY-NC-ND  授权发布。最后生成于 2024-04-08.