这篇文章主要讲解了“Scala尾递归的跟踪调用及局限方法是什么”,文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习“Scala尾递归的跟踪调用及局限方法是什么”吧!
想要把更新var的while循环转换成仅使用val的更函数式风格的话,有时候你可以使用递归。下面的例子是通过不断改善猜测数字来逼近一个值的递归函数:
def approximate(guess: Double): Double = if (isGoodEnough(guess)) guess else approximate(improve(guess))
这样的函数,带合适的isGoodEnough和improve的实现,经常用在查找问题中。如果想要approximate函数执行得更快,你或许会被诱惑使用while循环编写以尝试加快它的速度,如:
def approximateLoop(initialGuess: Double): Double = { var guess = initialGuess while (!isGoodEnough(guess)) guess = improve(guess) guess }
两种approximate版本哪个更好?就简洁性和避免var而言,***个,函数式的胜出。但是否指令式的方式或许会更有效率呢?实际上,如果我们测量执行的时间就会发现它们几乎完全相同!这可能很令人惊奇,因为递归调用看上去比简单的从循环结尾跳到开头要更花时间。
然而,在上面approximate的例子里,Scala编译器可以应用一个重要的优化。注意递归调用是approximate函数体执行的***一件事。像approximate这样,在它们***一个动作调用自己的函数,被称为尾递归:tail recursive。Scala编译器检测到尾递归就用新值更新函数参数,然后把它替换成一个回到函数开头的跳转。
道义上你不应羞于使用递归算法去解决你的问题。递归经常是比基于循环的更优美和简明的方案。如果方案是尾递归,就无须付出任何运行期开销。
跟踪尾递归函数
尾递归函数将不会为每个调用制造新的堆栈框架;所有的调用将在一个框架内执行。这可能会让检查程序的堆栈跟踪并失败的程序员感到惊奇。例如,这个函数调用自身若干次之后抛出一个异常:
def boom(x: Int): Int = if (x == 0) throw new Exception("boom!") else boom(x - 1) + 1
这个函数不是尾递归,因为在递归调用之后执行了递增操作。如果执行它,你会得到预期的:
scala> boom(3) java.lang.Exception: boom! at .boom(< console>:5) at .boom(< console>:6) at .boom(< console>:6) at .boom(< console>:6) at .< init>(< console>:6) ...
如果你现在修改了boom从而让它变成尾递归:
def bang(x: Int): Int = if (x == 0) throw new Exception("bang!") else bang(x 1)
你会得到:
scala> bang(5) java.lang.Exception: bang! at .bang(< console>:5) at .< init>(< console>:6) ...
这回,你仅看到了bang的一个堆栈框架。或许你会认为bang在调用自己之前就崩溃了,但这不是事实。如果你认为你会在看到堆栈跟踪时被尾调用优化搞糊涂,你可以用开关项关掉它:
-g:notailcalls
把这个参数传给scala的shell或者scalac编译器。定义了这个选项,你就能得到一个长长的堆栈跟踪了:
scala> bang(5) java.lang.Exception: bang! at .bang(< console>:5) at .bang(< console>:5) at .bang(< console>:5) at .bang(< console>:5) at .bang(< console>:5) at .bang(< console>:5) at .< init>(< console>:6) ...
尾调用优化
approximate的编译后代码实质上与approximateLoop的编译后代码相同。两个函数编译后都是同样的事三个Java字节码指令。如果你看一下Scala编译器对尾递归方法,approximate,产生的字节码,你会看到尽管isGoodEnough和improve都被方法体调用,approximate却没有。Scala编译器优化了递归调用:
public double approximate(double); Code: 0: aload_0 1: astore_3 2: aload_0 3: dload_1 4: invokevirtual #24; //Method isGoodEnough:(D)Z 7: ifeq 12 10: dload_1 11: dreturn 12: aload_0 13: dload_1 14: invokevirtual #27; //Method improve:(D)D 17: dstore_1 18: goto 2
尾递归的局限
Scala里尾递归的使用局限很大,因为JVM指令集使实现更加先进的尾递归形式变得很困难。Scala仅优化了直接递归调用使其返回同一个函数。如果递归是间接的,就像在下面的例子里两个互相递归的函数,就没有优化的可能性了:
def isEven(x: Int): Boolean = if (x == 0) true else isOdd(x - 1) def isOdd(x: Int): Boolean = if (x == 0) false else isEven(x - 1)
同样如果***一个调用是一个函数值你也不能获得尾调用优化。请考虑下列递归代码的实例:
val funValue = nestedFun _ def nestedFun(x: Int) { if (x != 0) { println(x); funValue(x - 1) } }
funValue变量指向一个实质是包装了nestedFun的调用的函数值。当你把这个函数值应用到参数上,它会转向把nestedFun应用到同一个参数,并返回结果。因此你或许希望Scala编译器能执行尾调用优化,但在这个例子里做不到。因此,尾调用优化受限于方法或嵌套函数在***一个操作调用本身,而没有转到某个函数值或什么其它的中间函数的情况。
感谢各位的阅读,以上就是“Scala尾递归的跟踪调用及局限方法是什么”的内容了,经过本文的学习后,相信大家对Scala尾递归的跟踪调用及局限方法是什么这一问题有了更深刻的体会,具体使用情况还需要大家实践验证。这里是亿速云,小编将为大家推送更多相关知识点的文章,欢迎关注!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。