scala - 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(我想 Scalaz 有一个)甚至不会评估。