Scala：尾遞歸和ListBuffer

我正在學習Scala，並在此過程中遵循Brien的15個練習（http://www.knowing.net/index.php/2006/06/16/15-exercises-to-know-a-programming-language-part-1/）在第二個練習中，我應該實施哈爾變換。我實現了它的大部分，但用尾遞歸的返回值掙扎了好幾個小時。由於編譯器不編譯++ - 或更確切地說是行haar(averages) ++ haar(averagesD)。Scala：尾遞歸和ListBuffer

我在做什麼錯在遞歸函數？
你能否就我的代碼給我其他反饋？

代碼：

import scala.collection.mutable.ListBuffer 
import scala.annotation.tailrec 

object haarWavelet2 { 

    def avg(tpl:Tuple2[Double, Double]):Double = (tpl._1 + tpl._2)/2. 
    def avgD(tpl:Tuple2[Double, Double]):Double = (tpl._1 - tpl._2)/2 
    def total_avg(nums:ListBuffer[Double]):Double = nums.sum/nums.length 

    @tailrec 
    def haar(nums:ListBuffer[Double]):ListBuffer[Double] = { 

    if (nums.length == 1) {return nums} 

    val buffer = new ListBuffer[Tuple2[Double, Double]] 
    for (i <- 0 to nums.length-1 by 2) buffer.append((nums(i), nums(i+1))) 

    val averages = for(tpl <- buffer) yield avg(tpl) 
    val averagesD = for(tpl <- buffer) yield avgD(tpl) 

    haar(averages) ++ haar(averagesD) // does not compile 
    } 

    def main(args: Array[String]): Unit = { 
      print(haar(ListBuffer(8., 5., 6., 2.))) 
    } 
}

來源

2014-01-14 Jon

*我在做什麼錯在遞歸函數？*你執行** **尾遞歸。根據定義** tail **遞歸調用必須是要評估的最後一個**語句，但在您的情況下，最後一個語句是'++'（進行遞歸調用，實際上是其中的兩個，然後才處理結果） –

你在這裏使用可變的'ListBuffer'的任何原因？遞歸函數尖叫「不可變」給我。 'Vector'具有非常好的追加速度。 – KChaloux

尾遞歸形式如下：

def func(x..., value){ 
    if(condition) return value 
    else func(y..., value') 
}

如果你看一下這個表格，你看到的是，爲了評估func所有我需要的是func本身，但有一組不同的參數。因此，只有一個項目要放在堆棧上，並且可以很容易地轉換爲迭代算法。

什麼你已經實現是這樣的：

def func(x...){ 
    if(condition) return value 
    else func(y...) + func(z...)

注意，爲了評估func，你必須首先評估func，運營商+，然後「功能」一次。所以這3個項目需要以非常實際的評估順序放置在堆棧上，這不適用於尾部呼叫優化。上述

來源

2014-01-14 21:15:01 wheaties

繼@wheaties結構，尾遞歸函數應該是這樣的，

@tailrec 
def haar(nums:ListBuffer[Double]): ListBuffer[Double] = { 

    def haarAcc (nums:ListBuffer[Double], acc:ListBuffer[Double]): ListBuffer[Double] = { 
     if (nums.length == 1) return acc 

     // val nums_updated ... 

     haarAcc(nums_updated, averages ++ averagesD) 
    } 

    haarAcc(nums, ListBuffer()) 
}

來源

2014-01-15 08:57:07 elm

爲了確保終止，在'haarAcc'中將'nums.length'定義爲連續調用的單調遞減。 – elm

Scala：尾遞歸和ListBuffer

回答

相關問題