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){}