今天要來談的是遞迴，不知道大家小時候有沒有跟我一樣，一看到遞迴就會有種莫名的恐懼，覺得很難去推論出這個遞迴函式到底要做什麼事情，然後到最後就頭暈了…但我沒想到 Hackerrank 這個遞迴主題的題目就是 Factorial Function 哈哈！這個我們之前在講迴圈的時候已經用過了。所以今天就讓我們來看一個比較再難一個的問題：河內塔問題 吧！如果你對河內塔問題不是很了解的話，可以參考這裡囉！
如果你們已經知道河內塔問題是什麼的話，可以知道有三支柱子從左到右分別為 A、B、C，而一開始在 A 上有 N 個盤子，假使今天 N = 1，那麼步驟就是 A -> C 結束。假使今天 N = 2，那麼步驟就會是 A -> B、A -> C、B -> C 結束，那麼 N > 2 時呢？這時候遞迴的威力就來啦！當 N > 2 是我們可以想像一開始在 A 上面的盤子是 1~N，N 是最底下的盤子的編號，那麼我們就可以把 1~N-1 個盤子暫時先看成是 1 塊超大盤子，那麼這時候不就是變成 N = 2 時的狀況了嗎？1 塊大盤子從 A 移到 B、第 N 塊盤子從 A 移到 C、再把一大塊盤子從 B 移到 C。這時候我們來看 1 塊大盤子要怎麼從 A 移到 B，疑？這時候不就又變成另一個子問題？也就是 1~N-1 個盤子如何從 A 借助 C 移到 B；而一大塊盤子從 B 移到 C 也是，也就是 1~N-1 個盤子如何從 B 借助 A移到 C (除了起點跟終點的柱子，第三根一定就是拿來作輔助)。Pseudo code 如下：
FUNCTION MoveTower(disk, source, dest, spare):
IF disk == 0, THEN:
move disk from source to dest
ELSE:
MoveTower(disk - 1, source, spare, dest)
move disk from source to dest
MoveTower(disk - 1, spare, dest, source)
END IF
def hanoi(n, A, B, C):
if n == 1:
print(f"{A}->{C}")
else:
hanoi(n-1, A, C, B)
hanoi(1, A, B, C)
hanoi(n-1, B, A, C)
n = int(input())
hanoi(int(n), 'A', 'B', 'C')
n 為 1 時，就是從 A 移到 C。當 n ≥ 2 時，我們就要先把 1~n-1 塊從 A 移到 B，所以這時你可以看到 honoi(n-1, A, C, B) ，也就是子問題 1~n-1 塊如何從 A 透過 C 移到 B；honoi(1, A, B, C) 把第 n 塊從 A 移到 C；honoi(n-1, B, A, C) ，也就是子問題 1~n-1 塊如何從 B 透過 A 移到 C。n = 3 會印出A->C
A->B
C->B
A->C
B->A
B->C
A->C
import scala.io.StdIn
object Solution {
def main(args: Array[String]) {
def hanoi(n: Int, a: String, b: String, c: String) : List[(String, String)] = {
if (n == 1) List((a, c))
else hanoi(n - 1, a, c, b) ++ hanoi(1, a, b, c) ++ hanoi(n - 1, b, a, c)
}
print("Input：")
hanoi(StdIn.readInt, "A", "B", "C").foreach { x => println(s"${x._1}->${x._2}")}
}
}
hanoi 的 return type 是 List of tuple，而 tuple 長度為 2，裡頭是 string 跟 string，List 是 Scala 常用的 immutable 結構 (linked list)。而本來在 Python 是直接印出結果，這裡則是當 n = 1 時，回傳 List((a,c)) 表示從 a 移到 c。當 n 不是 1 時，就是回傳 honoi(n-1, a, c, b) ++ honoi(1, a, b, c) ++ honoi(n-1, b, a, c) 這三個 List 組合而成的大 List。 ++ 是用來串接兩個 List。於是我們執行 honoi(StdIn.readInt, "A", "B", "C") 會得到一個 List，代表所有的 Steps，而我們 invoke foreach {x => function(x)} 來把 List 中每個元素取出當作 x 並執行 function(x) ，這裡的 function(x) 就是 println(s"${x._1}->${x._2}") 。這樣的寫法 (x => function(x)) 在 Scala 叫做 anonymous function，在其他語言也可以看到叫做 lambda function。s"${x._1}->${x._2}" 中的 x._1 是把 tuple 中第一個元素取出，以此類推。package main
import (
"bufio"
"fmt"
"os"
"strconv"
)
func hanoi(n int,a string, b string,c string){
if n == 1 {
fmt.Println(a,"->",c)
} else {
hanoi(n-1, a, c, b)
hanoi(1, a, b, c)
hanoi(n-1, b, a, c)
}
}
func main(){
scanner := bufio.NewScanner(os.Stdin)
scanner.Scan()
num, _ := strconv.Atoi(scanner.Text())
hanoi(num, "A", "B", "C")
}
use std::str::FromStr;
use std::io::stdin;
fn move_(n: i32, a: &str, b: &str, c: &str) {
if n == 1 {
println!("{}->{}", a, c);
} else {
move_(n - 1, a, c, b);
move_(1, a, b, c);
move_(n - 1, b, a, c);
}
}
fn main() {
let mut input = String::new();
stdin().read_line(&mut input).expect("Failed to read input");
let n = i32::from_str(input.trim()).expect("Failed to parse i32 from string");
move_(n, "A", "B", "C");
}
# Not tail recursion
def recursion(n):
if n == 1:
return n
else:
return n+recursion(n-1)
# Tail recursion
def recursion(n):
if n == 1:
return n
else:
return recursion(n-1)
n-1 就像是每次迴圈判斷條件的值 (for loop 常看到的 i)。迴圈結構的效能是比遞迴好的。def sum(n, total):
if n == 0:
return total
else:
return sum(n-1, total+n)
}
然而並不是所有語言寫成 Tail Recursion 都會進行效能的優化，例如 Python、Golang、Rust 都沒有，只有 Scala 有。因為在 Scala，我們傾向用 Functional programming 的方式來寫程式，所以不會去使用到迴圈，但其他三個語言在使用迴圈上就自然多了~
今天透過河內塔來看看每個語言如何去撰寫遞迴的程式，希望除了讓你對河內塔問題有所瞭解外，也了解到遞迴之中還有所謂的尾遞迴囉！明天見！
iThome鐵人賽
看影片追技術