再帰関数

参考書の整列のところで、「再帰処理」というものが出てきて、まず整列のところでこれが取り上げられているのが、どんなつがなりがあるのかもよくわからないのですが、一体どうゆうことなのか分かりません。
＜５！を求める例＞で、本来１２０なのに、【ｆ（５）】というのが出てきて１２０とは全然違う式が書いてあり、最終的な答えが１になっているみたいな感じです。

どなたか教えてください。

No.2 ベストアンサー 回答者： tatsumi01 回答日時： 2006/12/29 17:15

再帰関数というのは、関数の定義で自分自身を使っている関数です。

階乗ですと
ＦＡＣＴ（Ｎ）＝Ｎ×ＦＡＣＴ（Ｎ－１）
のように定義します。そうすると、
ＦＡＣＴ（５）＝５×ＦＡＣＴ（４）
で、一つ小さい値での階乗がわかれば計算できます。以下同様に
ＦＡＣＴ（４）＝４×ＦＡＣＴ（３）
ＦＡＣＴ（３）＝３×ＦＡＣＴ（２）
ＦＡＣＴ（２）＝２×ＦＡＣＴ（１）
これを無限に続けては困るので、どこかで止めないといけません。そこで
ＦＡＣＴ（１）＝１
と定義し、無限に計算が続かないようにします。
上の式で（下から）計算していってみて下さい。ＦＡＣＴ（５）＝１２０になることがわかります。

No.4 回答者： guccii 回答日時： 2006/12/31 15:05

まず整列のところで再帰処理が取り上げられるのは、マージソートが再帰処理で実装しやすいからです。

また、整列アルゴリズムのなかでマージソートは最重要です。シンプルかつ実質的には最速ですから。

再帰処理は他には構文解析や木構造の処理によく使われます。
慣れるとすごく便利な処理方式ですが、注意しないとスタックを浪費することもありますので、再帰処理を繰返処理に置き換えるやり方も学んでおいた方がいいでしょう。

No.3 回答者： chukenkenkou 回答日時： 2006/12/29 17:18

#1さんの回答と組み合わせて見てください。

f(x)といった関数が記載されていますよね？
f(0)=1といったことも書かれていませんか？

f(5)=5*f(5-1)
↓
f(4)=4*f(3-1)
↓
中略
↓
f(0)=1
※#1さんの例では、f(1)=1です。

No.1 回答者： E07Kaz 回答日時： 2006/12/29 17:10

再帰は理解すると非常に便利です。

5!を例にしますと、
5!=5*4!
=5*4*3!
=5*4*3*2!
=5*4*3*2*1
というふうになります。
これを言葉で書きますと、
if ( in == 1 )
out == 1
else
out == in * 再帰関数( in - 1 )
endif
return out
って感じですかね。
再帰関数では、終端条件を与えておかないと、
無限ループに陥りますので、ご注意ください。