go言語でローカルで定義した関数で再帰する話

go言語でローカルで定義した関数で再帰したいと思うことありますよね。ちょっと横着してクロージャに環境をキャプチャすることを任せてしまってそのコンテキストで木などを再帰的に辿りたいみたいな場合などに。

そんなわけでgoでもローカルで定義した関数上で再帰したいと思ったりしていたのですが。今まで再帰を書くのは無理だと思っていました。

func main() {
    // undefined: fib
    fib := func(n int) int {
        if n <= 1 {
            return n
        }
        return fib(n-1) + fib(n-2)
    }
    fmt.Println(fib(20))
}

そうそう。undefined: fib。定義したローカルの関数がその関数からは参照できずにエラーと言うやつです。

逆に言うと参照できないからエラーになるわけで参照できるようにしてあげれば再帰できるんです(今まで気づきませんでした)。

つまり、varで変数を先に初期化してから関数を代入してあげれば再帰できます。

func main() {
    var fib func(n int) int
    fib = func(n int) int {
        if n <= 1 {
            return n
        }
        return fib(n-1) + fib(n-2)
    }
    fmt.Println(fib(20))  // 6765
}

やりましたね！！