再帰: Nの階乗-アルゴリズム入門

スポンサーリンク

まずは再帰の定番中の定番であるNの階乗を求めるプログラムを作ります。

Nの階乗を2つのプロセス(線形再帰プロセス、線形反復プロセス)で記述してみます。 (SICPのSchemeコードをJavaScriptで書き直します)

線形再帰プロセス

N! = N * (N - 1)!

という風に考えます。 N=5のときは次のようになります。

5! = 5 * 4 * 3 * 2 * 1

5! = 5 * 4!

Nが1のときに1を返しそれ以外はn * factorial(n - 1)とします。

// JavaScript

function factorial(n){

    if (n === 1){
        return 1;
    }else{
        return n * factorial(n - 1);
    }
}

console.log(factorial(5));  // 結果 120

線形反復プロセス

線形反復プロセスは、for文やwhile文を使うような書き方で forやwhileを使わずに記述する書き方です。

カウンタとして機能する変数と、積を保存する変数を使います

// JavaScript

function factorial(n){

    return fact_iter(1, 1, n);

}


function fact_iter(product, counter, max_count){
    console.log(product + " " + counter + " " + max_count);

    if (counter > max_count){

        return product;

    }else{

        return fact_iter(product * counter, ++counter, max_count);

    }

}

console.log(factorial(5)); 


実行結果は次のようになります。

1   1  5
1   2  5
2   3  5
6   4  5
24  5  5
120 6  5
120