再帰呼び出しと関数テーブル
今回は再帰呼び出しの話。
再帰呼び出しのサンプルとして典型的なのはフィボナッチ数かな。 フィボナッチ数の定義を愚直にコードにするとこんな感じになる。
package main
import "fmt"
func fibonacciNumber(n int) int {
switch n {
case 0:
return 0
case 1:
return 1
default:
return fibonacciNumber(n-2) + fibonacciNumber(n-1)
}
}
func main() {
fmt.Println(fibonacciNumber(40))
}
一般に手続き型言語は再帰呼び出しに弱いと言われている（関数型のほうが有利）。 特に Go 言語の場合は goroutine に最適化を割り振っている関係で，関数呼び出しやその戻り1 のパフォーマンスが冷遇されているようだ。 したがって，再帰呼び出し部分のパフォーマンスを改善したければ，なるべく呼び出し回数を減らすようにするのがコツである。 たとえば上のフィボナッチ数の場合は
package main
import "fmt"
func fibonacciNumber(n int, fibMap map[int]int) int {
switch n {
case 0:
return 0
case 1:
return 1
default:
if fn, ok := fibMap[n]; ok {
return fn
}
fn := fibonacciNumber(n-2, fibMap) + fibonacciNumber(n-1, fibMap)
fibMap[n] = fn
return fn
}
}
func main() {
fmt.Println(fibonacciNumber(40, make(map[int]int)))
}
という感じに計算結果を保持っておくことでかなり改善する。
ところで，再帰呼び出しで怖いのが無限呼び出しに陥るパターンである。 Go 言語では関数値（function value）を介す場合であれば再帰呼び出しを禁止する。
たとえば先ほどのコードを以下のように書き換えてみる。
package main
import "fmt"
var fibonacciNumbers = make(map[int]int)
func fibonacciNumber(n int) int {
switch n {
case 0:
return 0
case 1:
return 1
default:
if fn, ok := fibonacciNumbers[n]; ok {
return fn
}
fn := fib(n-2) + fib(n-1)
fibonacciNumbers[n] = fn
return fn
}
}
type ff func(int) int
var fib ff = fibonacciNumber
func main() {
fmt.Println(fib(40))
}
fibonacciNumber() を fib() で別名定義しているだけだが，これを実行しようとすると以下のコンパイルエラーになる。
prog.go:25: initialization loop:
prog.go:25 fib refers to
prog.go:7 fibonacciNumber refers to
prog.go:25 fib
関数値 fib の部分でエラーになっている点に注目してほしい。
本当に「ついうっかり」再帰呼び出しになってしまう場合はエラーではじいてもらってありがたいのだが，そうでない場合もある。 あまり例示がうまくなくて申し訳ないのだが，以下の簡単なステート・マシンを考えてみる。
package main
import "fmt"
func f0(evt int) int {
fmt.Println("processing f0")
return 1
}
func f1(evt int) int {
fmt.Println("processing f1")
return 2
}
func f2(evt int) int {
fmt.Println("processing f2")
return 3
}
func f3(evt int) int {
fmt.Println("processing f3")
return 0
}
type fn func(int) int
var fs = []fn{
f0,
f1,
f2,
f3,
}
func StateMachin(stat, evt int) int {
return fs[stat](evt)
}
func main() {
s := 0
for e := 0; e < 10; e++ {
s = StateMachin(s, e)
if s == 0 {
break
}
}
fmt.Println("end")
}
fs が関数テーブルになっていて，状態 s とイベント e に対する処理 fs[s](e) を呼び出して処理後の状態を返してもらう。
一応 StateMachine() 関数で詳細を隠蔽しているつもりである2。
ここで StateMachine(3, evt) の処理に続けて StateMachine(1, evt) の処理がしたくなり
func f3(evt int) int {
fmt.Println("processing f3")
return StateMachin(1, evt)
}
などと書いたらどうなるか。 もちろんこれもコンパイルエラーになる。
prog.go:32: initialization loop:
prog.go:32 fs refers to
prog.go:20 f3 refers to
prog.go:34 StateMachin refers to
prog.go:32 fs
しかし実際には f3 を無限に呼び出しているわけではないので，このコンパイルエラーでは困ってしまう3。
このエラーを回避するには関数テーブル fs を介さなければよい。
たとえば
var fs = []fn{
f0,
f1,
f2,
//f3,
}
func StateMachin(stat, evt int) int {
if stat == 3 {
return f3(evt)
}
return fs[stat](evt)
}
とすれば，めでたく f1 → f2 → f3 → f1 とエンドレスにつながる。
ちなみにここでうっかり
func f3(evt int) int {
fmt.Println("processing f3")
return StateMachin(3, evt)
}
などと書くと，コンパイルエラーにもならず無限呼び出しが発生する。
再帰呼び出しは計画的に。
ブックマーク
- Goで再帰使うと遅くなりますがそれが何だ - YAMAGUCHI::weblog
- .\hoge.go:7: initialization loop - Qiita
- Fibonacci exercise (go tour) - Qiita
- Golangでゴルーチンにより再帰関数を並列処理 : 再帰処理を goroutine で並行処理するという業なコード。 goroutine が大量発生して面白い