階乗の実装
再帰の見本としてよく使われる階乗をJとF#で実装してみるテスト。
F#の場合
まずは普通に再帰的に実装してみる。
let rec fact = function 0 -> 1 | n -> n * fact (n-1)
次に末尾再帰の形で実装してみる。
let rec fact2 n res = if n = 0 then res else fact2 (n-1) (res * n)
最後に手続き的な実装もやってみる。
let fact3 n = let res = ref 1 for i in [1..n] do res := !res * i res
[以下追記(2009/01/09 23:08)]
いげ太さんのコメントにより追加。fold/reduce系の関数による実装。
let fact4 n = List.fold_left ( * ) 1 [1..n] let fact5 n = List.reduce_left ( * ) [1..n]
どんどんいろんな方法による実装が増えると面白いなあ。
[追記ここまで]
J言語の場合
まずはfact(n)の計算に1〜nまでの数列を用意して全部掛けるパターン。
fact =: */@:>:@i. fact 5 120
次に再帰的な実装。これは見た目どおり。
fact2 =: 3 : 'if. y=0 do. 1 else. y*fact2 <:y end.' fact2 5 120
再帰的な、暗黙の定義による実装。
fact3 =: 1:`(* $:@<:)@.* fact3 5 120
最後のが複雑だけど、自身を再帰的に呼び出す動詞 $: を使って再帰を表現している。
最初に * で符号を判定して @. の働きで引数が0なら 1: を、そうでないなら (* $:@<:) を適用する。
1:は定数関数で必ず1を返し、(* $:@<:)は y * fact3 <:y と同じこと。フックをよく見てみよう。