GOLangでフィボナッチ数を計算した

はじめに

直近Go言語を勉強していますが、なんか数学問題を解けてみまたいため、フィボナッチ数を計算できるロジックを作成しました。

環境

window 10
VSCode

Target

以下の結果を出力する

フィボナッチ数：(0,1,1,2,3,5...)

簡単に回帰関数を利用して、作りました。

package.go

package main

import "fmt"

func fibonacci() func(x int) int {
	return func(x int) int {
		if x < 2 {
			return x
		}
		f := fibonacci()
		return f(x-2) + f(x-1)
	}
}

func main() {
	f := fibonacci()
	for i := 0; i < 10; i++ {
		fmt.Println(f(i))
	}
}

実行結果：

0
1
1
2
3
5
8
13
21
34

結果ができましたね。しかし、計算量が

O(2^n)

だった。
根本的になおしました。

package.go

package main

import "fmt"

func fibonacci() func(x int) int {
	return func(x int) int {
		a, b:= x%2, 1
		for i := 0;i < x/2; i++{
		  a += b
		  b += a
		}
		return a
	}
}

func main() {
	f := fibonacci()
	for i := 0; i < 10; i++ {
		fmt.Println(f(i))
	}
}

これで良さそうですね。
計算量が

O(n)

になりました。良さそうですね。

以上