阶乘函数:
n!=n*(n-1)*(n-2)...3*2*1
针对这样的表述,直译成一个过程:
(define (factorial n)
(if (=n 1)
1
(* n (factorial (- n 1)))))
如果是factorial(6),其计算行为是:
(factorial 6)
(* 6 (factorial 5))
(* 6 (* 5 (factorial 4)))
(* 6 (* 5 (* 4 (factorial 3))))
(* 6 (* 5 (* 4 (* 3 (factorial 2)))))
(* 6 (* 5 (* 4 (* 3 (* 2 (factorial 1))))))
(* 6 (* 5 (* 4 (* 3 (* 2 1)))))
(* 6 (* 5 (* 4 (* 3 2))))
(* 6 (* 5 (* 4 6)))
(* 6 (* 5 24))
(* 6 120)
720
现在我们换种不同的角度来计算阶乘,我们可以将计算阶乘n!的规则描述为:先乘以1和2,而后将得到的结果乘以3,而后再乘以4,这样下去直到达到n.更形式的说,我们要维护一个变动的乘积product,以及一个从1到n的计数器counter,这一计算过程可以描述为counter和product的如下变化,从一步到下一步,它们都按照下面的规则变化:
product <- counter*product
counter <- counter-1
可以看到,n!也就是计算器counter超过n时乘积product的值。
这样,我们可以这样描述阶乘的过程:
(define (factorial n)
(fact-iter 1 1 n))
(define (fact-iter product counter max-count)
(if (> counter max-count)
product
(fact-iter (* counter product)
(+ counter 1)
max-count)))
这样,新的模型的6!的计算过程:
(factorial 6)
(factorial 1 1 6)
(factorial 1 2 6)
(factorial 2 3 6)
(factorial 6 4 6)
(factorial 24 5 6)
(factorial 120 6 6)
(factorial 720 7 6)
720
考虑前一个计算过程,代换模型揭示出一种先逐步展开而后收缩的形状,在展开的过程里,这一计算过程构造起一个推迟进行的操作所形成的链条,收缩阶段表现为这些运算的实际执行。这种类型的计算过程由一个推迟执行的运算链条刻画,称为一个递归计算过程。要执行这样的计算过程,解释器就需要维护好那些以后将要执行的操作的轨迹。在计算阶乘n!时,推迟执行的乘法链条的长度也就是为了保存其轨迹需要保存的信息量,这个长度随着n值而线性增长,就像计算中的步骤数目一样。这样的计算过程称为一个线性递归过程。
与之相对应,第二个计算过程里并没有任何增长或者收缩。对于任何一个n,在计算过程中的每一步,在我们需要保存轨迹里,所有的东西就是变量counter, product和max-count的当前值。我们称这种过程为一个迭代计算过程。一般来说,迭代计算过程就是那种其状态可以用固定数目的状态变量描述的计算过程;而与此同时,又存在着一套固定的规则,描述了计算过程在从一个状态到下一状态转换时,这些变量的更新方式,还有一个结束检测,它描述这一计算过程应该终止的条件。在计算n!时,所需的计算步骤随着n线性增长,这种过程称为线性迭代过程。
我们还可以从另一个角度来看这两个过程之间的对比。在迭代的情况里,在计算过程中的任何一点,那几个程序变量都提供了有关计算状态的一个完整描述。如果我们令上述计算在某两步之间停下来,要想重新唤醒这一计算,只需为解释器提供有关这三个变量的值。而对于递归计算过程而言,这里还存在着另外的一些隐含信息,它们并未保存在程序变量里,而是由解释器维持着,指明了在所推迟的运算所形成的链条里的漫游中,“这一计算过程处在何处”。这个链条越长,需要保存的信息也就越多。
在做迭代与递归之间的比较时,我们必须小心,不要搞混了递归计算过程的概念和递归过程的概念。当我们说一个过程是递归的时候,论述的是一个语法形式上的事实,说明这个过程的定义中(直接或间接地)引用了该过程本身。在说某一计算过程具有某种模式时(如线性递归),我们说的是这一计算过程的进展方式,而不是相应过程书写上的语法形式。当我们说某个递归过程将产生出一个迭代的计算过程时,别奇怪,上面的第二种方式就是,其事先称为尾递归。(某些语言某些编译器可能会直接将其优化为循环之类的动作)
分享到:
相关推荐
n后问题--非递归迭代回溯.rar n后问题--非递归迭代回溯.rar n后问题--非递归迭代回溯.rar n后问题--非递归迭代回溯.rar n后问题--非递归迭代回溯.rar n后问题--非递归迭代回溯.rar
DNS递归和迭代
文件检索器 递归迭代搜索 搜索功能很强大啊
在正整数集定义如下迭代序列 n=n/2 若n为偶数;n=3n+1 若n为奇数 从小于一百万的数开始,能够生成最长序列的是哪个数? 例如:13-40-20-10-5-16-8-4-2-1(10次) 文件包含迭代思路
递归与迭代算法及其在JAVA语言中的应用.pdf
fibonacci数列的各种解法,递归、存储优化的递归、自下而上的递归(迭代法)、尾递归。其中分析内容请移步我的博客、
使用动态规划方法实现0/1背包问题求解;一共两种解法:存储记忆+递归; 自下而上的递归(迭代法);我CSDN博客有详细介绍。
枚举算法,递归与分治策略,递归与迭代的思想、求最大值最小值、线性查找、二分查找与冒泡排序以及选择与交换排序、插入和希尔排序。本课程除了强调经典的算法理论和模型,亦兼顾编程实践能力。力图使得学员面对复杂...
Oracle使用递归查询。查询树结构的sql。在Oracle中,递归查询要用到start with ……connect by prior……
迭代与递归算法
本篇文章主要介绍了python使用递归、尾递归、循环三种方式实现斐波那契数列,非常具有实用价值,需要的朋友可以参考下
迭代与递归的区别
递归和迭代1
DNS迭代查询和递归查询的区别.docx
公司要求分享迭代和递归函数,在周末的时间整理了一个简单的PPT,在这里也分享给大家,互相学些,相互总结。
迭代法、穷举搜索法、递推法、递归、回溯法、贪婪法、分治法、动态规划法
实验2 二分检索的递归与迭代算法设计(报告).doc
fibonacci 递归求法
//二分查找,递归实现 int binarySearch(int a[],int low,int high,int key) { //查找某元素是否在数组中,若存在,则返回下标,否则返回-1; int mid=(low+high)/2; if(low>high){ return -1;//该元素不...