2014-02-18

Categories: プログラミング JavaScript

再帰は便利

再帰ってどのくらい使ってますか？

関数型言語では必ず使うのですが、なかなか普通は使わないんじゃないでしょうか。

再帰の例1: iota

例として、Lispでよく使う iota という関数を紹介します。

iota は、nまで連続した配列を出力する関数です。

function iota(n){
    function iota_impl(c,a,m){
        if(c > m){
            return a;
        }else{
            return iota_impl(c+1,a.concat([c]),m);
        }
    }
    return iota_impl(0,[],n);
}

console.log(iota(5)); // [0,1,2,3,4,5]

これくらいなら、ループの方が楽そうですね。

再帰の例2: fib

fib関数は、フィボナッチ数列のn番目の項を返す関数です。

function fib(n) {
  return n < 2 ? n : fib(n - 2) + fib(n - 1);
}

console.log(fib(3)) // 2

ここまで来ると再帰の方が分かりやすい気もしますね。

再帰には付き物の「スタックオーバーフロー」

先程の２つの例ですが、ちょっと値を大きくするとエラーが起こります。

iota(100000); // Uncaught RangeError: Maximum call stack size exceede
fib(100000); // Uncaught RangeError: Maximum call stack size exceede

これがいわゆるスタックオーバーフローですね。

スタックオーバーフローを無くすには、

• 値を小さくする
• スタックを大きく確保する
• ループに変換する

の３つの方法がありますが、今回は一番汎用性のある、ループに変換するという方法を紹介します。

iotaをループに変換

iotaはどんどんnを追加していくだけなので、変換すると単純なループになりますね。

function iota2(n){
    var a = [];
    for (var i=0; i <= n; i++) {
        a.push(i);
    }
    return a;
}

console.log(iota2(100000)); // [0,1,2, ... ,100000]

スタックをほとんど使わないので、スタックオーバーフローは起こりません。

fibをループに変換

fibは少しひねりが必要ですが、やり方は同じです。

function fib2(n){
    if(n < 2) return n;

    var a = 0;
    var b = 1;
    var r = 0;

    for (var i=2; i <= n; i++) {
        r = a + b;
        a = b;
        b = r;
    }

    return r;
}

console.log(fib2(100000)); // ?

処理が全く止まらないので結果はわかりませんでした。笑

C言語でやってみた結果を貼っておきます。

#include "stdio.h"

int fib2(int n){
    if(n < 2) return n;

    int a = 0;
    int b = 1;
    int r = 0;

    for (int i=2; i <= n; i++) {
        r = a + b;
        a = b;
        b = r;
    }

    return r;
}

int main (){
    printf("fib2: %d\n", fib2(100000));
    // fib2: 873876091
}

一瞬で答えが出ました。笑

やっぱりC言語は速いですね。。

まとめ

関数型言語ではこれを自動的に変換してくれます。（末尾再帰最適化）

覚えておくと便利なので、いつでも自分で変換できるようにしたいですね。

RECENT POSTS

---

---