尾遞歸缺點操作者的Scala

如果在一個函數的最後一個語句是FUNC（X，tailList）：尾遞歸缺點操作者的Scala

def func(x:Int):List[Int]... 
    case head :: tailList => head :: func(x,tailList)

這個函數轉換爲尾遞歸需要添加累加器作爲第三參數（並且保持它乾淨的添加func（）內的本地函數）。

insertTail(x,tailList,head::acc)

似乎不能正常工作。不應該「acc」持有正在進行的計算？

我在這裏錯過了什麼使它與累加器的遞歸工作？

添加一個更完整的例子

def funcTailTest(x:Int,xs:List[Int]):List[Int] = { 
@tailrec 
def inner(x:Int,xs:List[Int],acc:List[Int]) : List[Int] = xs match { 

    case head::tailList => { 
    inner(x,tailList,head::acc) 
    } 
} 
inner(x,xs,Nil) 

}

主要負責人應被加入到內（）函數的輸出，使W/O企圖使它的情況下尾遞歸的最後一條語句看起來

head::inner(x,tailList)

來源

2012-07-25 Vikas Pandya

如果您提供一個更完整的示例，這將有所幫助。 – Dirk 2012-07-25 13:51:06

''x''會發生什麼？是否應該添加到tailList的末尾？ – 2012-07-25 13:52:02

添加完整示例的編輯問題。 – 2012-07-25 13:59:17

假定反過來也是尾遞歸實現（它絕對可以是），以下是一個尾遞歸追加：

def append[T](y: T, xs: List[T]): List[T] = { 
    @tailrec 
    def appendAcc[T](y: T, xs: List[T], acc: List[T]): List[T] = xs match { 
    case Nil => y :: acc 
    case x :: xs => appendAcc(y, xs, x :: acc) 
    } 

    appendAcc(y, xs, Nil).reverse 
}

來源

2012-07-25 14:16:51

反向不是尾遞歸，它根本不是遞歸的。 https://github.com/scala/scala/blob/v2.9.2/src/library/scala/collection/immutable/List.scala#L1但是你說得對，用尾遞歸方式寫它非常簡單。 – 2012-07-25 14:36:46

以下是Scala的功能使用cons操作

def reverseUtility(ele: List[Int], res: List[Int]):List[Int] ={ 
    ele match { 
    case Nil => Nil 
    case x :: Nil => x :: res 
    case x :: y => reverseUtility(y, (x::res)) 
}}

傳遞的Int名單，並呼籲res(result)作爲函數的參數列表爲空來實現尾遞歸。該功能的時間複雜度爲O（N）

來源

2015-05-13 10:31:38

尾遞歸缺點操作者的Scala

回答

相關問題