遞歸

遞歸是指函數(shù)直接或間接調(diào)用自己。
遞歸常用于解決分治問題，將大問題分解為相同的小問題進行解決。
遞歸必須要有終止條件。

練習1

package main

import "fmt"

/*
遞歸  大問題分解成相同的小問題，必須有終止條件
f(n) 1..n

0 - 100        f(100)
0 - 99 + 100   f(99) + 100
0 - 98 + 99        f(98) + 99

f(n) = n + f(n-1)
f(1) = 1
*/

/*
addN(5) => 5+ addN(4)
addN(4) => 4 + addN(3)
addN(3) => 3 + addN(2)
addN(2) => 2 + addN(1)
addN(1) => 1 + addN(0)
addN(0) => 0 + addN(-1)
...
必須設(shè)置終止條件
*/
func addN(n int) int {
    if n == 1 {
        return 1
    }
    return n + addN(n-1)
}

func main() {
    fmt.Println(addN(5))
}

練習2 階乘

package main

import "fmt"

/*
n階乘
n! = 1 * 2 * 3 * 4 * 5 ... * n
n = 0 => n! = 1
*/

func factorial(n int) int {
    if n == 0 {
        return 1
    } else if n < 0 {
        return -1
    }
    return n * factorial(n-1)
}

func main() {
    fmt.Println(factorial(5))
    fmt.Println(factorial(-1))
}

練習3 漢諾塔游戲
漢諾塔游戲
將所有A柱上的圓盤借助B柱移動到C柱，在移動過程中保證每個柱子的上面圓盤比下面圓盤小。
可以在網(wǎng)頁上玩一下

package main

import "fmt"

/*
漢諾塔游戲
將所有A柱上的圓盤借助B柱移動到C柱，在移動過程中保證每個柱子的上面圓盤比下面圓盤小
n: A -> C(B)
n=1: A -> C
n>1: n-1(A -> B(C)); A->C; n-1(B->C(A))
*/
func tower(a, b, c string, layer int) {
    if layer == 1 {
        fmt.Println(a, "->", c)
        return
    }
    // A n-1 借助 C 移動到 B
    tower(a, c, b, layer-1)
    fmt.Println(a, "->", c)
    // B n-1 借助 A 移動到 C
    tower(b, a, c, layer-1)
}

func main() {
    fmt.Println("1層:")
    tower("A", "B", "C", 1)
    fmt.Println()
    fmt.Println("2層:")
    tower("A", "B", "C", 2)
    fmt.Println()
    fmt.Println("3層:")
    tower("A", "B", "C", 3)
    fmt.Println()
    fmt.Println("4層:")
    tower("A", "B", "C", 4)
}