Go

A Tour of Go の Exercise: Fibonacci closure 解答例

はじめに

Go 言語基礎文法最速マスターにて出題されている演習課題「Exercise: Fibonacci closure（フィボナッチ クロージャ）」の答えに辿り着くまでの手順と解答例の解説を記事にしてみました。フィボナッチ数列、クロージャ、ネームリターンバリュー、ネイキッドリターンなどについても簡単に説明しています。

課題

課題の目的は、下記のコードに フィボナッチ数（0, 1, 1, 2, 3, 5, …）を返す fibonacci 関数の実装をすることです。

package main

import "fmt"

// fibonacci is a function that returns
// a function that returns an int.
func fibonacci() func() int {
}

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

解答例

package main

import "fmt"

func fibonacci() func() int {
	f0, f1 := 0, 1

	return func() (x int) {
		x = f0
		f0, f1 = f1, f0 + f1
		return
	}
}

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

解説

初めに、フィボナッチ数列について簡単に説明します。

フィボナッチ数列とは、1202 年にイタリアの数学者 レオナルド・フィボナッチ によって書かれた書籍 算盤の書 で紹介された数列です。

この数列は、下記のような最初の 2 つの数が 0, 1 で、3 つ目以降は前の 2 つの数の和を並べたものです。

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 ...

漸化式（ぜんかしき）は F0 = 0, F1 = 1, Fn+2 = Fn + Fn+1 (n ≥ 0) のように定義されています。

漸化式がわからない人は気にしないでください、知らなくても大丈夫です。

花弁の数、松毬や仙人掌の螺旋構造、葉序、向日葵の種の配列などがフィボナッチ数になっており、自然界にはフィボナッチ数が多く存在していると言われているとか、いないとか、根拠はないよ。

このような神秘的な話から占いやオカルト、スピリチュアルビジネスでよく使われる数列です。

では、フィボナッチ数が何となくわかったところで課題のソースコードを読み解きます。

5 〜 6 行目、fibonacci 関数は int を返すとコメントがありますね。

// fibonacci is a function that returns
// a function that returns an int.

7 〜 8 行目、fibonacci 関数の戻り値が func() int になっています。

func fibonacci() func() int {
}

戻り値が 無名関数 って…どういうことだってばよ？って思いますよね。

Function closures に説明がある通り、Go の関数は closure（クロージャー）です。

クロージャーとは、自身の外部から変数を参照する関数値のことです。

つまり、フィボナッチ数を返すクロージャーを実装する必要があるってことがわかります。

10 〜 15 行目、main 関数では fibonacci 関数を変数 f に格納して、for 文で 10 回繰り返し変数 f を呼び出し、戻り値を fmt.Println 関数で出力しています。

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

つまり、ループカウンターの値がフィボナッチ数の項になるということですね。

さて、実装を進める前にフィボナッチ数の実装方法を考える必要があります。考えるのがめんどくさい場合は ループ処理による実装例 を参考に実装すると良いです。

フィボナッチ数列は「最初の 2 つの数が 0, 1 で、3 つ目以降は前の 2 つの数の和を並べたもの」なので、下記のようなコードを考えると思います。

func fibonacci() func() int {
	f0, f1 := 0, 1

	return func() int {
		f0, f1 = f1, f0 + f1
		return f0
	}
}

でも、間違えています。出力すると 1 から始まるフィボナッチ数列になっちゃいます。

課題の目標は 0 から始まるフィボナッチ数を出力することなので、下記のように変数を 1 つ用意して工夫をします。

func fibonacci() func() int {
	f0, f1 := 0, 1

	return func() (x int) {
		x = f0
		f0, f1 = f1, f0 + f1
		return
	}
}

クロージャーの戻り値に x という名前を付けています、これを Named return values（ネームリターンバリュー）と言います。

ネームリターンバリューを使うと return の後に何も書かずに戻すことができます、これを naked return（ネイキッドリターン）と言います。

今回のような短い関数で使うと効果的です。

実行すると下記のように出力されます。

0
1
1
2
3
5
8
13
21
34

大丈夫だ、問題ない。

あれ、でも何で f() が実行される度に変数が破棄されないのか疑問に思いませんでしたか。

これはクロージャーがローカル変数の状態を保持できる関数だからです。

通常は関数の呼び出しが終わるとローカル変数を破棄しますよね、でもクロージャーはローカル変数を保持することができるんです。

今回の課題で説明すると、まず main 関数で fibonacci 関数が実行されますよね。

f := fibonacci()

この時、fibonacci 関数の戻り値は func() int なので、func() int のアドレスが変数 f に格納されます。

そして、func() int は元の関数であるfibonacci 関数の変数 f0, f1 をローカル変数に保持します。

for 文の中で f() が実行される度に func() int が実行されます、変数 f には func() int のアドレスが格納されているからですね。

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

func() int は実行される度に保持しているローカル変数を更新して返します。

return func() (x int) {
  x = f0
  f0, f1 = f1, f0 + f1
  return
}

だから同じ値が出力されないんですね。

以上です。

おわりに

クロージャーを理解することは、ひとくろーじゃー。