1.遞歸與尾遞歸

1.1 遞歸

1.1.1 遞歸定義

遞歸大家都不陌生，一個函數(shù)直接或間接的調(diào)用它自己本身馆铁，就是遞歸。它通常把一個大型復(fù)雜的問題層層轉(zhuǎn)化為一個與原問題相似的規(guī)模較小的問題來求解歉胶，遞歸策略只需少量的代碼就可以執(zhí)行多次重復(fù)的計算献联。

1.1.2 遞歸的條件

一般來說，遞歸需要有邊界條件颠焦、遞歸前進段和遞歸返回段斩熊。當(dāng)邊界條件不滿足時，遞歸前進伐庭；當(dāng)邊界條件滿足時粉渠，遞歸返回。

以遞歸方式實現(xiàn)階乘函數(shù)的實現(xiàn)：

代碼清單1-1

def factorial(n:Int): Long ={
    if(n <= 0) 1
    else n * factorial(n-1)
}

代碼清單中圾另，if(n <= 0) 1是遞歸返回段霸株，else后面部分是遞歸前進段。

1.1.3 遞歸的缺點：

• 需要保持調(diào)用堆棧,如代碼清單1-1,每一次遞歸都要保存n*factorial(n-1)棧幀信息集乔。如果調(diào)用次數(shù)太多去件，可能會導(dǎo)致棧溢出
• 效率會比較低，遞歸就是不斷的調(diào)用自己本身，如果方法本身比較復(fù)雜尤溜，每次調(diào)用自己效率會較低倔叼。

1.2 尾遞歸

1.2.1 定義

尾遞歸的定義比較簡單，即函數(shù)在函數(shù)體最后調(diào)用它本身宫莱，就被稱為尾遞歸丈攒。

我們可以這樣理解尾遞歸

• 所有遞歸形式的調(diào)用都出現(xiàn)在函數(shù)的末尾
• 遞歸調(diào)用是整個函數(shù)體中最后執(zhí)行的語句且它的返回值不屬于表達式的一部分

1.2.2 例子程序

下面我們使用尾遞歸的模式實現(xiàn)上面的階乘

代碼清單1-2

def factorial(n:Int):Long = {
    @tailrec
    def factorial(main:Int,aggr:Int): Long ={
        if(main <= 0) aggr
        else factorial(main-1,main*aggr)
    }
    
   factorial(n,1)
}

我們可以比較代碼清單1-1和1-2
1-1中，每次的遞歸調(diào)用都要本身時依賴n這個變量授霸，所以巡验，它只能是個不同的遞歸。

1-2中绝葡，函數(shù)factorial每次返回的都是它自己本身深碱，沒有依賴任何值。它做的是將main每次減1藏畅，將aggr每次乘main敷硅，然后將這兩個結(jié)果作為下一次遞歸調(diào)用的參數(shù)，進行調(diào)用愉阎。

尾遞歸的核心思想是通過參數(shù)來傳遞每一次的調(diào)用結(jié)果绞蹦，達到不壓棧。它維護著一個迭代器和一個累加器榜旦。

1.3 循環(huán)

循環(huán)能夠解決大多數(shù)的累計問題幽七，循環(huán)可以完成累加和迭代，處理問題比較簡單溅呢，思想也比較符合澡屡，容易理解

n的階乘循環(huán)的寫法

代碼清單1-3

def fibfor(n:Int): Int ={
    var m = 1
    for (i <- 1 to n) {
        m = m * i
    }
    m
}

循環(huán)版本，會有var的可變變量咐旧，我們知道驶鹉，函數(shù)式編程就應(yīng)該更函數(shù)范，我們盡可能的要用vals去替換可變的vars
所以我們可以使用遞歸的方式來消除掉vars

2.改寫 (循環(huán)铣墨，遞歸 TO 尾遞歸)

事實上室埋，scala都是將尾遞歸直接編譯成循環(huán)模式的。所以我們可以大膽的說伊约，所有的循環(huán)模式都能改寫為尾遞歸的寫法模式

尾遞歸會維護一個或多個累計值(aggregate)參數(shù)和一個迭代參數(shù)姚淆。我們具體分析

2.1迭代器和累計器

• 累計值參數(shù)aggregate將每次循環(huán)產(chǎn)生的結(jié)果進行累計，然后傳到下一次的調(diào)用中屡律。

• 迭代器腌逢，和普通遞歸或循環(huán)一樣，每次遞歸或循環(huán)后疹尾，改變一次上忍。(如for(i=0;i<1-;i++)里面的i)

2.2 普通遞歸轉(zhuǎn)換為尾遞歸

并不是所有的遞歸都能改寫為尾遞歸骤肛，那些比較復(fù)雜的遞歸調(diào)用時無法優(yōu)化為尾遞歸的纳本。但是大部分還是能夠進行優(yōu)化的窍蓝。

代碼清單1-1 和代碼清單 1-2 是求n階階乘的普通遞歸與尾遞歸的寫法，前者沒有進行優(yōu)化繁成，每次調(diào)用都會壓棧吓笙。
后者，通過定義一個aggregate(累計)參數(shù)巾腕，對每一次調(diào)用后的結(jié)果做一次累計,而另一個參數(shù)main稱為迭代器,每一次調(diào)用都會-1面睛，當(dāng)達到符合返回的條件時，將累計值返回尊搬。

2.3 循環(huán)（while loop）轉(zhuǎn)為尾遞歸（tail recursion）

正如上文循環(huán)例子所述叁鉴，存在var,函數(shù)式編程就應(yīng)該有函數(shù)范，我們盡量使用val來代替佛寿，所以接下來來看幌墓，怎么將循環(huán)轉(zhuǎn)換為尾遞歸

2.3.1 循環(huán)和尾遞歸

正如上文所說的迭代器和累計器，循環(huán)和尾遞歸都有這兩個概念

迭代器和累計器

尾遞歸每一次的調(diào)用自身都會有一次累加（或者累積冀泻，累減等）常侣，然后會有一個迭代器進行迭代，一個累加器進行累加迭代的結(jié)果弹渔，然后作為參數(shù)胳施，再去調(diào)用自身。

2.3.2 如上面求n階乘的尾遞歸例子：

• 1.循環(huán)的例子中存在一個var肢专，它在每次循環(huán)中充當(dāng)一個累加器的角色舞肆，累加每一次的迭代結(jié)果，而每次迭代過程就是m*i的一個過程博杖。

• 2.尾遞歸也是一樣的思想椿胯，以main作為迭代器，每次遞減1欧募，類似循環(huán)里的i压状，以aggr作為累加器，每次累計迭代的結(jié)果跟继，類似循環(huán)的m种冬。

• 3.相對于普通的遞歸，這里尾遞歸多的一個參數(shù)就是累加器aggr舔糖，用于累計每一次遞歸迭代的結(jié)果娱两。這樣做的目的就是每一次調(diào)用的結(jié)果可以作為下一次函數(shù)調(diào)用的參數(shù)。

3.具體示例-加深理解

3.1 例子1 - 求斐波拉契數(shù)列

• 普通遞歸寫法（性能較低）

def fibonacci(n:Int): Long ={
    n match {
      case 1 | 2 => 1
      case _ => fibonacci(n-1) + fibonacci(n-2)
    }
}

• 循環(huán)的寫法（循環(huán)寫法）

def fibonacciFor(n:Int): Int = {
    var current = 1
    var next = 1
    if(n <=2) 1
    else {
        for(i <- 2 until n) {
            var aggr = current + next
            current = next
            next = aggr
        }   
        next
    }

}

可以看到金吗，aggr是累加器十兢，然后將累加的值賦值給下一個next趣竣，而current等于next，每一次循環(huán)旱物，都有給current和next賦予新值,當(dāng)累加完成后遥缕，返回next的值。

• 尾遞歸寫法

如何對其進行優(yōu)化宵呛？

仔細(xì)分析,上面的普通循環(huán)单匣，每一輪兩個值都在改變，然后又一個累加器aggr宝穗，對這兩個值進行累加户秤，并賦值給更大的next，然后進入下一次循環(huán)逮矛。

尾遞歸鸡号，我們也是同樣的做法，定義兩個接受值须鼎，當(dāng)前的鲸伴，和下一個，然后需要一個累加值莉兰。

這里普通方法的遞歸調(diào)用是兩個原函數(shù)相加挑围，涉及到的變量有 n , n-1 , n-2

因此,我們在考慮使用尾遞歸時，可能也需要使用到三個參數(shù)糖荒，初略涉及杉辙，尾遞歸函數(shù)需要使用三個參數(shù)，于是改寫如下：

def fibonacci(n: Int): Long = {
    @tailrec
    def fibonacciTail(main: Int, current: Int, next: Int): Long = {
      main match {
        case 1 | 2 => next
        case _ => fibonacciByTail(main - 1, next, current+next)
      }
      fibonacciTail(n, 1, 1)
    }
    
    fibonacciTail(n,1,1)

}

使用尾遞歸和模式匹配捶朵。每一次調(diào)用自身蜘矢，將next賦值給current，然后累加current和next的值賦值給新的next值综看，call下一輪品腹。思想上和上面循環(huán)很像。但是更函數(shù)范红碑，消除掉了var舞吭。

3.2 例子2 - loadBalance算法

需求，設(shè)計一個程序析珊，傳入一個比例數(shù)組羡鸥，比如Array（1,3,6,一直調(diào)用該函數(shù)，返回的3個節(jié)點的比例也應(yīng)該如傳入的1:3:6的比例一樣忠寻。

• 我最開始使用for循環(huán)和return實現(xiàn)了這個需求惧浴，代碼如下：

def loadBalance(arr:Array[Int]): Int ={
      //根據(jù)傳入的數(shù)組使用scan高級函數(shù)進行變化，具體算法例子：
      //eg （1奕剃，3衷旅，6） ->  (1,4,10)
      //這樣的目的是捐腿，隨機出來的值為0-1時，選擇第一個節(jié)點柿顶，為1-4時選擇第二節(jié)點茄袖，依次類推
      val segment:Array[Int] = arr.scan(0)(_ + _).drop(1)
      //隨機數(shù)的范圍，根據(jù)傳入的數(shù)組的數(shù)據(jù)之和來九串，例如上的便是 10 绞佩，產(chǎn)生的隨機數(shù)介于0 - 9 之間
      val weightSum:Int  = arr.sum
      val random = new Random().nextInt(weightSum)
      
      for(i <- 0 until segment.size ){
        if(random < segment(i)){

          return i
        }

      }
    0
}

我通過測試程序調(diào)用1萬次該方法寺鸥，返回的隨機節(jié)點的比例是符合傳入的比例的猪钮。

思考：

雖然這樣可以達到目的，但是代碼寫的既不優(yōu)雅胆建，在scala函數(shù)式編程中最好是不能使用return來強行打斷函數(shù)執(zhí)行的烤低，并且在最后，我還需要去寫一個0來作為默認(rèn)返回笆载。

尾遞歸優(yōu)化

大部分或者幾乎所有的for循環(huán)都能使用尾遞歸進行優(yōu)化扑馁，那上面這個代碼如何進行優(yōu)化呢？

思路：上文的for循環(huán)凉驻，每次增加的是segment的下標(biāo)腻要，每循環(huán)一次 +1，因此涝登，我們在設(shè)計尾遞歸時雄家，可以使用一個參數(shù)來實現(xiàn)相同的功能，而另一個參數(shù)應(yīng)該就是產(chǎn)生的隨機數(shù)胀滚。
ok趟济，我們來進行實現(xiàn)

def loadBalance(arr:Array[Int]): Int ={
      //根據(jù)傳入的數(shù)組使用scan高級函數(shù)進行變化，具體算法例子：
      //eg （1咽笼，3顷编，6） ->  (1,4,10)
      //這樣的目的是，隨機出來的值為0-1時剑刑，選擇第一個節(jié)點媳纬，為1-4時選擇第二節(jié)點，依次類推
      val segment:Array[Int] = arr.scan(0)(_ + _).drop(1)
      //隨機數(shù)的范圍施掏，根據(jù)傳入的數(shù)組的數(shù)據(jù)之和來钮惠，例如上的便是 10 ，產(chǎn)生的隨機數(shù)介于0 - 9 之間
      val weightSum:Int  = arr.sum
      val random = new Random().nextInt(weightSum)
      //寫一個內(nèi)部方法
      def loadUtil(rand:Int,index:Int) {
        //assert其监，保證程序健壯
        assert(index < arr.length && arr(index) >= 0)
          
        if(rand < segment(index)) index
        else loadUtil(rand,index+1)
      }
    loadUtil(random,0)
}

我們可以看到萌腿，使用尾遞歸的做法，代碼會非常的優(yōu)雅抖苦，現(xiàn)在寫一個測試類進行測試毁菱！

def main(args: Array[String]): Unit = {
    val arr = Array(1,2,7)
    val countMap = collection.mutable.Map[Int,Int]()

    for(_ <- 1 until 100000) {
      val res = loadBalance(arr)

      countMap.get(res) match {
        case Some(x) => countMap += (res -> (x+1))
        case None => countMap +=(res -> 1)
      }
    }

    countMap.foreach(x => {
      println(s"${x._1}  調(diào)用次數(shù) ${x._2}")
    })
    
  }

//測試10000次米死，返回結(jié)果如下：

2  調(diào)用次數(shù) 69966
1  調(diào)用次數(shù) 20028
0  調(diào)用次數(shù) 10005

如上，測試是通過的贮庞！是不是很優(yōu)雅峦筒，感受到了尾遞歸的魅力？

4. scala編譯器對尾遞歸的優(yōu)化

Scala 對形式上嚴(yán)格的尾遞歸進行了優(yōu)化窗慎，對于嚴(yán)格的尾遞歸物喷，不需要注解

@tailrec 可以讓編譯器去檢查該函數(shù)到底是不是尾遞歸，如果不是會報錯

具體以上面那個計算斐波拉契數(shù)列的例子進行性能分析

def time[T](t: =>T): T  = {
    val b = System.nanoTime()
    val x = t
    val e = System.nanoTime();
    println("time: " + (e-b)/1000 + "us");
    x
    
}

var count: Long = 0
  // @tailrec
  def fib2(n: Long): Long = {
    count += 1
    n match {
      case 1 | 2 => 1
      case _ =>
        fib2(n-1) + fib2(n-2)
    }
  }

通過上面時間和調(diào)用次數(shù)的測試遮斥，可以得出尾遞歸的性能消耗很低峦失，速度很快。

4.1 編譯器對尾遞歸的優(yōu)化

當(dāng)編譯器檢測到一個函數(shù)調(diào)用是尾遞歸的時候术吗，它就覆蓋當(dāng)前的活動記錄而不是在棧中去創(chuàng)建一個新的尉辑。

scala編譯器會察覺到尾遞歸，并對其進行優(yōu)化较屿，將它編譯成循環(huán)的模式隧魄。

4.2 Scala尾遞歸的限制

• 尾遞歸有嚴(yán)格的要求，就是最后一個語句是遞歸調(diào)用隘蝎，因此寫法比較嚴(yán)格购啄。

• 尾遞歸最后調(diào)用的必須是它本身，間接的賦值它本身的函數(shù)也無法進行優(yōu)化嘱么。

5. 總結(jié)

循環(huán)調(diào)用都是一個累計器和一個迭代器的作用狮含，同理，尾遞歸也是如此拱撵，它也是通過累加和迭代將結(jié)果賦值給新一輪的調(diào)用辉川，通過這個思路，我們可以輕松的將循環(huán)轉(zhuǎn)換為尾遞歸的形式拴测。

[本文完乓旗，歡迎轉(zhuǎn)載，轉(zhuǎn)載請注明出處]