Scala中河內塔的尾遞歸

Question

我是新來的Scala編程人員。 我的目標是實施一個河內塔問題的尾遞歸程序。 我相信它可以通過遞歸這樣實現：

// Implementing a recursive function for Towers of Hanoi,where the no of disks is taken as 'n', 'from' being the Start Peg, 'to' being the End Peg, and 'via' being Intermediate Peg 

def move(n: Int, from: Int, to: Int, via: Int) : Unit = { // Recursive Function 
    if (n == 1) { 
    Console.println("Move disk from pole " + from + " to pole " + to)// each move iteration printed. 
} 
else { 
    move(n - 1, from, via, to) //Moving n-1 disks from source to Intermediate 
    move(1, from, to, via) // Printing all the move iterations 
    move(n - 1, via, to, from) //Moving n and other n-1 disks to the final destination 
    } 
} 

它能否實現並採用尾遞歸呢？

Answer 1

有一種方法，它將堆棧移動到參數上。事情是這樣的：

case class Pos(n: Int, from: Int, to: Int, via: Int) 

def move(pos: Pos, rest: List[Pos]) : Unit = { 
    val Pos(n, from, to, via) = pos 
    if (n == 1) { 
    println(s"Move disk from pole $from to pole $to") 
    move(rest.head, rest.tail) 
    } else { 
    val pos1 = Pos(n - 1, from, via, to) 
    val pos2 = Pos(1, from, to, via) 
    val pos3 = Pos(n - 1, via, to from) 
    move(pos1, pos2 :: pos3 :: rest) 
    } 
} 

這通常是獲得尾遞歸出來的東西是不自然尾遞歸，因爲你只需要弄清楚雲堆棧上的最簡單的方法。不幸的是，如果除了遞歸之外還有其他操作，那將會更加困難。

在Scala中可以解決問題的另一種方法是使用非嚴格性，例如Stream。它會是這樣的：

def move(n: Int, from: Int, to: Int, via: Int): Stream[String] = { 
    if (n == 1) Stream(s"Move disk from pole $from to pole $to") 
    else { 
    println(s"$n pins left") 
    move(n - 1, from, via, to) #::: move(1, from, to, via) #::: move(n - 1, via, to, from) 
    } 
} 

然後你只需打印由move返回的字符串。這不是尾遞歸，但是這裏的訣竅是隻有第一個move被評估 - 其他的被保留爲函數，並且只根據需求進行評估。一個適當的Stream（我認爲斯卡拉茲有一個）不會評估這一點。

Answer 2

丹尼爾的偉大的解決方案提醒我，有一種更通用的方法尾部遞歸。你可以使用延續傳球風格http://en.wikipedia.org/wiki/Continuation-passing_style

基本上，如果你不想馬上執行一個方法的其餘部分，你可以把它包裝在一個函數對象中並在以後運行它。在這種情況下，該功能被稱爲延續。

但是我不確定您是否可以將我的代碼視爲真正的尾遞歸。畢竟，我必須定義第二種方法讓編譯器接受它。

import scala.annotation.tailrec 

def move2(n: Int, from: Int, to: Int, via: Int)(c: => Unit) : Unit = move(n, from, to, via)(c) 

@tailrec 
def move(n: Int, from: Int, to: Int, via: Int)(c: => Unit) : Unit = { 
    if (n == 1) { 
    Console.println("Move disk from pole " + from + " to pole " + to) 
    c 
    } else { 
    move(n - 1, from, via, to) { // this is like creating a list made up of two continuations 
     move2(1, from, to, via) {  // 1. this 
     move2(n - 1, via, to, from) { // expression 
     }        // here 
     } 
     c // and 2. the previous continuation 
    } 
    } 
} 

move(3, 1, 3, 2){}