这样的尾递归“解释”......

By include at 2019-07-20 • 1人收藏 • 231人看过

今天看到了两篇“解释”尾递归的文章,吓得我重新查了下尾递归的定义。

[漫谈递归:从斐波那契开始了解尾递归](http://www.nowamagic.net/librarys/veda/detail/2325)

[递归与尾递归](https://uternet.github.io/2014-05-18/tail_recursion.html)


第一篇使用了斐波那契数列的计算作为例子,斐波那契的计算是为人所知的,分为递归式和迭代式两种,也有所谓的缓存方法(好像有人称之为DP方法)。

 

在第一篇文章中,首先使用的是传统的递归计算,也就是

fib(n) => fib(n - 1) + fib (n - 2);

然后使用了迭代方法,也就是

fab(n, 1, 1) => fab(n - 1, 2, 1) => fib(n - 2, 3, 2) ......

(他的时间统计方法我也就懒得吐槽了,第二篇也提到了)

这样的讲解,对于斐波那契数列的计算来说,当然什么问题都没有,但是他文中的一些观点是值得商榷的:

  1. 尾递归的本质是:将单次计算的结果缓存起来,传递给下次调用,相当于自动积累



这句话看上去没有问题,但是,单次计算的结果就一定要传递给下次调用,并积累到一处吗?

他将斐波那契的递归计算改为了尾递归,这一点是没有问题的,但是计算方式也随之发生了改变,由原来的递归式计算变为了迭代式计算。速度当然上去了,但使用尾递归就一定可以提高效率吗?尾递归就一定得是迭代计算方式吗?既然可以尾递归,那使用循环描述可是方便的多。


第二篇对第一篇的鸡毛蒜皮的小错进行了修正,但是感觉还是没有 get 到点。


Scheme 中的尾递归优化,是为了解决使用函数递归进行迭代式计算可能造成栈溢出的问题的。


正如第二篇文章中的斐波那契函数

(define (fibonacci n)
  (if (<= n 2)
      1
      (+ (fibonacci (- n 1))
         (fibonacci (- n 2)))))
      
(define (fibonacci n a1 a2)
  (cond
   ((= n 0) 0)
   ((< n 2) a1)
   (else
    (fibonacci (- n 1) a2 (+ a1 a2)))))

那能不能使用递归的计算方法进行尾递归呢?

(define fib1
  (lambda (n k)
    (cond
     ((= n 1) (k 1))
     ((= n 2) (k 1))
     (else
      (fib1 (- n 1)
        (lambda (k2)
          (fib1 (- n 2) (lambda(k3)(k (+ k3 k2))))))))))
(define Identity (lambda (x) x))
(trace fib1)
(fib1 5 Identity)

(define fib2
  (lambda (n k)
    (cond
     ((= n 1) (k 1 0))
     ((= n 2) (k 1 0))
     (else
      (fib2 (- n 1)
        (lambda (k2 k3)
          (fib2 (- n 2) (lambda (x y)(k (+ k2 k3) (+ x y))))))))))
(define two (lambda (x y) (+ x y)))
(trace fib2)
(fib2 5 two)

通过 trace 观察整个过程,整个过程调用只有一条,也就是这个样子:

> (fib1 5 I)
|(fib1 5 #<procedure Identity>)
|(fib1 4 #<procedure>)
|(fib1 3 #<procedure>)
|(fib1 2 #<procedure>)
|(fib1 1 #<procedure>)
|(fib1 2 #<procedure>)
|(fib1 3 #<procedure>)
|(fib1 2 #<procedure>)
|(fib1 1 #<procedure>)
|5
5

所谓的尾递归,直观地看,恐怕就是“在函数的尾部调用函数自身”的意思。

这里写的思路并不是太清晰,我的本意是说明尾递归不一定非要是迭代式的计算,若有不解之处或认为文中描述有问题,希望提出来。


5 个回复 | 最后更新于 30 天前
2019-07-20   #1

感谢分享,  很多细节的地方确实以前没有思考过, 从你的帖子里面也衍生一些思考. 谈一下我的理解 ( 本人不是很科班, 对于语言的理解很不系统, 希望大家指正. ). 我觉得楼主说的是对的, 尾递归实际上应该只是简单的函数尾部调用自身. 


于是我产生了一个问题, 那么以迭代方式的尾调用和楼主说的有什么区别呢? 


我尝试思考了一下, 我的觉得实际上的区别更多的是来自于类似于实现算法的区别. 通常的递归调用有可能会对子问题进行重复计算.


fib(5) => fib(4) + fib (3);


比如当我们计算第五个数时, 我们必须重复进行第三个数的计算.

对于这样的问题, 很基本的优化方式就是记忆化. 缓存一部分之前计算的子问题的结果,  当对当前问题求值时就不用重复计算了. 而具体到斐波那契数列, 当前的结果只与前两个状态相关, 所以只需要两个变量就足够了. 


def fibonacci(n):

    a = 0

    b = 1

    if n < 0: print("Incorrect input")

    elif n == 0: return a

    elif n == 1: return b

    else: for i in range(2, n): c = a + b a = b b = c

        return b


如果我们用一个列表来表示对应的子问题, 并且如果问题涉及到一些子问题的最优化如 max, min 之类的, 那么这就是一个动态规划的解法了. 

而迭代方式的尾递归, 对我个人而言就是将函数参数用作存储用的变量, 这样的话尾递归和循环调用确实是等价的.


回到楼主提到的非迭代的方法的尾递归, 实际上是楼主手写 cps 来实现尾递归形式. 


那么这样的调用方式和迭代形式的尾递归又有什么区别呢?


 cps 可以看作是延续的等价形式, 所以楼主所做的类似于将原本并非是尾递归形式的代码, 通过 cps 转化成了一连串的延续. 这样子做的好处是, 所有调用被转化成尾递归所以在支持尾递归消除的编译器中不会出现爆栈的状况. (在 python 这样子的语言中, 尾递归还是会爆栈, 所以需要利用像 trampoline 这样的手段来消除这个问题.) 但是 cps 实现的尾递归对于计算是没有优化的, 所以它和普通递归的计算的复杂度是相同的, 还是会对子问题进行重复计算. 

比如对迭代形式的尾递归进行 trace:


> (fibonacci 5 1 1)

|(fibonacci 5 1 1)

|(fibonacci 4 1 2)

|(fibonacci 3 2 3)

|(fibonacci 2 3 5)

|(fibonacci 1 5 8)

|5

5

我们可以发现会比 fib1 要少一部分的计算. (我觉得也可以拿 尾递归不会增加延续 这个结论来解释, 但我有点说不上来)

事实上很多解释器是自动支持 cps 变换的.(垠神的40行代码?) 我记得我曾经上过一门导论, 老师提到过 ocaml 会帮你自动优化, 所以写两种形式(递归和尾递归)的代码都是可以的. 但现在想来好像其实不等价, 但我不确定是否 ocaml 的编译器会做更多优化, 对 chezscheme 也有同样的疑问. 


我的这些理解, 大部分都来源于 topl 讨论如何写 cps 解释器的章节. 我上的课一直是以授课为主的. 我也没上过编译器和解释器的课程, 缺乏对于研究和论文书写的训练, 所以用词很不严谨, 还望大家指正. 



2019-07-20   #2

回复#1 @sughiy :

谢谢回答,我也是非科班,用语也并不是很标准。

我之所以要提上面两篇文章中的问题,是因为我感觉,在我上面提到的两篇文章中,从斐波那契的递归方法计算经过““尾递归”变换”直接成为了迭代式计算,这里有一个跳跃,那就是算法的改变。我写这个,只是为了说明尾递归不一定是迭代的计算方式。

确实,我的方法用了 CPS  变换,使得整个函数递归过程是尾递归的,你在贴子中说的

所以楼主所做的类似于将原本并非是尾递归形式的代码, 
通过 cps 转化成了一连串的延续. 这样子做的好处是, 
所有调用被转化成尾递归所以在支持尾递归消除的编译
器中不会出现爆栈的状况.

的确,我把函数调用的延续给消除了,但该做的计算还是一点都不会少,计算得出的值被”包进“了代表延续的匿名函数中,如果计算量过大,内存照样不够用,毕竟匿名函数也是要内存的。爆不爆栈我不知道,匿名函数应该是存储在堆上的 :p

用于有些口水化,如果绝对有欠妥之处,欢迎指出。


2019-07-20   #3

回复#2 @include :

我的理解和你是一样的,感觉cps就是做了堆和栈上的交换。

2019-07-23   #4


首先看待一个问题


什么是递归?以及递归的问题所在?


递归就是函数调用自身,这一点没有问题。


那么递归的问题在哪里呢?


我们先看一下普通的函数调用,如果函数在求值时,发现参数位是另一个函数,那么就会保存下来当前栈,先求值这个“另一个”函数,等到得到值,再用栈上的其他参数进行计算。


这一点也是没有问题的。


那么问题在哪呢?


问题在每次保存栈,都会耗用一定的栈内存,而一个运行时的栈内存一般不大,如果函数嵌套过深,耗用的栈内存就会超出系统分配的,于是爆栈了。


这里可以看出,爆栈和递归其实没啥关系。如果我手写几十万行嵌套函数,一样会爆栈。


那么为啥递归函数常常会和爆栈联系起来呢?因为递归的特性,使得它可以很轻易的构建无穷无尽的函数嵌套。不仅几十万,几百万,无限都可以。


所以,你看爆栈其实关隘不在递归,而在于嵌套过深。


那么什么是尾递归呢? 先不要管尾,也不要管CPS啥的。


就记住一点,尾递归就是人为的增加一个参数,让调用子函数时,将当前栈当作值传入子函数,这样当前栈就可以被释放了(需要编译器进行行为优化)。这样无论如何嵌套,都不会超出栈大小而爆栈了。


Scheme(和现代一些智能编译器)可以将尾递归优化成循环,比如CPS什么,这个是编译器优化实现手段,而不是尾递归的本质。

30 天前   #5

回复#4 @guenchi :

感谢解释,

登录后方可回帖

登 录
信息栏

Scheme中文社区

推荐实现 ChezScheme / r6rs / r7rs large
theschemer.org
Q群: 724577239

精华导览

社区项目

包管理器:Raven
HTTP服务器:Igropyr (希腊火)
官方插件:vscode-chez

社区目标:

完善足以使Scheme工程化和商业化的库,特别是开发极致速度的Web服务器和ANN模块。

一直以来Scheme缺少一个活跃的中文社区,同时中文资料的稀少,导致大多数因为黑客与画家和SICP而接触Scheme的朋友,在学完SICP后无事可做,不能将Scheme转换为实际的生产力。最后渐渐的放弃。
同时Chicken等实现,却因效率问题无法与其他语言竞争。本社区只有一个目的,传播Scheme的文明之火,在最快的编译器实现上,集众人之力发展出足够与其他语言竞争的社区和库。


友情链接:

Clojure 中文论坛
函数式·China


Loading...