Go函数的递归调用

深碍√TFBOYSˉ_ 2021-07-24 22:10 434阅读 0赞

# 一 点睛 #

一个函数在函数体内调用了本身，我们称为递归调用。

# 二 快速入门1 #

## 1 代码 ##

package main
    import (
       "fmt"
    )
    
    func test(n int) {
       if n > 2 {
          n--
          test(n)
       }
       fmt.Println("n=", n)
    }
    
    func main() {
       test(4)
    }

## 2 图解 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70][]

## 3 测试 ##

n= 2
    n= 2
    n= 3

# 三 快速入门2 #

## 1 代码 ##

package main
    
    import "fmt"
    
    func test2(n int) {
       if n > 2 {
          n-- // 递归必须向退出递归条件逼进，否则就是无限循环调用
          test2(n)
       } else {
          fmt.Println("n=", n)
       }
    }
    
    func main() {
       test2(4)
    }

## 2 图解 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70 1][]

## 3 测试 ##

n= 2

# 四 递归调用的总结 #

函数递归需要遵守的重要原则

**1 执行一个函数时，就创建一个新的受保护的独立空间(新函数栈)。**

**2 函数的局部变量是独立的，不会相互影响。**

**3 递归必须向退出递归的条件逼近，否则就是无限递归。**

**4 当一个函数执行完毕，或者遇到 return，就会返回，遵守谁调用，就将结果返回给谁，同时当函数执行完毕或者返回时，该函数本身也会被系统销毁。**

# 五递归小练习 #

## 1 斐波那契数 ##

**a 需求**

请使用递归的方式，求出斐波那契数 1,1,2,3,5,8,13...

给你一个整数 n，求出它的斐波那契数是多少？

**b 思路**

当 n == 1 || n ==2 , 返回 1

当 n > 2, 返回前面两个数的和 f(n-1) + f(n-2)

**c 代码**

package main
    import (
       "fmt"
    )
    
    func fbn(n int) int {
       if (n == 1 || n == 2) {
          return 1
       } else {
          return fbn(n - 1) + fbn(n - 2)
       }
    }
    
    func main() {
       res := fbn(3)
       // 测试
       fmt.Println("res=", res)
       fmt.Println("res=", fbn(4)) // 3
       fmt.Println("res=", fbn(5)) // 5
       fmt.Println("res=", fbn(6)) // 8
    }

**d 测试**

res= 2
    res= 3
    res= 5
    res= 8

## 2 求函数值 ##

**a 需求**

已知 f(1)=3; f(n) = 2\*f(n-1)+1;

请使用递归的思想编程，求出 f(n)的值?

**b 思路**

直接使用给出的表达式即可完成。

**c 代码**

package main
    
    import (
       "fmt"
    )
    
    func f(n int) int {
       if n == 1 {
          return 3
       } else {
          return 2*f(n-1) + 1
       }
    }
    func main() {
       // 测试一下
       fmt.Println("f(1)=", f(1))
       fmt.Println("f(5)=", f(5))
    }

**d 测试**

f(1)= 3
    f(5)= 63

## 3 猴子吃桃子问题 ##

**a 需求**

有一堆桃子，猴子第一天吃了其中的一半，并再多吃了一个。以后每天猴子都吃其中的一半，然后再多吃一个。当到第十天时，想再吃时 （ 还没吃 ），发现只有 1 个桃子了。问题：最初共多少个桃子？

**b 思路分析**

第 10 天只有一个桃子。

第 9 天桃子 = (第10天桃子数量 + 1) \* 2。

规律: 第 n 天的桃子数据 peach(n) = (peach(n+1) + 1) \* 2。

**c 代码**

package main
    import (
       "fmt"
    )
    
    // n 范围是 1 到 10 之间
    func peach(n int) int {
       if n > 10 || n < 1 {
          fmt.Println("输入的天数不对")
          return 0 // 返回0表示没有得到正确数量
       }
       if n == 10 {
          return 1
       } else {
          return (peach(n + 1) + 1) * 2
       }
    }
    
    func main() {
       fmt.Println("第1天桃子数量是=", peach(1)) //1534
    }

**d 测试**

第1天桃子数量是= 1534

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70]: /images/20210724/4ae0be405a504065b8e60d4b0f7e6db8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70 1]: /images/20210724/7c4646f6d2df494f9273caa0d1d97c19.png