お気楽 Go 言語プログラミング入門

はじめに

前回は関数の基本的な使い方について説明しました。今回は再帰定義について説明します。

関数定義の中で、その関数自身を呼び出すことを「再帰呼び出し (recursive call)」とか「再帰定義 (recursive definition)」といいます。関数の定義に自分自身を使うことができるなんて、何か特別な仕掛があるのではないかと思われるかもしれません。

ところが、再帰定義は特別なことではありません。大昔のプログラミング言語ならばいざしらず、今では再帰呼び出しができないプログラミング言語のほうが珍しいでしょう。もちろん Go 言語の関数も再帰呼び出しが可能です。

●再帰定義の基本

再帰定義というと、Lisp / Scheme のような「関数型言語」の専売特許だと思われている方もいるでしょう。実際、Ｃ言語などの手続き型言語では、再帰定義を難しいテクニックの一つと思い込んでしまい、初心者の方は避けて通ることが多いように思います。再帰定義は、今まで説明した関数の呼び出しとまったく同じなので、難しく考える必要はありません。慣れるまでちょっと苦労するかもしれませんが、ポイントさえつかめば簡単に使いこなすことができるようになります。

まずは簡単な例を見てみましょう。階乗を計算するプログラムです。階乗の定義を下図に示します。

\(\begin{array}{l} 0! = 1 \\ n! = n \times (n - 1)! \end{array}\)

図 : 階乗の定義

階乗の定義からわかるように、n の階乗は n - 1 の階乗がわかれば求めることができます。実は、これをそのままプログラムすることができます。次のリストを見てください。

リスト : 階乗 (sample41.go)

package main
import "fmt"

func fact(n int) int {
    if n == 0 {
        return 1
    } else {
        return n * fact(n - 1)
    }
}

func main() {
    for i := 0; i < 13; i++ {
        fmt.Println(i, ":", fact(i))
    }
}

$ go run sample41.go
0 : 1
1 : 1
2 : 2
3 : 6
4 : 24
5 : 120
6 : 720
7 : 5040
8 : 40320
9 : 362880
10 : 3628800
11 : 39916800
12 : 479001600

関数 fact は引数 n が 0 であれば 1 を返し、そうでなければ n * fact(n - 1) の計算結果を返します。fact の定義で fact 自身を呼び出しています。これが再帰呼び出しです。

階乗と同じように再帰定義で表されるアルゴリズムはたくさんあります。階乗の計算は簡単なので、再帰呼び出しを使わなくても繰り返しでプログラムできますが、再帰で定義されるアルゴリズムのなかには、繰り返しに変換すると複雑なプログラムになってしまうものがあります。

このような場合は、素直に再帰定義を使ったほうがわかりやすいプログラムになり、間違いを犯す危険性が少なくなります。難しいアルゴリズムでも、再帰定義を使うと簡単にプログラムできる場合もあるのです。

●再帰定義のポイント

それでは、再帰定義のポイントを説明しましょう。次の図を見てください。

┌─────┐  ┌─────┐  ┌─────┐  ┌─────┐  ┌─────┐
│Call:1    │->│Call:2    │->│Call:3    │->│Call:4    │->│Call:5    │
│n:4       │  │n:3       │  │n:2       │  │n:1       │  │n:0       │
│value : 24│<-│value : 6 │<-│value : 2 │<-│value : 1 │<-│value : 1 │
└─────┘  └─────┘  └─────┘  └─────┘  └─────┘

        図 : fact の再帰呼び出し（n:引数の値, value:返り値）

上図は関数 fact(4) の呼び出しを表したものです。最初の呼び出し (Call:1) では、引数 n の値は 4 なので n の値を 1 減らして fact を再帰呼び出しします。2 回目の呼び出しでは、引数 n の値に 3 が代入されます。ここで、最初に呼び出したときと、2 回目に呼び出したときでは、引数 n の値が違うことに注意してください。

関数の引数は局所変数として扱われます。前回で説明したように、局所変数には有効範囲（スコープ）があります。引数の場合、その関数が実行されている間だけ有効です。局所変数は関数呼び出しが行われるたびに新しく生成されて、そこに値が代入されます。そして、関数の実行が終了すると、生成された局所変数は廃棄されます。つまり、1 回目の呼び出しと 2 回目の呼び出しでは、引数 n は名前が同じでも異なる変数になるのです。ここが再帰呼び出しを理解するポイントの一つです。

プログラムを見ると変数 n は一つしかありませんが、再帰呼び出しが行われるたびに新しい変数 n が作られていくと考えてください。fact(4) を実行しているときの n は 4 であり、fact(3) を呼び出すときには、この n の値を書き換えるのではなく、新しい変数 n を用意して、そこに 3 を代入するのです。

同様に再帰呼び出しが行われ、5 回目の呼び出し (Call:5) で引数 n が 0 になります。このとき、if の then 節が実行され 1 が返されます。ここで再帰呼び出しが止まります。これを再帰呼び出しの「停止条件」といいます。ここが第 2 のポイントです。停止条件がなかったり、あってもその条件を満たさない場合、関数を際限なく呼び出すことになり、Go 言語であればプログラムの実行は途中で停止します。再帰呼び出しを使う場合は、この停止条件に十分注意してください。

fact(0) は 1 を返して fact(1) に戻ります。fact(1) を実行しているあいだ、引数 n の値は 1 です。したがって、fact(1) の返り値は 1 * 1 を計算して 1 となります。あとは同様に、再帰呼び出しした関数の返り値を使って値を計算し、最後に fact(4) の値 24 を求めることができます。

●ユークリッドの互除法

もう一つ簡単な数値計算の例を示しましょう。負でない整数 a と b の最大公約数を求めるプログラムを「ユークリッド (Euclid) の互除法」で作ります。まず最初に、ユークリッドの互除法を説明します。

[ユークリッドの互除法]
負でない整数 \(a, b \ (a \gt b)\) で、\(a\) を \(b\) で割った余りを \(r\) とする。
このとき、\(a\) と \(b\) の最大公約数は \(b\) と \(r\) の最大公約数に等しい。

ユークリッドの互除法は簡単に証明できます。\(a\) と \(b\) の割り算を式 (1) で表します。

\(a = q \times b + r \quad \quad (1)\)

ここで、\(a\) と \(b\) の最大公約数を \(m\) とすると、\(a = m \times a', \ b = m \times b'\) となります。すると、式 (1) は式 (2) で表すことができます。

\(m \times a' = q \times m \times b' + r \quad \quad (2)\)

左辺は \(m\) で割り切れるので、右辺も \(m\) で割り切れる必要があります。\(q \times m \times b'\) は \(m\) で割り切れるので、\(r\) も \(m\) で割り切れることになります。つまり、\(m\) は \(b\) と \(r\) の公約数であることがわかります。\(b\) と \(r\) の最大公約数を \(m'\) とすると、式 (3) が成り立ちます。

\(m \leq m' \quad \quad (3)\)

次に、\(b = m' \times b'', \ r = m' \times r' \)として式 (1) に代入すると、式 (4) が成り立ちます。

\(a = q \times m' \times b'' + m' \times r' \quad \quad (4)\)

右辺は \(m'\) で割り切れるので、\(a\) も \(m'\) で割り切れる必要があります。つまり、\(m'\) は \(a\) と \(b\) の公約数であることがわかります。したがって、式 (5) が成り立ちます。

\(m' \leq m \quad \quad (5)\)

式 (3) と (5) より \(m = m'\) となり、\(a\) と \(b\) の最大公約数は \(b\) と \(r\) の最大公約数に等しいことが証明されました。

あとは b を a とし、r を b にして同じ計算をすればいいわけです。この計算を繰り返し行うと、a と b はどんどん小さくなっていき、r = 0 になったときの b が最大公約数になります。

プログラムは再帰定義を使って簡単に作ることができます。次のリストを見てください。

リスト : 最大公約数 (sample42.go)

package main
import "fmt"

// 最大公約数
func gcd(a, b int) int {
    if b == 0 {
        return a
    } else {
        return gcd(b, a % b)
    }
}

// 最小公倍数
func lcm(a, b int) int {
    return a * b / gcd(a, b)
}

func main() {
    fmt.Println(gcd(42, 30))
    fmt.Println(gcd(15, 70))
    fmt.Println(lcm(5, 7))
    fmt.Println(lcm(14, 35))
}

関数 gcd は引数 a と b の最大公約数を求めます。b が 0 の場合は a を返します。これが再帰呼び出しの停止条件になります。そうでなければ、gcd を再帰呼び出しして、b と a % b の最大公約数を求めます。gcd はユークリッドの互除法の定義をそのままプログラムしただけです。このように、再帰定義を使うと簡単にプログラムを作ることができます。また、整数 a と b の最小公倍数 (lcm) は a * b / gcd(a, b) で求めることができます。

それでは実行してみましょう。

$ go run sample42.go
6
5
35
70

●累乗の計算

次は累乗を求める関数 pow を作ってみましょう。累乗は x の n 乗という x を n 回掛ける計算です。累乗は x の右上に小さく n を書くことで表されますが、ここでは x ** n と書くことにします。

pow (x, y) = x ** y

x ** 3 = x * x * x;
x ** 4 = x * x * x * x;
x ** 5 = x * x * x * x * x;

  図 : 累乗の計算

今回のプログラムは、引数 x を実数、y を整数とします。単純な繰り返しでプログラムを作ると次のようになります。

リスト : 累乗 (sample43.go)

package main
import "fmt"

func pow(x float64, n int) float64 {
    v := 1.0
    for ; n > 0; n-- {
        v *= x
    }
    return v
}

func main() {
    fmt.Println(pow(2, 16))
    fmt.Println(pow(2, 32))
    fmt.Println(pow(2, 64))
}

$ go run sample43.go
65536
4.294967296e+09
1.8446744073709552e+19

x ** 4  = (x ** 2) ** 2 -> 2 回
x ** 8  = (x ** 4) ** 2 -> 3 回
x ** 16 = (x ** 8) ** 2 -> 4 回

一般化すると
x ** y = (x ** (y / 2)) ** 2       （n は偶数）
x ** y = ((x ** (y / 2)) ** 2) * x （n は奇数）

        図 : 累乗の高速化

この場合、n 回の乗算が必要になります。ところが、式を変形するともっと少ない回数で求めることができます。階乗の計算では n を n - 1 の計算に置き換えていきますが、累乗の場合は y を y / 2 に置き換えていくことができます。y が半分になっていくので減少の度合いが大きくなり、計算回数は少なくて済みます。

それでは、この考え方をプログラムしてみましょう。x ** (y / 2) を計算する部分は、再帰を使えば簡単です。プログラムは次のようになります。

リスト : 累乗 (2)

func pow(x float64, y int) float64 {
    if y == 0 {
        return 1
    } else if z := pow(x, y / 2); y % 2 == 0 {
        return z * z
    } else {
        return x * z * z
    }
}

局所変数 z を定義します。z の値は x ** (y/2) です。これは pow を再帰呼び出しすれば簡単に求めることができます。あとは、y が偶数であれば z * z を返し、奇数であれば x * z * z を返します。このように、再帰呼び出しを使って累乗を効率的に計算することができます。

●末尾再帰と繰り返し

再帰定義のなかで、処理の最後で再帰呼び出しを行う場合を「末尾再帰 (tail recursion)」といいます。英語では tail recursion ですが、日本語では末尾再帰のほかに末端再帰とか終端再帰と呼ぶことがあります。末尾再帰は簡単な処理で繰り返しに変換できることが知られています。

Lisp などの関数型言語や論理型言語の Prolog では、プログラムをコンパイルもしくは実行するときに、末尾再帰を繰り返しに変換する処理系があります。この機能を「末尾再帰最適化」といいます。なかには Scheme ^[*1] のように、言語仕様に末尾再帰最適化を行うことを明記しているプログラミング言語もあります。

たとえば、階乗を計算する関数 fact を思い出してください。fact は最後に n と fact の返り値を乗算しているので、このプログラムは末尾再帰ではありません。これを末尾再帰に変換すると次のようになります。

リスト : 階乗(末尾再帰, sample44.go)

package main
import "fmt"

func facti(n, a int) int {
    if n == 0 {
        return a
    } else {
        return facti(n - 1, a * n)
    }
}

func main() {
    for i := 0; i < 13; i++ {
        fmt.Println(i, ":", facti(i, 1))
    }
}

$ go run sample44.go
0 : 1
1 : 1
2 : 2
3 : 6
4 : 24
5 : 120
6 : 720
7 : 5040
8 : 40320
9 : 362880
10 : 3628800
11 : 39916800
12 : 479001600

最後の再帰呼び出しで、facti の返り値をそのまま返しているので、このプログラムは末尾再帰になっています。これで階乗を計算できるなんて、ちょっと不思議に思われるかもしれません。そこが再帰呼び出しの面白いところです。このプログラムでは引数 a の使い方がポイントです。

たとえば facti(4) を実行すると、このプログラムでは 4 * 3 * 2 * 1 を計算します。このとき、計算の途中経過を引数 a に記憶しているのです。facti の呼び出しを下図に示します。

facti(4, 1)
|   facti(3, 4)
|   |   facti(2, 12)
|   |   |   facti(1, 24)
|   |   |   |   facti(0, 24)
|   |   |   |   => a の値 24 を返す
|   |   |   => 24
|   |   => 24
|   => 24
=> 24

        図 : facti の動作

引数 a には計算途中の値が格納されていることがわかります。このような変数を「累算変数」とか「累算器」といいます。

関数型言語の場合、while文や for文などの繰り返しがないプログラミング言語があります。また、論理型言語 Prolog にも単純な繰り返しはありません。これらのプログラミング言語では、繰り返しのかわりに末尾再帰を使ってプログラミングを行い、末尾再帰最適化によりプログラムを高速に実行することができます。

ところで、最大公約数を求める関数 gcd は末尾再帰になっています。Go 言語は末尾再帰最適化をサポートしていないようですが、繰り返しに変換するのは簡単です。次のリストを見てください。

リスト : 最大公約数を求める (sample45.go)

package main
import "fmt"

func gcdi(a, b int) int {
    for b > 0 {
        a, b = b, a % b
    }
    return a
}

func main() {
    fmt.Println(gcdi(42, 30))
    fmt.Println(gcdi(15, 70))
}

$ go run sample45.go
6
5

関数 gcdi は引数 a, b の値を書き換えることで最大公約数を求めています。再帰定義を使ったプログラムはユークリッドの互除法であることがすぐにわかりますが、繰り返しに変換するとプログラムは少しわかりにくくなると思います。

繰り返しは再帰定義に比べると実行速度やメモリの消費量など効率の点で有利です。このため、何がなんでも繰り返しでプログラムしようとする方もいるでしょう。ところが、再帰定義を使うと簡単にプログラムできるが、繰り返しではとても複雑なプログラムになってしまう場合もあります。したがって、とくに問題がなければ再帰定義を繰り返しに変換する必要はないと思います。複雑なプログラムは、しばらくたつと書いた本人でさえ理解できなくなることがよくあります。わかりやすいプログラムがいちばんです

-- note --------
[*1] Scheme は Lisp の方言の一つです。Scheme は Lisp の標準である Common Lisp よりもシンプルな仕様で、熱心なユーザが多いプログラミング言語です。

●クイックソート

それでは、再帰定義の例題として、高速なソートアルゴリズムを取り上げます。ソートは昔から研究されている分野で、優秀なアルゴリズムが確立しています。その中でもクイックソート (quick sort) は高速なソートアルゴリズムとして有名です。クイックソートはある値を基準にして、要素をそれより大きいものと小さいものの 2 つに分割していくことでソートを行います。2 つに分けた各々のグループを同様に分割して 2 つのグループに分けます。最後はグループの要素が一つになってソートが完了します。

9 5 3 7 6 4 2 8     最初の状態

9 5 3 7 6 4 2 8     7 を枢軸にして左側から 7 以上の値を探し、
L           R       右側から 7 以下の値を探す。

2 5 3 7 6 4 9 8     交換する
L           R

2 5 3 7 6 4 9 8     検索する
      L   R

2 5 3 4 6 7 9 8     交換する
      L   R

2 5 3 4 6 7 9 8     検索する。R と L が交差したら分割終了。
        R L

[2 5 3 4 6] [7 9 8] この 2 つのグループについて再び
                    同様な分割を行う

        図 : クイックソート

基準になる値のことを「枢軸 (pivot)」といいます。枢軸は要素の中から適当な値を選びます。今回は区間の真ん中にある要素を選ぶことにしましょう。上図を見てください。左側から枢軸 7 以上の要素を探し、左側から 7 以下の要素を探します。探索のときは枢軸が番兵 ^[*2] の役割を果たすので、ソート範囲外の要素を探索することはありません。見つけたらお互いの要素を交換します。探索位置が交差したら分割は終了です。

あとは同じ手順を分割した 2 つのグループに適用します。これは再帰定義を使えば簡単に実現できます。分割したグループの要素数が 1 になったときが再帰の停止条件になります。

-- note --------
[*2] 条件を満たす要素をあらかじめ配列に入れておく方法を「番兵 (sentinel)」といいます。また、要素そのものを番兵とか番人と呼びます。

●クイックソートのプログラム

それでは、クイックソートのプログラムを示します。

リスト : クイックソート (sample46.go)

package main
import "fmt"

func quicksort(low, high int, buff []int) {
    pivot := buff[low + (high - low) / 2]
    i, j := low, high
    for {
        for pivot > buff[i] { i++ }
        for pivot < buff[j] { j-- }
        if i >= j { break }
        buff[i], buff[j] = buff[j], buff[i]
        i++
        j--
    }
    if low < i - 1 { quicksort(low, i - 1, buff) }
    if high > j + 1 { quicksort(j + 1, high, buff) }
}

func main() {
  a := []int{5,6,4,7,3,8,2,9,1,0}
  quicksort(0, 9, a)
  fmt.Println(a)
}

$ go run sample46.go
[0 1 2 3 4 5 6 7 8 9]

関数 quicksort の引数 buff がソートする配列 (スライス)、low が区間の下限値、high が区間の上限値です。quicksort は buff の low から high までの区間をソートします。

最初に、区間の真ん中にあるデータを枢軸として選び、変数 pivot にセットします。次の for ループで、左側から枢軸以上の要素を探しています。ここでは枢軸以上という条件を、枢軸より小さい間は探索位置を進める、というように置き換えています。

同様に次の for ループで右側から枢軸以下の要素を探します。お互いの探索位置 i, j が交差したら分割は終了です。break 文で for ループから脱出します。そうでなければお互いの要素を交換します。交換したあと i と j の値を更新しておくことを忘れないでください。

そして、分割した区間に対して quicksort を再帰呼び出しします。このとき要素数をチェックして、2 個以上ある場合に再帰呼び出しを行います。この停止条件を忘れると正常に動作しません。ご注意ください。

●クイックソートの欠点

クイックソートは、枢軸の選び方で効率が大きく左右されます。区間の中央値を枢軸に選ぶと、区間をほぼ半分に分割することができます。この場合がいちばん効率が良く、データ数をN とすると N * log₂ N に比例する時間でソートすることができます。

逆に、区間での最大値または最小値を枢軸に選ぶと、区間はその要素と残りの要素の 2 つに分割にされることになります。これが最悪の場合で、分割のたびに最大値もしくは最小値を選ぶと、実行時間は要素数の 2 乗に比例することになります。これは遅いソートアルゴリズムであるバブルソートや単純挿入ソートと同じです。

この問題は枢軸の選び方を工夫することで、完全ではありませんが回避することができます。区間の中からいくつかの要素を選び、その中で中央の値を持つ要素を枢軸とします。たくさんの要素を選ぶとそれだけ最悪の枢軸を選ぶ危険性は少なくなりますが、値を選ぶのに時間がかかってしまいます。実際には数個の要素を選び、その中央値を枢軸とする場合が多いようです。特に、9 個の要素から枢軸を選ぶ median-of-9 という方法は優秀です。興味のある方は拙作のページ Algorithms with Python 「整列 (1)」をお読みください。

●バックトラック法と再帰定義

ある問題を解こうとするとき、可能性のあるパターンをすべて求めて、解の条件を満たしているか調べるしか方法がない場合があります。すべてのパターンを求めるとき、よく用いられる手法に「バックトラック法 (backtracking)」があります。

たとえば、簡単な例として迷路を考えてみましょう。ある地点 A で道が左右に分かれているとします。ここで、左の道を選んで先へ進むと、行き止まりになってしまいました。この場合は A 地点まで戻って右の道へ進まないといけません。

このように、失敗したら元に戻って別の選択枝を選ぶ、という試行錯誤を繰り返して解を見つける方法がバックトラック法なのです。バックトラック法は、いろいろな分野の問題に応用できる方法です。そして、再帰定義を使うと簡単にプログラムを作ることができます。

●順列の生成

簡単な例題として「順列 (permutation)」を生成するプログラムを作ってみましょう。異なる n 個の順列の総数は、n の階乗 (n!) 通りあります。たとえば 4 つの整数 1, 2, 3, 4 の順列は 24 通りあります。これをすべて求めるプログラムを作ります。最初に、繰り返しでプログラムしてみましょう。次のリストを見てください。

リスト : 順列の生成（繰り返し版）

package main
import "fmt"

func main() {
    var perm [4]int
    var used [5]bool
    // 一つ目の数字を選ぶ
    for n1 := 1; n1 <= 4; n1++ {
        if used[n1] { continue }
        perm[0] = n1
        used[n1] = true
        // 二つ目の数字を選ぶ
        for n2 := 1; n2 <= 4; n2++ {
            if used[n2] { continue }
            perm[1] = n2
            used[n2] = true
            // 三つ目の数字を選ぶ
            for n3 := 1; n3 <= 4; n3++ {
                if used[n3] { continue }
                perm[2] = n3
                used[n3] = true
                // 四つ目の数字を選ぶ
                for n4 := 1; n4 <= 4; n4++ {
                    if used[n4] { continue }
                    perm[3] = n4;
                    used[n4] = true
                    // 順列を出力
                    fmt.Println(perm)
                    used[n4] = false
                }
                used[n3] = false
            }
            used[n2] = false
        }
        used[n1] = false
    }
}

少々長いリストですが、やっていることは簡単です。選んだ数字は配列 perm に格納し、配列 used に印 (true) をつけておきます。あとは used に印がついていない数字を選んでいくだけです。数字を 4 つ選んだら順列 perm を出力します。

そして、次の順列を発生させるため、選んだ数字に対応する used に false をセットします。選ぶ数字がなくなったならば、もう一つ前のループに後戻りします。このように、後戻りしながら数字を選んでいくことで、24 通りの順列を生成することができます。

このプログラムは 4 重のループですが、けっこうたいへんですね。もし、1 から 10 の順列を発生させるとなると、10 重のループになってしまいます。ところが、再帰定義を使うともっと簡単にプログラムを作ることができます。次のリストを見てください。

リスト : 順列の生成 (再帰版, sample47.go)

package main
import "fmt"

func permutation(n int, perm []int, used []bool) {
    if n == len(perm) {
        fmt.Println(perm)
    } else {
        for i := 1; i <= len(perm); i++ {
            if used[i] { continue }
            perm[n] = i
            used[i] = true
            permutation(n + 1, perm, used)
            used[i] = false
        }
    }
}

func main() {
    permutation(0, make([]int, 4), make([]bool, 5))
}

関数 permutation は、1 から len(perm) までの順列を生成します。考え方は繰り返し版と同じで、数字を選んで perm にセットし、used に印 (true) をつけます。あとは印のついていない数字を選んでいけばいいのです。最初の呼び出しで 1 つの数字を選び、次の再帰呼び出しで 2 つめの数字を選びます。このように、n 重のループが n 回の再帰呼び出しに対応するわけです。

たとえば、len(perm) の値が n だとします。n 番目の数字を選び順列を出力したら、n 番目の再帰呼び出しが終了し、n - 1 番目の再帰呼び出しに戻ります。その後は選んだ数字の used の印を消して、新しい数字を選びます。もしも、選ぶ数字がなければ、n - 2 番目の再帰呼び出しに戻り、n - 2 番目の数字を選び直します。これで 1 から n までの順列をすべて生成することができます。