再帰呼び出しと関数テーブル

今回は再帰呼び出しの話。

再帰呼び出しのサンプルとして典型的なのはフィボナッチ数かな。 フィボナッチ数の定義を愚直にコードにするとこんな感じになる。

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)
}

とすれば,めでたく f1f2f3f1 とエンドレスにつながる。 ちなみにここでうっかり

func f3(evt int) int {
    fmt.Println("processing f3")
    return StateMachin(3, evt)
}

などと書くと,コンパイルエラーにもならず無限呼び出しが発生する。

再帰呼び出しは計画的に。

ブックマーク

Go 言語に関するブックマーク集はこちら


  1. 再帰呼び出しが「末尾呼び出し(tail call)」の場合は,戻りの最適化でパフォーマンスの向上が期待できるが, Go 言語のコンパイラはこの辺の最適化も行っていないらしい。 ↩︎

  2. 実際には別パッケージにしてちゃんとクラス設計すべきだろうけど色々端折っている。ゴメンペコン。 ↩︎

  3. このコードに限れば StateMachine(1, evt) ではなく f1(evt) を呼び出せば済む話なのでこれは言いがかりであるが,「話の都合」ということで軽く流していただけるとありがたい。 ↩︎