计算机中的黑魔法:尾递归(2)

举例来讲,在上面这个过程中,guess 和 x 是good-enough?这个过程的两个约束变量,<, abs, -, square都是自由变量。自由变量是和环境相关的,他们已经有了确定的意义来保持他们正常的执行,但是如果现在guess这个约束变量改名为abs,将会导致abs这个自由变量的意义被约束变量屏蔽,过程中出现的abs为约束变量,不在具有自由变量当中求绝对值的功能。

所以说,对于过程的设计者而言,过程实现中,自由变量和约束变量的名字都在哪些地方用到是一个非常需要注意的地方,一个过程的顺利执行依赖于约束变量和自由变量的名字不同,并且自由变量的意义正确。

抽象2—内部定义和块结构

这一点的抽象就更加为我们过程的使用者考虑,它也是一种局部的概念,像局部变量一样,只有内部的作用域可以访问并且识别他,作用域之外是不知道作用域内有这个东西的。只不过我们之前抽象的是变量,这次抽象的是过程。

sicp中的求平方根的过程,和用户交互的仅仅是一个接口sqrt,其中的子过程的具体实现细节都被抽象一个个的【黑箱】。但是对于用户来说,这些实现计算过程的黑箱是没有用的,只会扰乱他们的思维,并且在用户想自定义一个与这些黑箱中的某一个同名的过程的时候是不被允许的(不能在一个作用域内定义两个同名的过程),这些有着具体功能的【黑箱】污染了全局名字环境。

对于一个结构局部的东西,我们更好的方式是把他们定义在这个结构的内部,而不应该放在全局环境范围内,因为你需要的并不是其他人也需要的,如果其他人不需要这些东西,那么他们的命名就有可能造成过程调用的命名冲突,造成程序混乱。

scheme支持在过程的内部再定义新的过程,内部新定义的过程只能在内部作用域可见,外部是不知道有内部这些过程的定义的。

(define (sqrt x) (define (good-enough? guess x) (abs (- (square guess) x)) 0.001)) (define (improve guess x) (average guess (/ x guess))) (define (sqrt-iter guess x) (if (good-enough? guess x) guess (sqrt-iter (improve guess x) x))) (sqrt-iter 1.0 x))

根据上面的例子来看,我们就把求平方根这计算过程中用到的小黑箱一个一个的都定义在了这个过程的内部 ,过程之外看不到他们,这种嵌套的过程定义就叫做块结构。局部化使程序更清晰,减少全局名字,减少相互干扰。除此之外,由于将一些黑箱进行了内部定义之后,还有一处可以改进的地方,就是参数x的使用。由于局部过程的形参都在x的作用域内,我们就不必在局部过程中再传递x了,直接调用即可。相对于局部过程来说,现在的X由原来的约束变量,变为现在的自由变量了。

计算过程的多重形态

我们可以用不同种类的过程来完成同一件任务,那么在真正的程序设计的时候,我们应该选用哪种方式呢?按照之前数据结构的角度来看,我们有两个指标:时间复杂度和空间复杂度。不同的过程自然有这不同的计算过程,我们应该通过衡量两个不同计算过程的上述的两个指标来确定最终选择哪一个作为最终版本。这就要求我们能够准确的观察到任何一个过程执行的过程和执行的效果,以及执行过程中所耗费的各种资源。

递归和迭代应该是两种非常重要的计算形式。如果一个问题同时可以用这样两种形式解决,那么我们应该选择哪一种呢?

在以实例说明递归和迭代的区别之前,首先要明确这样两个概念的区别:

递归计算进程:是计算中的情况和具体的执行行为,反映计算中需要耗费资源维持的过程执行的某些信息和情况。 用递归方式定义过程:是程序写法,在定义过程的代码里出现了对这个过程本身的调用,但是实际的计算过程可能并不需要耗费资源来进行维持过程的执行情况。

假如现在有一个求n的阶乘的需求:我们有正向和逆向两种思路来求得结果

反向(线性递归)

算法如下:n! = n (n-1)! = n (n-1) (n-2)!…..2 1 = n * (n-1)!

有了具体的计算进程,我们可以根据它来写一个过程

(define (factorial n) (if (= n 1) 1 (* n (factorial (- n 1)))))

PS:可以看出这个过程在定义的时候调用了自身

假设现在我们想计算(factorial 6),根据shceme的代换模型推导,可以得出如下计算进程图示:

计算机中的黑魔法:尾递归

从图示中我们可以看出,当我们计算(factorial 6)的时候,根据计算过程的定义,要执行(* 6 (factorial (- 6 1)))。通过这一个复合的表达式我们就可以看出来,(factorial 6)这一步的计算结果并没有计算出来,它需要计算下一个状态来辅助它得出(factorial 6)这一步的计算结果。因为本次的计算没有完成要进行其他的运算来辅助完成,那么本次的运算就算是中断了,既然中断了,我们就需要保存现场,保存此次计算过程目前的状态(变量等等一些资源)以便当下一状态的计算结果出来之后能够顺利的衔接上,从而计算出最终的结果。以后的计算进程仍然是按照这种形式来的,直到遇到边界。

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/c6b66c1476bb1e840ad5167de46e6595.html