Question

1. 通常一个不断更新 var 的 while 循环可以修改为递归函数。

   
   xxxxxxxxxx
   //************ while 版本 *****************//
   def func(init_guess: Double) : Double = {
       var guess = init_guess
       while(!=is_ok(guess))        // 不满足条件，继续迭代
         guess = improve(guess)
       guess // 返回结果
   }
   ​
   //************ 递归函数 版本 *****************//
   def func(guess : Double) : Double = {
       if (is_ok(guess)) guess       // 满足条件，返回
       else func(impove(guess))      // 不满足条件，继续递归
   }

   • 从代码简洁性来讲，递归函数的版本更好。但是从执行效率上讲，通常 while 版本更好。

   • 如果递归函数是尾递归的，则这两个版本的执行效率一样高。尾递归tail recursive：递归函数的递归发生在函数的最后一步。

     因为 Scala 编译器会执行尾递归优化。当Scala 检测到尾递归时，编译器将其替换为跳到函数的最开始，并且在跳转之前将参数更新为新的值。这样尾递归并不会在每次调用时都构建一个新的栈帧，所有的调用都会在同一个栈帧中执行。

     这在调试尾递归函数时可能会是不利影响。如果你对调试信息感到困惑，可以将尾递归优化关闭，方法是 scala 命令或者 scalac 编译器添加参数 -g:notailcalls。 一旦调试结果，可以继续打开尾递归优化。

2. 在Scala 中使用尾递归比较受限，因为Scala 只能对那些在函数末尾直接调用自己的函数做优化。如果递归调用是间接的，则无法使用尾递归优化。

   • 最后一个表达式是递归调用之后再做了其它操作：无法使用尾递归优化。

     
     xxxxxxxxxx
     def func(x: Int) : Int =
     {
       if (x==0) 0
       else func(x-1) + 1   // 无法使用尾递归优化，因为最后一个表达式是 func 的间接调用：调用之后再加 1
     }

   • 相互递归调用：无法使用尾递归优化。

     
     xxxxxxxxxx
     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)

   • 最后一步调用的是一个值函数（而不是发起调用的那个函数自己）：无法使用尾递归优化。

     
     xxxxxxxxxx
     var funValue = (x :Int) => x+1
     def func(x: Int) : Int = {
         if(x!=0) {println(x); funValue(x-1)}
         else 0
     }
     funValue = func _ // 现在 funValue 指向一个打包了 func 函数的值函数对象