尾遞歸失敗（可能是因爲隱式缺點轉換）

Question

我有我相信是一個相當簡單的尾遞歸函數。然而，@tailrec告訴我，否則。

@tailrec 
    def _next(continue : String, current : List[Long], first : Boolean) : Stream[Long] = { 
    current match { 
     case head :: tail => head #:: _next(continue, tail, false) //this line breaks tailrec 
     case Nil if first => empty 
     case _ => { 
     val (nc, nl) = getIds(continue) 
     _next(nc, nl, true) 
     } 
    } 
    } 

呈現我

[error] could not optimize @tailrec annotated method _next: it contains a recursive call not in tail position 
[error] case head :: tail => head #:: _next(continue, tail, false) 
[error]         ^

它可能與我從日食接受隱通知做的事：- Implicit conversions found: _next(continue, tail, false) => consWrapper(_next(continue, tail, false))，但不幸的是，這是沒有幫助我解決問題。

我該如何解決這個問題，並且，對於布朗尼分，我哪裏去錯了，認爲這會尾部遞歸？

Answer 1

問題是您代碼中的最後一項操作不是_next的調用，而是Stream cons操作#::。

一個解決方案是使用StreamBuilder構建流並將此StreamBuilder作爲累加器變量保留。

@tailrec 
    def _next(continue : String, current : List[Long], first : Boolean, acc: Stream.StreamBuilder[Long]) : Stream[Long] = { 
    current match { 
     case head :: tail => 
     acc += head 
     _next(continue, tail, false, acc) 
     case Nil if first => acc.result 
     case _ => { 
     val (nc, nl) = getIds(continue) 
     _next(nc, nl, true, acc) 
     } 
    } 
    } 

這不是特別有效的 - 如果你使用的++=，而不是+=添加收藏全給它的StreamBuilder是比較合適的。出於這個原因，考慮改變你的代碼是這樣的：

@tailrec 
    def _next(continue : String, current : List[Long], first : Boolean, acc: Stream.StreamBuilder[Long]) : Stream[Long] = { 
    current match { 
     case Nil => 
     acc.result 
     case list => 
     acc += list 
     val (nc, nl) = getIds(continue) 
     _next(nc, nl, true, acc) 
    } 
    }