设为首页 - 加入收藏
广告 1000x90
您的当前位置:三五图库香港35图库大全 > 不变式 > 正文

是否所有的循环都能用递归代替?

来源:未知 编辑:admin 时间:2019-05-25

  另:在有些函数式语言中并没有循环的概念,如Haskell和Scheme里既没有for循环,也没有while循环,只能使用递归。

  #define foo(x) {bar_1(x); bar_2(x)}

  #define foo(x) do { bar_1(x); bar_2(x); } while (0)

  if(WTF) do { bar_1(something); bar_2(something); } while (0); else //...

  结论很暴力,但细说起来还是有点意思的,容我慢慢道来。(赠送循环不变式分析法解释)

  可以注意到,在fib1中,我们必须小心处理a,b,tmp三者的赋值顺序,以确保下一个状态的准确。 除此以外,i也是迭代过程中需要处理的状态,这里只是通过for循环来做了。

  那么如果这时候我要用《算法导论》上提到的分析“循环不变式”的方法,来分析一下我写的fib1正不正确,该怎么做呢?

  我们来理清一下,在a,b,tmp,i,n这5个变量中,tmp仅仅是用来解决赋值时的顺序问题的,n是常量,真正跟迭代的状态有关的变量是a,b,i这三个。

  所以我们得到循环不变式:a == fib(i) && b == fib(i + 1) ,只要我们能证明这个特质在从当前状态到下一个状态的过程中能得以保持(以及对初始状态成立),我们就相当于证明了式子在迭代的每个阶段都成立(有没有发现其实就是数学归纳法?),我们就能确信我们的代码没有错,即当i == n的时候,我们一定能得到a == fib(n)。

  为了让这件事情做得更机械一点,我们把代码改写成下面的fib2这样,把迭代变量a,b,i都暴露出来,并且都通过next_*这些临时变量来计算下一个状态,这样我们就只需要考虑下一个状态和上一个状态的关系,而不用关心赋值的顺序了(可以注意到对next_*赋值的三条语句的顺序是不重要的,对后面三条语句也一样)。

  通过上面的改造,我们发现,在新的fib2中,迭代变量a,b,i已经被明确地暴露出来了,并且对下一个状态的计算过程很明确,不再是捣鼓一些不明所以的tmp变量了,而且对计算顺序也不再敏感。

  不过,它显然没有fib1简洁好看。那么怎么做到内外兼修呢? 可以把迭代变量作为一组参数定义一个函数专门用来迭代,然后这组参数表达的就是当前状态,在函数体内要做的主要事情,就是1. 判断是否到达终止状态, 2. 计算出下一个状态。 这样一来我们就得到了下面的fib3 。 可以看到,我们之前通过next_*变量做的事情,现在被传参过程中的参数拷贝替代了。

  这样做好处当然明显,就是迭代变量一览无余,分析程序正确性更容易了。另外,计算下一个状态的过程中也不需要考虑赋值的顺序了,读写都方便很多。

  但是这样写也是会带来一些问题的,比如递归调用需要消耗栈内存空间,这样一来程序就不可能长时间运行(因为每次迭代都要消耗内存空间)。

  不过可以看到,以上的fib3和fib2是直接对应的,对于给出其中任何一种,我们都很容易机械地把它翻译为另外一种,这种递归形式被称为尾递归(见什么是尾递归? - 编程)。 既然人可以容易的在两种形式之间转换,那么机器自然也能,所以在c++里,如果编译的时候加了-O2的优化选项,这种形式的递归是可以仅占用常量内存空间的。

  所以从表达能力的角度考虑,那么当然是应该把这种没有副作用的纯函数写成递归的形式的。

  不过从实际使用的角度看,有相当多的非函数式语言(如Python,JavaScript)是不做尾递归优化的,所以在使用的时候也就要考虑这样写导致的占用栈空间的代价,当然在非性能瓶颈处主要考虑的还是表达能力。

  为什么国外的工程师在给单片机做死循环时喜欢用 for(;;) 而不是 while(1)? - 编程

  2.循环比递归的效率高(递归每调用一次都要存一份当前function的副本,时间内存都消耗增大)

  3.只有在循环写出来会把人看晕的情况下,优先选递归,递归使得代码简单易懂。

  以上引自DEITEL 的《C++ how to program 》,字典一样,解决很多问题。

本文链接:http://1763inn.com/bubianshi/716.html

相关文章:

相关推荐:

网友评论:

栏目分类

现金彩票 联系QQ:24498872301 邮箱:24498872301@qq.com

Copyright © 2002-2011 DEDECMS. 现金彩票 版权所有 Power by DedeCms

Top