14-Golang函数-递归

递归

递归是指函数直接或间接调用自己。
递归常用于解决分治问题，将大问题分解为相同的小问题进行解决。
递归必须要有终止条件。

练习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)
...
必须设置终止条件
*/
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柱，在移动过程中保证每个柱子的上面圆盘比下面圆盘小。
可以在网页上玩一下

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