1 递归
递归是指函数直接或间接调用自己,递归常用于解决分治问题,将大问题分解为相同的小问题进行解决,需要关注终止条件
我们每做一个递归的时候一定要判断清楚递归的结束条件是什么
阶乘
package main
import "fmt"
func fact(n int) int {
// 结束条件
if n < 0 {
return -1
}
if n == 0 {
return 1
}
// 间接调用
return n * fact(n-1)
}
func main() {
/*
阶乘
n1 = 1 * 2 * 3 * n => (n - 1) * n
fact(3) = 3 * fact(2)
fact(2) = 2 * fact(1)
fact(1) = 1 * fact(0)
*/
fmt.Println(fact(5))
}
斐波那契值
package main
import "fmt"
func fbn(n int) int {
if n == 0 {
return 0
}
if n <= 2 {
return 1
}
res := 0
for i := 3; i <= n; i++ {
// 间接调用
res = fbn(i-1) + fbn(i-2)
}
return res
}
func main() {
res := fbn(5)
fmt.Println(res)
}
汉诺塔
package main
import "fmt"
/*
a => 开始
b => 借助
c => 终止
layer => 盘子数量
*/
func tower(a, b, c string, layer int) {
// 终止条件
// 如果 layers 只有 1 层是就将 a 的盘子移动到 C
if layer == 1 {
fmt.Println(a, "->", c)
return
}
// layer - 1 a -> B
// 将 a 移动到 b
// 函数直接调用自己本身
tower(a, c, b, layer-1)
fmt.Println(a, "->", c)
// b 上的盘子移动到 c
tower(b, a, c, layer-1)
}
func main() {
/*
汉诺塔:
n 个盘子:(开始) A -> (终止) c (借助) B
n-1 个盘子 -> B 借助 C
n - 2 A -> C
n - 1 A -> B
n - 2 C -> B
将第 n 个盘子 -> C
B 的 n-1 -> C 借助 A
*/
tower("1", "2", "3", 3)
}
1.2 函数调用逻辑
程序运行时会在内存中分配一块空间,程序在启动时会有一个自己的代码区。
可以理解为内存的地址,是由低地址到高地址,代码区完了以后会有一个数据区
数据区完了以后是堆,堆中间是一个空闲的,然后空闲的空间过了就是栈
堆和栈是用来分配和释放的,当一个进程在使用堆的时候,申请是由低地址到高地址申请的,栈则是相反的是由高地址向低地址去申请。
栈:函数调用的时候,栈用来存储函数调用之间存储的关系
每个函数调用的时候都会在内存中去申请一块空间,当一个函数调用另外一个函数的时候,会在栈区向下申请一个空间
当fact(3)
调用 fact(2)
函数时候会在栈区在申请一块空空间,向下存储。然后 fact(2)
在调用 fact(1)
又会再去申请一块空间
如果函数无限递归会出现内存溢出的问题,所以我们在做函数递归的时候一定要注意他的结束条件。
当函数调用结束的时候,栈区的内存就会得到释放