再帰とは、ある「もの」の記述内容に、その「もの」が含まれていることをいう。 特に「もの」が関数であるとき、再帰関数と呼ばれる。また、 その「もの」が行なう処理を再帰処理という。 特にコンピュータの世界では、再帰関数や再帰処理は避けて通れない。 しかし、私は再帰関数や再帰処理が苦手である。 苦手なものは、自分で積極的に使ってみるしかない。 このページは、再帰関数のカタログとすべく、いろいろな再帰関数を示す。 なお、この例は特記なき限り、paiza.io ( https://paiza.io/ )で確認した結果を載せている。
再帰関数のメリットとは、複雑な構造を分解することで処理の内容が明確になることである。 いっぽうデメリットは、再帰構造の認識に長けたプログラマが少ないため、 了解性（保守性、理解性）に欠けることが挙げられる。
コンピュータ言語としては、再帰関数を呼び出す場合は再帰関数と同じ名前を使うが、 中には、再帰関数専用のなまえを使うこともある。 たとえば、Forth の場合は再帰関数の名前ではなく、RECURSE というワード（関数とほぼ同義）を使う。 また、Fortran では、対象関数を再帰関数として使う場合には予約語 recursive をつける必要がある。 OCamlは再帰をする関数を定義するときには予約語 rec をつける必要がある。
まずは数を一つ定め、この定めた数から決まった数が一つ得られる計算を対象としてみよう。
再帰関数の例として、頻繁に挙げられるのは階乗であろう。6! = 1 * 2 * 3 * 4 * 5 * 6 = 720 である。 以下の例では、n が 0 または正の整数であることを前提としている。 また、 n が 0 のとき 1 を返すことを終了条件としている。 n が 1 以下の時としても 1 を返すこととしてもよい。n と 0 を比較することは、 1 回多く再帰計算をしていることになる。
コードは JavaScript である。
function factorial(n) {
if (n === 0) {
return 1
}
return n * factorial(n - 1)
}
console.log(`factorial(6) = ${factorial(6)}`) // factorial(6) = 720
C 言語の例である。
#include <stdio.h>
extern int factorial(int);
int main(void){
printf("factorial(6) = %d\n", factorial(6));
return 0;
}
int factorial(int n) {
if (n == 0) {
return 1;
}
return n * factorial(n - 1);
}
Java の例である。
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
System.out.println("factorial(6) = " + factorial(6));
}
public static int factorial(int n) {
if (n == 0) {
return 1;
}
return n * factorial(n - 1);
}
}
Visual Basic の例である。VBA ではない。
public class compiler
shared function Main as integer
Console.WriteLine ("Facotiral(6) = "+ Factorial(6).ToString)
return 0
End function
shared function Factorial(n As Integer) As Integer
If n == 0 Then
Return 1
End If
Return Factorial(n - 1) * n
End Function
end class
Python 3 の例である。factorial の定義は、factorial(6) を呼び出す前でなければならない。
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
print("factorial(6) = ", factorial(6))
階乗は初項 1 、末項 n の等差数列の積であった。 初項 1 、末項 n の等差数列の和を考えることができる。 これを三角数という。triangle(6) = 1 + 2 + 3 + 4 + 5 + 6 = 21 である。 同じくコードは JavaScript である。
function triangle(n) {
if (n === 0) {
return 1
}
return n * triangle(n - 1)
}
console.log(`triangle(6) = ${triangle(6)}`) // triangle(6) = 21
もちろん、triangle(n) = n(n + 1) / 2 で計算されるのだが、足し算だけで行なうとするとこうなる、 という例である。再帰の例で階乗ばかり出て、三角数が出てこないのは、 三角数は上記のように乗算でたちまち計算できてしまうので、面白味がないからだろう。
フィボナッチ数 F(n) は次で定義される：
F(0) = 0
F(1) = 1
F(k + 2) = F(k) + F(k + 1)
F(2) = 1, F(3) = 2, F(4) = 3, F(5) = 5, F(6) = 8 である。 なお、初項 F(0) と F(1) の取り方は様々な変種がある。
JavaScript による実装を示す。
function fibonacci1(n) {
if (n <= 1) {
return n
}
return fibonacci1(n - 1) + fibonacci1(n - 2)
}
console.log(`fibonacci1(6) = ${fibonacci1(6)}`) // fibonacci1(6) = 8
上記の計算では、ある n に対して既に計算した F(n) を何度も呼び出すというムダがある。 そこで、F(n) の領域を配列などで事前に確保するとともに、 F(n) を計算したらメモして、そのあとはメモを使うという方法をとればよい。 具体的な方法は追って書く。
以上は、再帰関数の例としてよく挙げられるものだろう。実際にはほかにも、 漸化式で与えられる数列は再帰関数として実装できる。ここでは、 再帰関数の例としてはあまり例をみないが、カタラン数を考えてみよう。
カタラン数とは、ある種の組合せの数であり、ベルギーの数学者であるカタランにちなんで名づけられた。
カタラン数 C(n) は次の式で定義される。
`C(0) = 1`
`C(1) = 1`
`C(k + 1) = (2(2k + 1)) / (k + 2) C(k)`
カタラン数の例として多く紹介されるのは、カッコの開きと閉じを正しく対応させる組合せの数、 という表現だろう。
function catalan(n) {
if (n <= 1) {
return 1
}
return 2 * (2 * n + 1) * catalan(n - 1) / (n + 2)
}
console.log("catalan(6) = " + catalan(6)) // catalan(6) = 132
上記の計算式において、return に記述された式の分子の部分が途中で桁あふれするかもしれない。 そのような場合は、分子を乗じる前に分母の (n + 2) であらかじめ割れるだけ割っておくといいだろう。 なお、`C(k)` は整数であることが保証されている。
割り算を使わない再帰的定義もある。
`C(k + 1) = sum_(i=0)^kC(i)C(k-i)`
メモ化の例題として好適だろう。
次のような数も再帰的な定義により計算できる。なお、三角数のように四則演算による直接的表現ができるものもあれば、 階乗のようにできないものもある。
また、ベルヌーイ数は、項番を指定すると偶数または1の場合は有理数を、そうでない場合は 0 となる数である。 これも再帰的に定義できる。実装のコードは宿題となる。
階乗や等差数列の和は、１つの数から得られる１つの数を求める方法だった。 次は２つの数から１つの数を得る計算を見ていく。
まず順列を考えよう。
順列とは、全体集合から一部の要素を取り出して、順番を気にして並べたときの異なる並べ方の数である。 例として、A, B, C, D, E の全体５つから２つを取り出して順序を気にして並べると、 AB, AC, AD, AE, BA, BC, BD, BE, CA, CB, CD, CE, DA, DB, DC, DE, EA, EB, EC, ED の全部で 20 通りある。全体の数を n, 取り出す数を k とすると、 順列の総数 P(n,k) は、P(n,k) = n! / (n - k)! となる。
階乗の計算は再帰的に実現できたので、この式に従って行なってもよいが、 別の再帰関数を使う方法もある。k = 0 のとき P(n,k) = 1 とすれば、 この定義からわかるように、k > 0 のとき、P(n,k) = n * P(n-1,k-1) である。 これをそのまま再帰関数としてプログラミングしてみた。
function permutation(n, k) {
if (k === 0) {
return 1
}
return n * permutation(n - 1, k - 1)
}
console.log("permutation(5, 2) = " + permutation(5, 2)) // permutation(5, 2) = 20
組合せとは、全体集合から一部の要素を取り出して、順序を気にせずに取り出した種類に着目したときの取り出す数である。 例として、A, B, C, D, E の全体５つから２つを取り出して順序を気にせずに数え上げると、 AB, AC, AD, AE, BC, BD, BE, CD, CE, DE の全部で 10 通りある。全体の数を n, 取り出す数を k とすると、 組合せの総数 C(n,k) は直接の式は次の通りである。たとえば、C(5,2)=10 である。
`C(n,k) = (n!) / (k! (n - k)!)`
C(n,k) が満たす関係式は多く知られているが、ここでは、次の関係式を使おう。
`n C(n-1,k-1) = k C(n,k) `
C(n, 0) = 1 と合わせて、そのまま再帰関数としてプログラミングしてみた。
function combination(n, k) {
if (k == 0) {
return 1
}
return n * combination(n - 1, k - 1) / k
}
console.log("combination(5, 2) = " + combination(5, 2)) // combination(5, 2) = 10
最大公約数 (エス : plej granda komuna divizoro, PGKD, 英 : Greatest Common Divisor, gcd) を求めるアルゴリズムは、 ユークリッドの互除法と呼ばれている。 JavaScript による実装は次の通り。
function gcd(x, y) {
if (y === 0) return Math.abs(x)
return gcd(y, x % y)
}
console.log(`gcd(3555, 675) = ${gcd(3555, 675)}`) // gcd(3555, 675) = 45
次の数も再帰的な計算により計算できる。
ベルヌーイ数を有理数として表したとき、分子と分母を互いに素である整数として求めるのであれば、 この範疇にあたるが、残念ながら私の能力ではプログラムのコードを示せない。
自然数を `n, m` とするとき、`nsqrt(m)` の根号の中をできるだけ小さな数で表して、 `n sqrt(m) = p sqrt(q)` としたい。このときの `[n, m]` から `[p , q]` を求めるアルゴリズムは、 再帰を使って実装できる。n が根号の外に出ている部分、x が根号の中の部分である。 素数は 19 までしか用意していない。529 (= 23*23 ) 以上の数に対応するには、 エラトステネスの篩の要領で素数を付け加えればいい。 解析幾何早わかりで使った。
function sqrt(n, x) {
const p = [2,3,5,7,11,13,17,19]; // 素数
for (let i = 0; i < p.length; i += 1) {
let sq = p[i] * p[i];
if (sq > x) {
return [n, x]
}
if (x % sq === 0) {
return [n * p[i] * sqrt(1, x/sq)[0], sqrt(1, x/sq)[1]]
}
}
return [n, x]
}
console.log(`sqrt(1, 48) = ${sqrt(1, 48)}`) // => [4, 3]
配列は再帰的データ構造ではないが、再帰的データ構造と同じように扱うことができる。 たとえば、a[0], a[1], a[2], ..., a[n-1] という配列があったときに、 f(a[0], a[1], a[2], ..., a[n-1]) = g(a[0], f(a[1], ..., a[n-1])) という関係があれば、再帰的に処理を進めることができる。
数のときと同様に、１出力、２出力と分けてもよかったが、ここでは分けないことにする。
配列の和を再帰的に求めることができる。a[0] + a[1] + ... + a[n-1] を S(a[0..n-1]) とかけば、S(a[0..n-1]) = a[0] + S(a[1..n-1]) となり、 再帰処理を使える。あるいは、S(a[0..n-1]) = S(a[0..n-2]) + S[a-1] を使ってもよい。 ここでは JavaScript により、記述した。
const arr = [3209, 59094, 969094, 819609, 3238994, 819487];
function sumarr(arr, n) {
if (n == 0) {
return 0
}
return sumarr(arr, n - 1) + arr[n - 1]
}
console.log("sumarr(arr, 6) = " + sumarr(arr, 6)) // sum(arr, 6) = 5909487
なお、この再帰と、次の Array.prototype.reduce() メソッドおよびアロー関数を比べてみるとおもしろいだろう。
const arr = [3209, 59094, 969094, 819609, 3238994, 819487];
const reducer = (accumulator, currentValue) => accumulator + currentValue;
console.log("arr.reduce(reducer) = " + arr.reduce(reducer));
配列の積も、同様に再帰的に求めることができる。
配列の最大値や最小値も、再帰的な解法がある。
リストは Lisp などの関数型言語ではもちろん、他の言語でも基本となるデータ構造である。 リストの構造は再帰に向いている。というのも、リストは、最初の要素＋残りのリスト、という構造になっていて、 リストが再帰的に定義されているからだ。ではまず、最初の例を見る。
最初はリストの長さを返す関数 my-length を作る。my- の接頭辞をつけたのは、 もともとシステム組み込みの関数 length とバッティングしないようにするためである。 リストの定義のとおり、最初の要素の car と残りの要素 cdr にわけて、car をみつけたら１ずつ増やす、 ということをリストが空になるまで繰り返せばよい。この場合、car で得られた要素は、 アトムであろうがリストであろうが１と数える。
* (defun my-length (list)
(if (null list)
0
(+ 1 (my-length (cdr list))) ))
MY-LENGTH
* (my-length '(1 2 3 4 5))
5
* (my-length '(1 2 (3 4 5) 4 5))
5
my-length は、リストの要素の内容を参照することはなかった。つぎはリストの内容を参照する再帰を調べよう。
my-copy は、リストの要素をコピーする関数である。
* (defun my-copy (list)
(if (null list)
()
(cons (car list) (my-copy (cdr list))) ))
MY-COPY
* (my-copy '(1 2 3 5 4 4 6 5))
(1 2 3 5 4 4 6 5))
* (my-copy '(1 2 (3 5 4) (4 6 5)))
(1 2 (3 5 4) (4 6 5))
次は、リストの各要素を２倍する関数 map2* を作る。 リストの定義のとおり、最初の要素の car と残りの要素 cdr にわけて、car をみつけたら２倍して返し、 残りとつなぐということを行なう。
(defun map2* (list)
(if (null list)
()
(cons (* 2 (car list)) (map2* (cdr list)) ) ))
結果を確認する。
* (map2* '(1 2 3 4 5)) (2 4 6 8 10)
このパターンは、mapcar を適用したものと同じである。
* (mapcar #'(lambda (x) (* x 2)) '(1 2 3 4 5)) (2 4 6 8 10)
通常のプログラミングは mapcar で行なうのがいいだろう。そして、関数の再帰を作る必要があれば、 このパターンを思い出してみるといいだろう。
２つのリストを連結する append2 を作る。Steel Bank Common Lisp による結果である。
(defun append2 (list1 list2)
(if (null list1)
list2
(cons (car list1) (append2 (cdr list1) list2)) ))
これでリストが連結できるか試す。
* (append2 '(6 5 6) '(5 4 3 2 1 2)) (6 5 6 5 4 3 2 1 2)
今までのリスト処理は、リストの要素がすべてアトムであることを前提にしていた。 こんどは、リストの要素がさらにリストである場合も含めることにする。 リストが入れ子である場合に、すべてのリスト構造を保存し、アトムに至るまでくまなくたどることを 「深い」と表現する。この深い再帰パターンを考える。 深いコピー関数はこうなる。
(defun deep-copy (list)
(if (null list)
()
(if (atom (car list))
(cons (car list) (deep-copy (cdr list)))
(cons (deep-copy (car list)) (deep-copy (cdr list))) )))
結果はどうだろうか。
* (deep-copy '(1 2 (3 5 4) (4 6 5))) (1 2 (3 5 4) (4 6 5))
うまくいったようだ。
ではこれをもとにして、２倍する関数の深いバージョンを作る。
(defun deep-map2* (list)
(if (null list)
()
(if (atom (car list))
(cons (* 2 (car list)) (deep-map2* (cdr list)))
(cons (deep-map2* (car list)) (deep-map2* (cdr list))) )))
適用結果を見よう
* (deep-map2* '(1 2 (3 5 4) (4 6 5)) ) (2 4 (6 10 8) (8 12 10))
クイックソートは実用的に用いられているソーティング手法である。次がクイックソートの例である。
(defun qsort (list)
(if (null list)
list
(qsort-sub (car list) (cdr list) nil nil) ))
(defun qsort-sub (pivot list left right)
(if (null list)
(append (qsort left) (cons pivot (qsort right)))
(if (< (car list) pivot)
(qsort-sub pivot (cdr list) (cons (car list) left) right)
(qsort-sub pivot (cdr list) left (cons (car list) right)) )))
再帰関数では、引数を食いつくすイメージが私にはある。 しかし、食うだけではなくて、貯めることもある。アリとキリギリスのようだ。 この貯める変数をアキュムレータという。蓄積変数ともいう。 この蓄積変数は次のように使う。LISP で、与えられたリストを逆順にしたリストを返す関数である。 reverse は Common Lisp にあるので、my-reverse というなまえで作る。 この例では、rlist が蓄積変数となっている。rlist が結果として得られる逆順のリストになっている。
(defun my-reverse (list rlist)
(if (null list)
rlist
(my-reverse (cdr list) (cons (car list) rlist)) ))
試してみよう。nil を忘れずに
* (my-reverse '( 1 2 3 5 4 4 6 5) nil) (5 6 4 4 5 3 2 1)
アキュムレータとなる変数には accumulator または acc を使うこともある。
再帰関数のデバッグには、いろいろな方法がある。Common Lisp では、トレースが使える。 以下は、素朴なフィボナッチ関数を fib という名前で実装した例に対してトレースを実行した結果だ。 なお、この例では paiza.io は使えなかったので、デスクトップの Steel Bank Common Lisp を使った。 trace の結果のコロンの左側の数字は、関数の適用の段数を表している。
* (defun fib (n)
(if (<= n 1)
n
(+ (fib (- n 1)) (fib (- n 2))) ))
FIB
* (trace fib)
(FIB)
* (fib 4)
0: (FIB 4)
1: (FIB 3)
2: (FIB 2)
3: (FIB 1)
3: FIB returned 1
3: (FIB 0)
3: FIB returned 0
2: FIB returned 1
2: (FIB 1)
2: FIB returned 1
1: FIB returned 2
1: (FIB 2)
2: (FIB 1)
2: FIB returned 1
2: (FIB 0)
2: FIB returned 0
1: FIB returned 1
0: FIB returned 3
3
*
下請関数というのは目にすることはないと思う。ここでいう下請関数というのは、 仕様として表現された表の再帰関数から呼び出される関数であり、 それ自身が呼び出されるのは表の再帰関数からに限る、という関数である。
相互再帰とは、再帰の一種である。 通常の再帰は、直接それ自身のみに対する再帰となっているが、 相互再帰とは、それ自身だけでなく他の関数などとの組合せによって再帰を構成するものである。
相互再帰の例としてよく使われるのが、与えられた自然数が奇数か否か、 あるいは偶数か否かを判定する関数である。次は JavaScript で記述した相互再帰の例である。
function is_even(n) {
if (n == 0) {
return true
}
return is_odd(n - 1)
}
function is_odd(n) {
if (n == 0) {
return false
}
return is_even(n - 1)
}
console.log("is_even(4) = " + is_even(4)) // -> true
console.log("is_even(5) = " + is_even(5)) // -> false
console.log("is_odd(5) = " + is_odd(5)) // -> true
console.log("is_odd(4) = " + is_odd(4)) // -> false
他にも相互再帰の例はある。高校数学で漸化式を履修した方であれば、 確率漸化式を思い出すだろう。たとえばこんな問題である。 島 A と島 B に時刻 k （k >= 0) にコメがそれぞれ A(k) kg と B(k) kg あるとする。時刻 k + 1 のとき、島 A では自分の島に p % 残し、 残りの (100 - p) % を島 B に渡す。 同じように、島 B では自分の島に q % 残し、残りの (100 - q) % を島 A に渡す。 なお、百分率は重量比である。 A(0) = a (kg), B(0) = b (kg) としたとき、時刻 n での島 A 、 島 B にあるコメはそれぞれ何 kg か。
const p = 0.60;
const q = 0.45;
function kome_a(n) {
if (n == 0) {
return 30;
}
return p * kome_a(n-1) + (1.0 - q) * kome_b(n-1)
}
function kome_b(n) {
if (n == 0) {
return 70
}
return (1.0 - p) * kome_a(n-1) + q * kome_b(n-1)
}
console.log("kome_a(10) = " + kome_a(10)) // 57.894736842102546
console.log("kome_b(10) = " + kome_b(10)) // 42.10526315789747
n = 10 程度であれば問題ないが、これより増やすとスタックあふれになることは間違いない。
相互再帰の別の例として、 ATSプログラミング入門 (jats-ug.metasepi.org) にある例題を考えよう。次のように帰納的に定義された関数を考える:
なお、上記ページではシグマを用いずに書かれているが、私の判断でシグマを用いて書き直した。このとき、 定義も少し変更した。変更点は、上記のページではシグマの開始が i = 1 であったのを、 私の判断で i = 0 に変更したことである。これは、n = 0 のときにシグマの範囲が空集合になってしまうのが気になったからだ。 実際には、i = 0 のとき積は必ず 0 だから和には影響を与えない。
さて、このとき、`n` を与えて直接 `P(n)`を求める再帰関数を書くこともできるが、 上記ページでは新たな関数 `Q(n)` を別に定義して `P(n)` と `Q(n)` の相互再帰として求めることもできる。 このとき、`P(n)` と `Q(n)` は次のように定義される：
実際にはどうなっているのだろうか。まず、`P(n)` のみから構成される計算を追う。
n P(n)
0 1
1 1 = 1 + 0 * 1
2 2 = 1 + 0 * 1 + 1 * 1
3 6 = 1 + 0 * 1 + 1 * 1 + 2 * 2
4 24 = 1 + 0 * 1 + 1 * 1 + 2 * 2 + 3 * 6
どこかで見たような列だが、それは置いておく。では、P(n) と Q(n) を相互に使うとどうなるだろうか。
n P(n) Q(n)
0 1 0
1 1 = 1 + Q(0) 1 = Q(0) + 1 * P(1)
2 2 = 1 + Q(1) 5 = Q(1) + 2 * P(2)
3 6 = 1 + Q(2) 23 = Q(2) + 3 * P(3)
4 24 = 1 + Q(3) (省略)
なるほど、確かに同じだ。なお、P(n) は、n の階乗の別定義になっている。
本格的な相互再帰は再帰下降構文解析で現れるが、まだ理解していない。 別の例を出す。三角関数の `sin theta` と `cos theta` が与えられたとき、 n を自然数として `sin ntheta` と `cos ntheta` を求める問題がおもしろい。解法は後で示す。
今までの再帰関数の実装では、関数に名前がつけられていることが前提だった。 では、無名関数で再帰を実装することはできるのだろうか。答は可能である。 一つの方法は言語の仕様に依存する方法で、その言語の仕様にある、自己参照をするキーワードを使う方法である。 APL、Forth、R などがある。もう一つの方法は、言語の仕様に事故参照をするキーワードがない場合でも使える方法で、 不動点コンビネータを使う方法である。どちらも、詳細は省略する。
最近の言語では再帰を扱うことができる。長寿言語の代表格である Fortran も再帰が扱える。 COBOL は標準では扱えないようだ。
将棋のルールを利用したパズルに詰将棋がある。 詰将棋は、玉方の玉を詰方が最短手順で詰ますのがルールとなっているが、 玉方は最長手数となるように抵抗する。この抵抗の方法はいろいろあるが、 詰方の線駒による王手に対して玉方が自身の駒を動かしたり売ったりして利きを遮る方法がある。 この遮る駒を合駒というが、この合駒を無駄に取られるだけの場合、つまり無駄合いの場合は、 合法的な合駒としては認めない。 では、何をもって無駄というのかが、詰将棋のルールとして議論が多くあるところである。 コンピュータで詰将棋を解くときには、ある基準で無駄合を定義する必要がある。 その便法として、柿木義一氏が提案した「無駄合の判定法」は一つの指針となる。 この無駄合を判定するアルゴリズムは、再帰的定義が使われている。
上記は詰将棋の玉側の抵抗が無駄になる場合の判定に再帰を使う例であった。 この裏返しで、詰将棋の正解となる詰手順に再帰を使う例がある。 この再帰を使うことによって、初期盤面から最終詰めまでの手数を長くすることができる。 なお、詰将棋は通常「詰方最短、玉方最長」のルールであるが、このルールを別のルールにすることもできる。 この別ルールによる詰将棋は「フェアリー」と呼ばれ、通常詰将棋でも、またフェアリー詰将棋でも、 再帰手順を活用した長手順詰将棋作品が存在する。
再帰を理解するための有名なことばがある。
再帰を理解するために最初に理解する必要があるのは、再帰だ。
英語では次の通りである。
To understand recursion, first you must understand recursion.
エスペラントだと、こうなるのだろうか。
Por kompreni rikuron, unuafoje oni devas komprenas rikuron.
言語によっては、主語と目的語が同じであるような動詞があり、これを再帰動詞という。 また、再帰動詞の目的語として使われる代名詞を再帰代名詞という。 なお、再帰代名詞を目的語とせずとも、再帰動詞は成り立つ。
再帰反射、あるいは再帰性反射とは、光源から入射した光が、 入射光と反射材の角度にかかわらず、反射材によって光源に向かって反射することをいう。 通常の反射は、法線に対して対称の方向に反射したり(鏡面反射）、拡散したり（乱反射）するが、 反射材に特別な性質を付与することで、再帰反射をさせることができる。JIS では、 再帰性反射体や再帰性反射材について規格を定めている。
私は日本史のことを全く知らないが、国際事情が「複雑怪奇」と言い残して総辞職した日本の内閣があったことは覚えている。 調べてみたらこの内閣は平沼騏一郎内閣であることはわかったが、 複雑怪奇であると表現したのは国際事情ではなく欧州情勢だった。 知ったかぶりをするとろくなことにはならない。この再帰のページも、「複雑怪奇」ならぬ「複雑再帰」なのだ。
Wikipedia の太田裕美の項を見ると、相互再帰と思われる挿話があった。
2010年5月16日、松本隆作詞家生活40年記念コンサートに出演した際、「今の太田裕美があるのは松本隆のおかげ、今の松本隆があるのは太田裕美のおかげ」と冗談めかして発言した。
正規表現では、バランスのとれた任意個のカッコを認識できない。正規表現は有限オートマトンと等価であり、 有限オートマトンは任意のカッコの数のバランスを認識する手段がないからだ。 しかし、正規表現の実装によっては、 正規表現の式の中で、自分自身の部分式を参照できる。これはつまり、自らを再帰的に呼び出せる、ということであり、 この再帰呼び出しによってバランスのとれた任意個のカッコを認識できる。たとえば、 Ruby の Regexp というクラスの構文には、再帰構文がある。 この再帰構文を使ってバランスのとれたカッコにマッチする式は次の通りとなる。
balanced =
/
\A # 文字列の先頭にマッチ
(?<brackets> # "brackets"という部分式の開始
\( # リテラル開きカッコにマッチ
\g<brackets> # ゼロ回以上の"brackets"部分式にマッチ
\) # リテラル閉じカッコにマッチ
) # 部分式の終了
* # パターン全体をゼロ回以上繰り返し
\z # 文字列の末尾にマッチ
/x
以上は、アンダースタンディング コンピューテーションの p.107 による。
次の文献があるが、私はどれも未見である。
