函数递归

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

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

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

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇