递归-阶乘&阶乘算法&汉诺塔

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

[14:54:18 root@go day1]#go run main.go 
120

斐波那契值

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) 又会再去申请一块空间

如果函数无限递归会出现内存溢出的问题，所以我们在做函数递归的时候一定要注意他的结束条件。

当函数调用结束的时候，栈区的内存就会得到释放