2008-03-18

用递归计算阶乘咋不行呢？

关键字: scheme 递归 代码大全2

    读《代码大全2》，已经读了一半，喘口气。总结八个字：百科全书，受益匪浅。小到一个赋值语句、一个循环的编写，大到需求分析、架构设计，无所不包，看后 半部分目录，更是扯到了重构、软件工艺、程序员的性格特征这样的话题。恰好手边的工作暂时比较有闲，可以实践下“创建高质量的代码”中的部分建议，晚上读 书，第二天就重构，乐在其中。这一部分中对设计、子程序、类、变量、语句的处理建议，可能你平常已经在这么做，可作者这么精辟地概括出来让人叹服，而有些 地方是你平常绝对很少注意的，特别是在变量和三种常见控制语句的处理上。
  
    说说我认为是缺点的地方，就是作者貌似对函数式语言了解很少，举的例子全部用的是广泛应用的静态语言（c/c++,java,vb)。例如作者有这么一句话：如果为我工作的程序员用递归去计算阶乘，那么我宁愿换人。作者对递归的态度相当谨慎，这在静态命令式语言中显然是正确的，但是在函数式语言中，由于有尾递归优化的存在，递归反而是最自然的形式，况且我打心里认为递归更符合人类思维。请注意，在FP中只有尾递归的程序才是线性迭代的，否则写出来的递归可能是线性递归或者树形递归，两种情况下都可能导致堆栈溢出并且性能较差。

scheme写阶乘：

(define (fac n)
  (if (= 1 n)
      1
      (* n (fac (- n 1)))))
  显然这个版本不是尾递归，计算过程是一个线性递归过程，计算(fac 4)的过程如下：

(* 4 （fac 3))
(* 4  (3 * (fac 2)))
(* 4  (3 * (* 2 (fac 1))))
(* 4  (3 * (* 2 1)))
(* 4  (3 * 2))
(* 4 6)
24
    因为解释器是采用应用序求值，需要将表达式完全展开，然后依次求值，在这个过程中，解释器内部需要保存一条长长的推迟计算的轨迹。
改写成一个尾递归版本：


(define (fac n)
  (define (fac-iter product n)
    (if (= 1 n)
        product
        (fac-iter (* n product) (- n 1))))
  (fac-iter 1 n))

 我们来看看它的计算过程：


(fac-iter 1 4)
(fac-iter 4 3)
(fac-iter 12 2)
(fac-iter 24 1)
24


可以看到，在这个过程中，解释器不需要保存计算轨迹，迭代的中间结果通过product变量来保存，这是一个线性迭代的计算过程。
最后再看一个斐波拉契数列的例子：
 


(define (fib n)
  (cond ((= n 0) 0)
            ((= n 1) 1)
            (else
                 (+ (fib (- n 1))  (fib (- n 2))))))
  这个计算过程展开是一个树形递归的过程(为什么说是树形？展开下计算过程就知道），改写为线性迭代：
(define (fib n)
  (define (fib-iter a b count)
     (if (= count 0)
         b
         (fib-iter (+ a b) a (- count 1))))
   (fib-iter 1 0 n))
 
     上述的内容在sicp第一章里有更详细和深入的讨论。
评论
guile 2008-03-20   回复
恩，所以人家Code Complete指的也应该是计算过程，所以说的和你是一个意思，所以难道你还不是挑刺啊：）
dennis_zane 2008-03-19   回复
我没有想偏，我也没有说尾递归是fp的专利，我更强调线性迭代和所谓线性递归是指计算过程。呵呵，这文章不是挑刺。
guile 2008-03-19   回复
人家说的应该就是计算过程，而不是调用的形式，这本来就不是一本介绍开发语言的书，也不可能讨论形式上这些属于语言细节的问题。

你的理解是对的，但是可能想偏了，回想一下SICP相关章节中的一些习题，也会要求你分别用递归和迭代的方式去实现，都是指的计算过程。

另外尾递归也不是FP的专利，只要愿意，C也可以实现一个支持尾递归的编译器来。事实上，我记得IBM JDK141就早已支持尾递归的写法了。
发表评论

您还没有登录，请登录后发表评论

dennis_zane
搜索本博客
我的留言簿
  • 你好,看过你关于自定义classloader的回帖,想问问几个问题:   ...
    -- by llp20_2000
存档
最新评论