10.md

斐波那契数列

这个数列从第 3 项开始，每一项都等于前两项之和

题目

大家都知道斐波那契数列，现在要求输入一个整数 n，请你输出斐波那契数列的第 n 项（从 0 开始，第 0 项为 0，第 1 项是 1 ）。 n <= 39

思路

递归

F(0) = 0，F(1) = 1, F(n) = F(n - 1) + F(n - 2)

实现

package main

import "fmt"

func main() {
	fmt.Println(Fibonacci(4))
}

func Fibonacci(n int) int {
	f1 := 0
	f2 := 1
	if n == 0 {
		return f1
	} else if n == 1 {
		return f2
	}
	for i := 1; i < n; i++ {
		tmp := f2
		f2 = f1 + f2
		f1 = tmp
	}
	return f2
}