…を知らない人がいるかもしれないので、念のために；の計算を再帰で書くと、「にぱも」（疑 似日本語プログラミング環境）では以下のようになります。（自然数の）階乗とは、 1からその数までを順番にかけたもの で、普通「！」 で表します。例えば５の階乗 (5!) は、
5! = 1 x 2 x 3 x 4 x 5 = 120となります。これをプログラムで計算させる場合、繰り返し構文でもいいので すが、上で説明している再帰的な定義を使うと、1! = 1 ←定義 2! = 2 x 1! = 2 x 1 = 2 3! = 3 x 2! = 3 x 2 = 6 4! = 4 x 3! = 4 x 6 = 24 5! = 5 x 4! = 5 x 24 = 120 ...のようになり、結局、下のようにかける、ということです。
＃ 再帰関数定義の例 ＃ 関数カイジョウを引数はアで定義する もしアが１以下ならば １を返す でなければ アアをアとする アアから１を引く アに関数カイジョウを引数はアアで呼び出したものを掛ける アを返す ヒキに数値入力する 関数カイジョウを引数はヒキで呼び出したものを出力するこのように関数カイジョウの定義の中にカイジョウ自体が出てくるもの が 再帰関数 です。ちなみに階乗の計算は以下に埋めこんである JavaScript でも確認できます。 しかし、再帰関数は処理効率という意味ではなかなか厳しいものがあります。 これは、関数の中で関数を繰り返し呼び出すときの計算コストが実 は効いているというわけで、特に大きな数に対して処理すると、関数呼び出し が指数関数的に増大して非常に重い処理になります。
返り値用の領域をスタックに用意して、レジスタをスタックに退避して、ロー カル変数もスタックに積んで…みたいなことなのですが、詳細はここでは略し ます。そのような時に、ここで説明する動的計画法 (Dynamic Programing, DP)の考えかたを取り入れると、効率よく解ける場合があります。
DP 自体は本来オペレーションズ・リサーチ (Operations Research, OR) の分 野などでよく扱われた、再帰とは直接関係ないものです。最適化問題を複数の 部分問題に分割して解く際に、そこまでに求められている以上の最適解が求め られないような部分問題を切り捨てながら解いていく手法です。動的計画法を単純に説明すると、処理内容が小さな計算の繰り返しで あるとき、既に計算した値はどこか（多くの場合は配列）に保存し ておいて、いつでも再利用できるようにして重複計算を避けようとい う考え方です。もちろんこの手法は万能ではなく、以下の性質をもつ問題に適 応するのがいいとされています。
整数nにたいして（とりあえず0≤n<100としておきます）これ の「フィボナッチ数」 を求めなさい、という問題を考えます。フィボナッチ数とは、最初の２つの数は１、３つ目以降は、直前の２つの数の和、 というものです。具体的には以下のようなものです。
1, 1, 2, 3, 5, 8, 13, 21, ...
本質ではないですが、「にぱも」プログラムでは、直前に示された変数（こ の場合は、ループ変数）に名前をつけずに「それ」で使えていることに注意 してください（？！）同様に、再帰法から動的計画法へ機械的に 書き換えることができることがあります。例えば、フィボナッチ数のプログラ ムで、終了条件
もしアが二以下ならば 一を返すは、初期化の部分
フィの０番目を１とする フィの１番目を１とするに対応していますし、また、再帰呼び出し
エを関数フィボを引数はイで呼び出したものとする エに関数フィボを引数はウで呼び出したものを足すは、（既に計算された）小さなデータを織り込む部分
エをフィのイ番目とする エにフィのウ番目を足すに対応しているのがわかるでしょう。ですので、動的計画法でプログラムを書 くのは慣れてなくて難しいかもしれませんが、そんなときは、まずは再帰で記 述して、それが動的計画法で書き直せるかを考えてもいいかもしれません。
ただ、メモリ効率という意味では再帰のほうがいい場合もある（そうじゃない 場合もある）ということも、頭の片隅においておくといいかもしれません。言 い換えると、 CPU 効率とメモリ効率の トレードオフ（両天秤にかける） 、という感じでしょうか？問題によっては劇的に処理速度が速くなりますので、覚えておくと（プログラ マとして）幸せになれるときがきっとくるでしょう。