最近はアルゴリズムを勉強している。
なかなか頭に入ってこないので、アウトプットをして整理する。
なお、今回は設計技法「再帰」の話。
一連の処理の中で、自分自身を呼び出すことを「再帰呼び出し」と言う。
以下、1からNまでの総和を計算する再帰関数の例を書く。
package main import ( "fmt" ) func recursive(N int) int { fmt.Printf("recursive(%d)を呼び出しました。\n", N) if N == 0 { return 0 } result := N + recursive(N-1) fmt.Printf("%dまでの和 = %d\n", N, result) return result } func main() { recursive(5) } // recursive(5)を呼び出しました。 // recursive(4)を呼び出しました。 // recursive(3)を呼び出しました。 // recursive(2)を呼び出しました。 // recursive(1)を呼び出しました。 // recursive(0)を呼び出しました。 // 1までの和 = 1 // 2までの和 = 3 // 3までの和 = 6 // 4までの和 = 10 // 5までの和 = 15
再帰関数にはある程度テンプレートが決まっており、以下のようになる。
func 関数名 (引数) { if ベースケース { return ベースケースに対する値 } // 再帰呼び出しを行う 関数名(次の引数) return 答え }
ここで、再帰関数を使ってフィボナッチ数列を求める再帰関数を考える。
- フィボナッチ数列とは？ ⇒ 「1,1,2,3,5,8,13,21,34,55…」と続く数列のことで、前2つの値を加算してできる数列のこと。
フィボナッチ数列の漸化式は以下になる。
- F0 = 0
- F1 = 1
- Fn = Fn-1 + Fn-2 (n=2,3,4…)
なお、漸化式とは、ある数列に対して規則性を表す等式のことを指す。
フィボナッチ数列の場合、F0 = 0、 F1 = 1の条件式が成り立つ場合、Fn = Fn-1 + Fn-2 (n=2,3,4…)という規則性があるということ。
package main import ( "fmt" ) func fibo(N int) int { fmt.Printf("fibo(%d)を呼び出しました。\n", N) if N == 0 { return 0 } else if N == 1 { return 1 } result := fibo(N-1) + fibo(N-2) fmt.Printf("%d 項目 = %d\n", N, result) return result } func main() { fibo(5) } // fibo(5)を呼び出しました。 // fibo(4)を呼び出しました。 // fibo(3)を呼び出しました。 // fibo(2)を呼び出しました。 // fibo(1)を呼び出しました。 // fibo(0)を呼び出しました。 // 2 項目 = 1 // fibo(1)を呼び出しました。 // 3 項目 = 2 // fibo(2)を呼び出しました。 // fibo(1)を呼び出しました。 // fibo(0)を呼び出しました。 // 2 項目 = 1 // 4 項目 = 3 // fibo(3)を呼び出しました。 // fibo(2)を呼び出しました。 // fibo(1)を呼び出しました。 // fibo(0)を呼び出しました。 // 2 項目 = 1 // fibo(1)を呼び出しました。 // 3 項目 = 2 // 5 項目 = 5
このフィボナッチ数列のコードは、作成したものの「同じ計算を何度も実行していて効率が極めて悪い」という問題がある。
上記結果を見ても、 fibo(3) , fibo(2) , fibo(1) , fibo(0) を何度か呼び出しているのがわかる。
そもそもフィボナッチ数列は再帰関数を用いなければ、for文（計算量: O(N))でできる問題なので、再帰関数を用いると無駄な計算があることがわかる。
fibofor := [6]int{0, 1} for n := 2; n < 6; n++ { fibofor[n] = fibofor[n-1] + fibofor[n-2] fmt.Printf("%d 項目 = %d\n", n, fibofor[n]) } // 2 項目 = 1 // 3 項目 = 2 // 4 項目 = 3 // 5 項目 = 5
再帰関数で無駄な計算をさせない方法の1つがメモ化（キャッシュとも言う）。
つまり、1度計算した結果を変数に保存しておく方法。
func mfibo(n int, memo []int) int { fmt.Printf("func mfibo(%d) を呼びました\n", n) if memo[n] != -1 { fmt.Println("メモ化した値を返しました") return memo[n] } if n == 0 { memo[0] = 0 return 0 } else if n == 1 { memo[1] = 1 return 1 } memo[n] = mfibo(n-1, memo) + mfibo(n-2, memo) return memo[n] } func main() { // memo初期化 memo := make([]int, 6) for i, _ := range memo { memo[i] = -1 } mfibo(5, memo) fmt.Println("memo => ", memo) } // func mfibo(5) を呼びました // func mfibo(4) を呼びました // func mfibo(3) を呼びました // func mfibo(2) を呼びました // func mfibo(1) を呼びました // func mfibo(0) を呼びました // func mfibo(1) を呼びました // メモ化した値を返しました // func mfibo(2) を呼びました // メモ化した値を返しました // func mfibo(3) を呼びました // メモ化した値を返しました // memo => [0 1 1 2 3 5]
再帰関数は複雑なコードをシンプルに表現することができる手法。
しかし、無駄な計算量コストが増えてしまいがちなので、メモ化して無駄な計算コストを防ぐことが大事だということを学んだ。
アルゴリズムとは無関係の話だが、Go言語は再帰を使うと遅くなるらしい。。。
原因は、再帰関数の引数などを保管する「スタック領域」がGo言語はデフォルトが小さい、かつスタック領域の大きさを最小にするような最適化を行わないかららしい。。。
つまり、再帰呼び出しを行う度に一定量のスタック領域を食いつぶしていくイメージなのかな。。。
あと、再帰をつかったときの計算量がよくわからない。。。今後の課題である🤔
次は、「動的計画法」をやる。
