iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 10
0

今天要來談的是遞迴,不知道大家小時候有沒有跟我一樣,一看到遞迴就會有種莫名的恐懼,覺得很難去推論出這個遞迴函式到底要做什麼事情,然後到最後就頭暈了…但我沒想到 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

Python 3

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')
  • 根據上述的 Pseudo code,要寫出來並不難,當 n1 時,就是從 A 移到 C。當 n ≥ 2 時,我們就要先把 1~n-1 塊從 A 移到 B,所以這時你可以看到 honoi(n-1, A, C, B) ,也就是子問題 1~n-1 塊如何從 A 透過 C 移到 Bhonoi(1, A, B, C) 把第 n 塊從 A 移到 Chonoi(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

Scala

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}")}
    }
}
  • 概念上與 Python 是一樣的,只是我們這裡 hanoi 的 return type 是 List of tuple,而 tuple 長度為 2,裡頭是 stringstring,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 中第一個元素取出,以此類推。

Golang

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")
}
  • Golang 的部分沒什麼特別的,概念和做法幾乎和 Python 的部分是一模一樣的。

Rust

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");
}
  • Rust 的部分也沒什麼特別的,概念和做法幾乎和 Python 的部分是一模一樣的 XDD。

遞迴注意事項和尾遞迴

  • 遞迴一個很重要要注意的地方是終止條件的設置,並且逐層返回。不然很有可能造成無限遞迴,最後產生 Stack Overflow Error。
  • 為什麼會有 Stack Overflow 呢?那是因為每次當在例如 A Function 去 call B function 時,A 會把目前執行的狀態,包含參數、區域變數、Call B Function 後要返回的 Address 等等資訊放到 Stack 中。假設我們一直遞迴下去的話,最後可以想見 Stack 就會爆掉囉!
  • 這時候我們介紹一個重要的遞迴方式叫做 Tail Recursion,也就是指函數的最後一個動作是直接 Call 自己或是另一個函數,例如下面第一個不是 Tail Recursion,而第二個就是。
# 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)
  • 在 Tail Recursion 的時候,很多語言就會對此進行優化,那是因為如果是 Tail Recursion 的話,其實很容易轉化成迴圈結構的,例如下面這個函式,就是用 Tail Recursion 的方式來加總 1~n,其實就是把本來 For-loop 我們會有一個變數來不斷累加數字,改成是參數傳遞在函式裡面 ( total+n ),而 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 的方式來寫程式,所以不會去使用到迴圈,但其他三個語言在使用迴圈上就自然多了~

結語

今天透過河內塔來看看每個語言如何去撰寫遞迴的程式,希望除了讓你對河內塔問題有所瞭解外,也了解到遞迴之中還有所謂的尾遞迴囉!明天見!


上一篇
[Day 8] 談談映射這件事
下一篇
[Day 10] 零壹零壹零零壹
系列文
30 天把自己榨好榨滿的四週四語言大挑戰!30

尚未有邦友留言

立即登入留言