庄周梦蝶

生活、程序、未来
   :: 首页 ::  ::  :: 聚合  :: 管理

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

Posted on 2008-03-18 19:34 dennis 阅读(7634) 评论(11)  编辑  收藏 所属分类: 计算机科学与基础
    读《代码大全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 11)
            (
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第一章里有更详细的介绍和讨论。


评论

# re: 用递归计算阶乘咋不行呢?  回复  更多评论   

2008-03-18 19:44 by 久城
不了解函数式语言,但是《代码大全》还是很不错的。

刚进公司时买了一本...

很遗憾,到现在也没看完几章...

有时间要好好学习一下了。

# re: 用递归计算阶乘咋不行呢?  回复  更多评论   

2008-03-19 17:20 by CowNew开源团队
阶乘的非递归算法也很简单呀,不知道为什么很多教科书讲阶乘的时候都用递归算法。
//实例性代码,未考虑大数值的计算溢出问题
private int calcFact(int value)
{
int fact = 1;
for (int i = 2; i <= value; i++)
{
fact *= i;
}
return fact;
}

# re: 用递归计算阶乘咋不行呢?  回复  更多评论   

2008-03-19 17:36 by ZelluX
@CowNew开源团队
Thinking in Lisp...

# re: 用递归计算阶乘咋不行呢?  回复  更多评论   

2008-03-19 17:47 by dennis
@CowNew开源团队
教科书上讲阶乘都是用递归算法,这是因为阶乘就是用递归定义的嘛
n=1 fac(n)=1
n>1 fac(n)=n*fac(n-1)

类似Lisp这样的函数式语言能将数学公式直接描述出来(what to do,而非how to do),Lisp本来就是为了解决符号推断而发展起来的,比如用Lisp求函数导数,你能想象用java做出来吗?做出来也够呛。

# re: 用递归计算阶乘咋不行呢?  回复  更多评论   

2008-03-19 19:27 by CowNew开源团队
@dennis
阶乘就是用递归定义的吗?“N的阶乘等于1*2*3*4*……*(N-1)*N”

# re: 用递归计算阶乘咋不行呢?  回复  更多评论   

2008-03-19 20:34 by ZelluX
@dennis
不是吧。。递归定义只是一种表达形式而已。。
Lisp只是多了将函数作为基本类型的特性而已,描述上和其他语言还是一样的吧,SICP序言中就提到了它们都是imperative的,而不是数学中更常见的declarative。
Java不能求导不就是因为Java没函数指针或者说callback机制不够强大吗

# re: 用递归计算阶乘咋不行呢?  回复  更多评论   

2008-03-20 09:15 by dennis
@ZelluX
嗯,我得承认我的表述很不恰当,我的本意是Scheme更容易将说明性的数学公式直接翻译为表达式。Lisp模拟函数求导很容易,除了将 函数作为一等公民的特性外,更重要的是可以将符号作为数据来平等对待,如果用java来做,恐怕要自己搞一个类似词法分析的东东。

# re: 用递归计算阶乘咋不行呢?  回复  更多评论   

2008-03-20 09:40 by ZelluX
@dennis
需要什么词法分析。。
dy/dx不就行了吗

double derivative = (f(x + EPISILON) - f(x)) / EPESILON;

# re: 用递归计算阶乘咋不行呢?  回复  更多评论   

2008-03-20 10:07 by dennis
@ZelluX
我说的是符号求导,比如求函数2x^2的导数是4x

# re: 用递归计算阶乘咋不行呢?[未登录]  回复  更多评论   

2008-04-08 19:54 by 闲耘
才知道尾递归,学习。
http://blog.xianyun.org/2008/04/08/factorial-and-tail-recursion/

# re: 用递归计算阶乘咋不行呢?  回复  更多评论   

2010-02-01 18:03 by zagfai
@CowNew开源团队

无知...

函数式没循环

只有注册用户登录后才能发表评论。


网站导航: