2

I'm new to programming in Scala. My aim is to implement a tail-recursive program for the Towers of Hanoi problem. I believe it can be achieved by recursion like this:

// 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
  } 
}

Can it implemented using tail-recursion as well?

4

2 回答 2

4

有一种方法，将堆栈移动到移动的参数。像这样的东西：

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 有一个）甚至不会评估。

于 2013-10-06T08:41:10.917 回答
2

Daniel 的出色解决方案提醒我，有一种更通用的方法可以使方法尾递归。您可以使用延续传递风格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){}
于 2013-10-08T21:40:20.630 回答