6.golang之递归——斐波那契数

1.斐波那契数

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

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

思路：

1）当 n == 1 || n == 2，返回1

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

package main
import (
	"fmt"
)

func fibonacci(n int) int {
	if (n == 1 || n == 2) {
		return 1
	} else {
		return fibonacci(n - 1) + fibonacci(n - 2) 
	}
}
// 使用递归的方式，求出斐波那契数：1,1,2,3,5,8,13...
func main() {
	res := fibonacci(10)
	fmt.Println("res=",res)
}

2. 求函数值

 

package main
import (
	"fmt"
)

func getSum(n int) int {
	if (n == 1) {
		return 3
	} else {
		return 2 * getSum(n - 1) + 1
	}
}

func main() {
	res := getSum(10)
	fmt.Println("res=",res)
}

3. 猴子吃桃问题

 

package main
import (
	"fmt"
)
// 题目： 有一堆桃子，猴子第一天吃了其中的一半，并再多吃了一个！以后每天猴子都吃其中的一半，然后再多吃一个。当到第十天时，想再吃时（还没吃），发现只有一个桃子了。
// 问题：最初共多少个桃子
func getSum(n int) int {
	if (n == 10) {
		return 1
	} else {
		return 2 * (getSum(n + 1) + 1)
	}
}

func main() {
	res := getSum(1)
	fmt.Println("最初一共有桃子：",res,"个")
}