再帰といえばハノイの塔ですが、もっともシンプルな「階乗」を扱います。
■前提
- 『階乗』とは、『5!』のように記載し『5×4×3×2×1』を意味する
- 『再帰』とは『ある関数内で再びその関数自身を呼び出す事』
■サンプル
下記に半角で数値を入力し計算をクリックすると、その値の階乗を計算してくれます。(但し大きな数値を入力するとInfinityになってしまいます)
■サンプルソース(JavaScript)
function calc(){ var num = parseInt(document.forms[0].elements["num"].value); var answer = perform(num); alert(answer); } function perform(NUM){ if(NUM == 1){ return NUM; } else{ return (NUM * perform(NUM-1));, } }
■サンプルソース(HTML)
<form> <input type="text" size="10" name="num" /> <input type="button" value="計算" onclick="calc();" /> </form>
■解説
まず5の階乗について考えると、5の階乗は4の階乗に5を掛けたもの・・・という事は4の階乗は、3の階乗に4を掛けたもの
求める階乗の値をnとし、nの階乗を求める関数をfuncとすると、求める値はfunc(n)である。上記の考え方を数式に反映させると、以下のようになる。
func(n) = n × func(n-1)
ここで永遠に再帰するといつかn=0の状態になるが、階乗というものは1までを掛ければよいので条件分岐し
if(n==1){return n;}
とし、それ以外の時のみ
else{return (n * perform(n-1));}
と再帰を実行するようにする。(サンプルソースではnをNUMと記載してます)
メリット
コードがシンプルに記述できる事
デメリット
メモリーを大量に消費する事
■おまけ
この問題を例えば再帰を使わずに解くと…
- まずn個要素がある配列をつくる
- その配列は差が1である
- それをfor文で繰り返す
- for文の中で掛け算をする
短く書くと以下のようになる。
(function(n){if(n > 0){return n * arguments.callee(n - 1)}else{return 1}})(5);