递归
递归是指函数直接或间接调用自己。
递归常用于解决分治问题，将大问题分解为相同的小问题进行解决。
递归必须要有终止条件。
练习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)
}
