n=1时为1,即f(n)=1

n=2时,第一步是一步,第二步也是一步这种情况,还有第一步是两步是这种,所有共有2种,即f(2)=2

n>2时,f(n)=f(n-1)+f(n-2)

go实现

package main

import "fmt"

func main() {

	c := step(10)

	fmt.Println(c)
}

func step(n int) int {
	if n == 1 {
		return 1
	} else if n == 2 {
		return 2
	} else {
		return step(n-1) + step(n-2)
	}
}

思路先从前边一个开始，后面直接递归

这算法有点像1+2+3+……+100

go实现

package main

import "fmt"

func main() {

	c := add(100)

	fmt.Println(c)
}

func add(n int) int {
	if n >= 2 {
		return n + add(n-1)
	} else {
		return n
	}
}