J言語には階乗については!(エクスクラメーションマーク)という専用の動詞が用意されていますが、階乗は普通nの階乗はn-1の階乗にnを掛けたもの、というような定義をします。なお0の階乗は1です。このような定義の仕方は定義される関数が定義の中に出てくるので再帰的(リカーシブ)と呼ばれます。
ケース文がリカーシブな定義に使われます。ケースはある条件下ではある関数を選び、終了条件になったときに別の関数が選ばれます。
factorial=: 1:`(]*factorial@<:) @. * factorial "0 i.6 1 1 2 6 24 120
注：1:(いちコロン)というのはコンスタント関数で1を返す。
まず1行目の1:`(]*factorial@<:)は動名詞(gerund)で、`(バッククオート)の前の動詞(この場合は1:)と後ろの動詞、この場合は(]*factorial@<:)つまり、nにn-1の階乗(factorial)を掛けるというものです。これが@.以降の動詞の結果が0ならば前者の1:、0でなければ後者の(]*factorial@<:)が適用する、ということで定義どおりの関数になっている。
ここで注意して欲しいのは関数名でJ言語では関数に名前をつけなくても、ふつうは同じ結果を得ることができますが、この再帰では名前を使っています。
(sum=: +/) i.5 10 +/ i.5 10
しかし、$:(ドルコロン)という言葉が用意されていて、名前のない関数でもこれを使うと再帰関数を定義することができます。以下は先ほどの階乗(factorial)を関数を定義せずに実行した例です。
1:`(]*$:@<:) @. * "0 i. 6 1 1 2 6 24 120
ハノイの塔というパズルがあります。大きさの違う円盤のセットがあって、AからCを使ってBに移すのに必ず大きな円盤は小さい円盤のしたにある、という条件のもとに動かします。
以下はこのプロセスを再帰的にプログラムしたものです。
h=: b`(p,.q,.r)@.c
c=: 1: < [
b=: 2&,@[ $ ]
p=: <:@[ h 1: A. ]
q=: 1: h ]
r=: <:@[ h 5: A. ]
3 h x=: 'ABC'
AABACCA
BCCBABB
0 1 2 3 4 <@h"0 1 x
++-+---+-------+---------------+
||A|AAC|AABACCA|AACABBAACCBCAAC|
||B|CBB|BCCBABB|CBBCACCBBAABCBB|
++-+---+-------+---------------+
解説：ハノイの塔は元の山が何枚の円盤から出来ているにせよ、AからBに移したいのならば、その枚数より一枚少ない山をAからCに移して、それから1枚(一番おおきいの)をAからBに移して、それから山をCからBに移すことになります。
従って、全体をn h 'abc'とすると、1.(n-1)枚の山について(n-1) h 'acb'する(aからbにうつす)、2.1枚をa->bする,3.(n-1)枚の山について(n-1) h 'cba'する(cからbにうつす)、というような再帰的な定義が可能です。さてnから1引いた数については
(0 1 2 3 4 5) A. 'abc' abc acb bac bca cab cba 1 A. 'abc' acb 5 A. 'abc' cba
b=: 2&,@[ $ ]は、右側引数の冒頭2桁をたてに並べるもので、これの羅列がハノイの塔を解いたことになります。
1 b 'abc' a b (2 , 1) $ 'abc' a b 2 1 $ 'abc' a b
演習：
22.1 以下のプログラムを演習せよ。
f=:1:`(+//.@(,:~)@($:@<:))@.* NB.二項係数
f i.6
1 0 0 0 0 0
1 1 0 0 0 0
1 2 1 0 0 0
1 3 3 1 0 0
1 4 6 4 1 0
1 5 10 10 5 1
<@f"0 i.6 NB.ボックス化した二項係数
+-+---+-----+-------+---------+-------------+
|1|1 1|1 2 1|1 3 3 1|1 4 6 4 1|1 5 10 10 5 1|
+-+---+-----+-------+---------+-------------+
g=:1:` ( (],+/@(_2&{.))@$:@<:)@.* NB.フィボナッチ
g 10
1 1 2 3 5 8 13 21 34 55 89
解説：定義を読んで、結果をみればわからないでもないですが、自分でこの定義を書ける気がしませんね。$:(ドルコロン)という自己参照の動詞が加わるとますますわかりにくくなるような気がする。でもとりあえずわかったので書きます。二項係数のは1 2 1とかの数列について,:~でそれを上下二列の配列にして、+//.でななめに足すと1 3 3 1という数列が作れます、という話。/.(スラッシュドット、オブリーク)はななめに動詞を作用させる副詞。フィボナッチのは1 1 2とかの数列について、後ろの2項を足した数を、もとの数列の後ろにくっつける、ということをやっています。
