nの階乗(n!)は次のように定義される。
n! = n × (n-1) × (n-2) × ... × 2 × 1
これを一般化すると
n! = n × (n-1)! ただし、0! = 1
となる。このように階乗の定義の中に階乗の計算があるものを再帰的定義という。
プログラミング言語には再帰的定義をそのまま書ける再帰的手続きを使えるものがあり、手続きの中で自分自身を呼び出すことができる。Rubyでも可能で、次のようなプログラムが書ける。
01: def factorial(x) 02: if x<0 03: "エラー:負の数の階乗は計算できません。" 04: elsif x==0 05: 1 06: else 07: x * factorial(x-1) 08: end 09: end 10: 11: puts factorial(ARGV[0].to_i)
1-9行が階乗の計算をするfactorialメソッドで、引数が負の場合、エラーを表す文字列を返す。4行は数学的定義に従ってx=0のとき1を返す。そうでなければ、7行によって数学的定義通りに階乗を計算する。
11行目で、コマンドラインから最初の引数を受け取って整数化し、factorialメソッドを呼んでいる。例えば、
ruby fact.rb 10
とすると、ARGV[0]には'10'が入る。
多くのプログラミング言語では、このアルゴリズムで12!(CPUが32ビットの場合)または20!(64ビットの場合)より大きな数は計算できない。CPUが扱える整数の最大値を超えてしまうからである。Rubyは多倍長整数という仕組みをもっているので、メモリが許す限り大きな整数を扱える。ただし、再帰的メソッドの呼び出しには回数の制限があるため、実際にはこのプログラムでメモリ一杯までの数を計算することはできない。