方案中的河内塔（递归）

Question

今天在scheme中写了如下代码，但是求值错误。请不要告诉我我编程很糟糕，我知道这是一个经典的递归问题，但我遇到了麻烦：

(define (towers-of-hanoi n source temp dest)
 (if (= n 1)
  (begin (display "Move the disk from ")
         (display source) 
         (display " to " )
         (display dest)
         (newline))
 (begin (towers-of-hanoi (- n 1) source temp dest)
        (display "Move the disk from ") 
        (display source)
        (display " to ")
        (display dest)
        (newline)
  (towers-of-hanoi(- n 1) temp source dest))))

我期望代码能够工作，当我调试它时，我只是更加困惑。谁能帮我？

Answer 1

在您的代码中，最后一个递归调用似乎是错误的，并且过程参数的顺序存在问题。试试这个：

(define (towers-of-hanoi n source dest temp)
  (if (= n 1)
      (begin 
        (display "Move the disk from ")
        (display source) 
        (display " to " )
        (display dest)
        (newline))
      (begin 
        (towers-of-hanoi (- n 1) source temp dest)
        (display "Move the disk from ") 
        (display source)
        (display " to ")
        (display dest)
        (newline)
        (towers-of-hanoi (- n 1) temp dest source))))

我注意到您一直在问标记为 的问题racket，这是针对 Racket 的相同代码的更惯用和更短的版本：

(define (towers-of-hanoi n source dest temp)
  (cond [(= n 1)
         (printf "Move the disk from ~a to ~a~n" source dest)]
        [else
         (towers-of-hanoi (sub1 n) source temp dest)
         (printf "Move the disk from ~a to ~a~n" source dest)
         (towers-of-hanoi (sub1 n) temp dest source)]))

无论哪种方式，它都会按预期工作：

(towers-of-hanoi 3 "source" "dest" "temp")

Move the disk from source to dest
Move the disk from source to temp
Move the disk from dest to temp
Move the disk from source to dest
Move the disk from temp to source
Move the disk from temp to dest
Move the disk from source to dest