設計技法「再帰」を学ぶ - Try T.M Engineer Blog

最近はアルゴリズムを勉強している。

なかなか頭に入ってこないので、アウトプットをして整理する。

なお、今回は設計技法「再帰」の話。

一連の処理の中で、自分自身を呼び出すことを「再帰呼び出し」と言う。

「再帰呼び出しを行う関数」のことを「再帰関数」と言う。

以下、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]