@blog.justoneplanet.info

日々勉強

Javascriptで再帰

再帰といえばハノイの塔ですが、もっともシンプルな「階乗」を扱います。

■前提

  • 『階乗』とは、『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);

コメントはまだありません»

No comments yet.

RSS feed for comments on this post.TrackBack URL

Leave a comment