【愚公系列】2022年07月 Go教学课程 025-递归函数

---

一、递归函数

如果一个函数在内部调用自身本身，这个函数就是递归函数。

递归函数的优点是定义简单，逻辑清晰。理论上，所有的递归函数都可以写成循环的方式，但循环的逻辑不如递归清晰。

构成递归的条件：

• 子问题须与原始问题为同样的事，且更为简单
• 不能无限制地调用本身，须有个出口，化简为非递归状况处理

1.递归函数的基本使用

package main

import "fmt"

func main() {
    
   c:=Test(3)
   fmt.Println(c)
}
func Test(n int) int {
    
	// 只有第一排的人才知道自己的排数
	if n == 1{
    
		return 1
	}
	// 如果不是第一排，问一下前一排的人
	r := Test(n-1)
	fmt.Println("前一排的排数：",r)
	// 把前一排人的排数+1，计算出自己的排数。
	return r+1
}

3.相关案例

一个正整数的阶乘（factorial）是所有小于及等于该数的正整数的积，并且0的阶乘为1。自然数n的阶乘写作n!。1808年，基斯顿·卡曼引进这个表示法。
亦即n!=1×2×3×…×(n-1)×n。阶乘亦可以递归方式定义：0!=1，n!=(n-1)!×n。

package main

var s int = 1

func main() {
    
	TestDemo(5)
	print(s)
}
func TestDemo(n int) {
    
	if n == 1 {
    
		return
	}
	s *= n
	TestDemo(n - 1)
}

总结

递归就是一个函数在其内部可以调用其本身，那么这个函数就是递归函数即自己调用自己的函数

• 优点：结构清晰，可读性强，可以极大的减少代码量，用有限的语句来定义对象的无限集合。
• 缺点：效率低，调用栈可能会溢出：函数每次调用都会在内存栈中分配空间，而每个进程的容量是有限的，当调用的层次太多时，就会超出栈的容量，从而导致溢出。