Scala：尾递归的跟踪调用及其局限

在7.2节中，我们提到过想要把更新var的while循环转换成仅使用val的更函数式风格的话，有时候你可以使用递归。下面的例子是通过不断改善猜测数字来逼近一个值的递归函数：

 
 
 
      
  
  
  1. def approximate(guess: Double): Double =  
    2.   
  
  
  2.  if (isGoodEnough(guess)) guess  
    3.   
  
  
  3.  else approximate(improve(guess))  
    4.

编辑推荐：Scala编程语言专题

这样的函数，带合适的isGoodEnough和improve的实现，经常用在查找问题中。如果想要approximate函数执行得更快，你或许会被诱惑使用while循环编写以尝试加快它的速度，如：

 
 
 
      
  
  
  1. def approximateLoop(initialGuess: Double): Double = {  
    2.   
  
  
  2.  var guess = initialGuess  
    3.   
  
  
  3.  while (!isGoodEnough(guess))  
    4.   
  
  
  4.   guess = improve(guess)  
    5.   
  
  
  5.  guess  
    6.   
  
  
  6. }  
    7.

两种approximate版本哪个更好？就简洁性和避免var而言，***个，函数式的胜出。但是否指令式的方式或许会更有效率呢？实际上，如果我们测量执行的时间就会发现它们几乎完全相同！这可能很令人惊奇，因为递归调用看上去比简单的从循环结尾跳到开头要更花时间。

然而，在上面approximate的例子里，Scala编译器可以应用一个重要的优化。注意递归调用是approximate函数体执行的***一件事。像approximate这样，在它们***一个动作调用自己的函数，被称为尾递归：tail recursive。Scala编译器检测到尾递归就用新值更新函数参数，然后把它替换成一个回到函数开头的跳转。

道义上你不应羞于使用递归算法去解决你的问题。递归经常是比基于循环的更优美和简明的方案。如果方案是尾递归，就无须付出任何运行期开销。

跟踪尾递归函数

尾递归函数将不会为每个调用制造新的堆栈框架；所有的调用将在一个框架内执行。这可能会让检查程序的堆栈跟踪并失败的程序员感到惊奇。例如，这个函数调用自身若干次之后抛出一个异常：

 
 
 
      
  
  
  1. def boom(x: Int): Int =  
    2.   
  
  
  2.  if (x == 0) throw new Exception("boom!")  
    3.   
  
  
  3.  else boom(x - 1) + 1 
    4.

这个函数不是尾递归，因为在递归调用之后执行了递增操作。如果执行它，你会得到预期的：

 
 
 
      
  
  
  1. scala> boom(3)  
    2.   
  
  
  2. java.lang.Exception: boom!  
    3.   
  
  
  3.  at .boom(< console>:5)  
    4.   
  
  
  4.  at .boom(< console>:6)  
    5.   
  
  
  5.  at .boom(< console>:6)  
    6.   
  
  
  6.  at .boom(< console>:6)  
    7.   
  
  
  7.  at .< init>(< console>:6)  
    8.   
  
  
  8. ...  
    9.

如果你现在修改了boom从而让它变成尾递归：

 
 
 
      
  
  
  1. def bang(x: Int): Int =  
    2.   
  
  
  2.  if (x == 0) throw new Exception("bang!")  
    3.   
  
  
  3.  else bang(x 1)  
    4.

你会得到：

 
 
 
      
  
  
  1. scala> bang(5)  
    2.   
  
  
  2. java.lang.Exception: bang!  
    3.   
  
  
  3.  at .bang(< console>:5)  
    4.   
  
  
  4.  at .< init>(< console>:6)  
    5.   
  
  
  5. ...  
    6.

这回，你仅看到了bang的一个堆栈框架。或许你会认为bang在调用自己之前就崩溃了，但这不是事实。如果你认为你会在看到堆栈跟踪时被尾调用优化搞糊涂，你可以用开关项关掉它：

 
 
 
      
  
  
  1. -g:notailcalls 
    2.

把这个参数传给scala的shell或者scalac编译器。定义了这个选项，你就能得到一个长长的堆栈跟踪了：

 
 
 
      
  
  
  1. scala> bang(5)  
    2.   
  
  
  2. java.lang.Exception: bang!  
    3.   
  
  
  3.  at .bang(< console>:5)  
    4.   
  
  
  4.  at .bang(< console>:5)  
    5.   
  
  
  5.  at .bang(< console>:5)  
    6.   
  
  
  6.  at .bang(< console>:5)  
    7.   
  
  
  7.  at .bang(< console>:5)  
    8.   
  
  
  8.  at .bang(< console>:5)  
    9.   
  
  
  9.  at .< init>(< console>:6)  
    10.   
  
  
  10. ...  
    11.

尾调用优化

approximate的编译后代码实质上与approximateLoop的编译后代码相同。两个函数编译后都是同样的事三个Java字节码指令。如果你看一下Scala编译器对尾递归方法，approximate，产生的字节码，你会看到尽管isGoodEnough和improve都被方法体调用，approximate却没有。Scala编译器优化了递归调用：

 
 
 
      
  
  
  1. public double approximate(double);  
    2.   
  
  
  2.  Code:  
    3.   
  
  
  3.   0: aload_0  
    4.   
  
  
  4.   1: astore_3  
    5.   
  
  
  5.   2: aload_0  
    6.   
  
  
  6.   3: dload_1  
    7.   
  
  
  7.   4: invokevirtual #24; //Method isGoodEnough:(D)Z  
    8.   
  
  
  8.   7: ifeq 12 
    9.   
  
  
  9.   10: dload_1  
    10.   
  
  
  10.   11: dreturn  
    11.   
  
  
  11.   12: aload_0  
    12.   
  
  
  12.   13: dload_1  
    13.   
  
  
  13.   14: invokevirtual #27; //Method improve:(D)D  
    14.   
  
  
  14.   17: dstore_1  
    15.   
  
  
  15.   18: goto 2 
    16.

尾递归的局限

Scala里尾递归的使用局限很大，因为JVM指令集使实现更加先进的尾递归形式变得很困难。Scala仅优化了直接递归调用使其返回同一个函数。如果递归是间接的，就像在下面的例子里两个互相递归的函数，就没有优化的可能性了：

 
 
 
      
  
  
  1. def isEven(x: Int): Boolean =  
    2.   
  
  
  2.  if (x == 0) true else isOdd(x - 1)  
    3.   
  
  
  3. def isOdd(x: Int): Boolean =  
    4.   
  
  
  4.  if (x == 0) false else isEven(x - 1)  
    5.

同样如果***一个调用是一个函数值你也不能获得尾调用优化。请考虑下列递归代码的实例：

 
 
 
      
  
  
  1. val funValue = nestedFun _  
    2.   
  
  
  2. def nestedFun(x: Int) {  
    3.   
  
  
  3.  if (x != 0) { println(x); funValue(x - 1) }  
    4.   
  
  
  4. }  
    5.

funValue变量指向一个实质是包装了nestedFun的调用的函数值。当你把这个函数值应用到参数上，它会转向把nestedFun应用到同一个参数，并返回结果。因此你或许希望Scala编译器能执行尾调用优化，但在这个例子里做不到。因此，尾调用优化受限于方法或嵌套函数在***一个操作调用本身，而没有转到某个函数值或什么其它的中间函数的情况。（如果你还不能完全明白尾递归，参见8.9节）。

【相关阅读】

  1. Scala允许的重复参数
  2. 学习Scala的闭包
  3. Scala的偏应用函数
  4. Scala：函数文本的短格式和占位符语法
  5. 介绍Scala的***类函数

文章名称：Scala：尾递归的跟踪调用及其局限
文章出自：http://www.shufengxianlan.com/qtweb/news1/351901.html

网站建设、网络推广公司-创新互联，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联

猜你还喜欢下面的内容

软件开发知识

行业网站建设

租用服务器　　 　王君美油画　　 　成都店面装修公司　　 　四川锦华橡塑　　 　成都微信开发　　 　成都模板网站　　 　川银永信　　 　香港云主机　　 　成都h5网站建设　　 　香港云空间　　 　古巴雪茄　　 　手机网站制作　　 　西云服务器托管　　 　力比特工程　　 　混凝土密封固化剂　　 　成都封阳台　　 　重庆移动网站建设　　 　雅安服务器托管　　 　资阳网站建设　　 　成都网站维护