递归函数

一种计算过程，如果其中每一步都要用到前一步或前几步的结果，称为递归的。用递归过程定义的函数，称为递归函数，例如连加、连乘及阶乘等。

提示

递归特性:

提示

1. 调用自身函数

提示

2. 必须有一个明确的结束条件

提示

3. 在计算机中，函数调用是通过栈(stack)这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈帧，每当函数返 回，栈就会减一层栈帧。由于栈的大小不是无限的，所以，递归调用的次数过多，会导致栈溢出。

案例1

package main

import "fmt"

func factorial(n int)int{
	if n == 0{
		return 1
	}
	return n * factorial(n-1)
}

func main() {
	// 计算n的阶乘,即 n！
	var ret = factorial(4)
	fmt.Println(ret)
}

案例2

这个数列生成规则很简单，每一项都是前两项的和，举例

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233……

package main

import "fmt"

func fib(n int) int {
	if n == 2 || n == 1 {
		return 1
	}
	return fib(n-1) + fib(n-2)
}

func main() {
	// 计算n的阶乘,即 n！
	ret:=fib(6)
	fmt.Println(ret)
}