頻出の再帰処理とクロージャーパターンを覚えよう

始めに

再帰処理では処理速度を向上したり無限ループを防ぐために処理と処理の間で共有する記憶データを利用する場合があリます。
そのような記憶データは再帰関数の外側に定義する必要がありますが、再帰関数をエクスポートして再利用する場合に記憶データを保持する変数がメモリリークの原因となってしまいます。
この記事ではそのような再帰処理で共有される変数をクロージャーの中に閉じ込めるパターンを紹介します。

1.単純な再帰処理

再帰処理の例ではフィボナッチ数列の例がよく上がります。フィボナッチ数列は、前の二つの数字を足して次の数字を作っていく数列です。

0 1 1 2 3 5 8 13 ... 

typescriptでフィボナッチ関数のf(n)を求める式は以下のようになります。

function fibonacci(n: number): number {
    if (n === 0) {
        return 0;
    }
    if (n === 1) {
        return 1;
    }
    return fibonacci(n - 2) + fibonacci(n - 1);
}

2.メモリを用いた再帰処理

1の例でアルゴリズムは動くが、fibonacci(100)を実行してみるととても長い実行時間がかかってしまいます。
これが何故かというと、フィボナッチ関数が同じ計算を何度も繰り返しているためです。例えば、 f(100)はf(99)とf(98)を呼び出し、f(99)はf(98)とf(97)を呼び出し、f(98)はf(97)とf(96)を呼び出し...と続きます。ここで、f(98)とf(97)は二回呼び出されている事が分かります。
f(0)などは全てのf(x)から呼び出され、合計で実行される数は2^100となっています。
しかし、本来ならば計算しなければいけない数はf(100),f(99),f(98)...f(0)の合計100の計算でいいはずです。

100回の計算ですませるためには、一度した計算結果を保存しておき、計算済みの値を再利用するようにします。

書き換えると以下のようになります。

fibonacci-memory.ts

const memory: {
    [ key: number ]: number
} = {};

export function fibonacci(n: number): number {
    let result;
    if (n === 0) {
        result = 0;
    } else if (n === 1) {
        result = 1;
    } else {
        result =
            (memory[ n - 1 ] ? memory[ n - 1 ] : fibonacci(n - 1))
            + (memory[ n - 2 ] ? memory[ n - 2 ] : fibonacci(n - 2));
    }
    memory[ n ] = result;
    return result;
}

console.time("fibonacci");
console.log(fibonacci(100));
console.timeEnd("fibonacci");

少し複雑ですが、要はフィボナッチ関数で一度計算した結果をmemoryに格納して再利用するように実装したものです。実行してみると、数秒で計算が完了します。

$ ts-node fibonacci-memory.ts 
354224848179262000000
fibonacci: 2.280ms

3.メモリを用いた再帰処理のクロージャー関数

さて、ここでこのフィボナッチ関数を外部のファイルからインポートして使いたいとします。

fibonacchi-import.ts

import { fibonacci } from "./fibonacci-memory";

console.time("fibonacci");
console.log(fibonacci(100));
console.timeEnd("fibonacci");

実行してみると以下のようになります。

$ ts-node fibonacci-import.ts 
354224848179262000000
fibonacci: 2.429ms

外部ファイルから利用してもmemoryオブジェクトによって処理が早くなっています。しかし、フィボナッチ関数の外にあるmemoryは関数の実行が終わってもメモリから解放されず、メモリリークを起こしてしまいます。

これを防ぐために、クロージャー関数でfibonacci関数をくくりましょう。

fimanacci-memory-colosure.ts

function fibonacciClosure(m: number) {
    const memory: {
        [ key: number ]: number
    } = {};

    function fibonacci(n: number): number {
        let result;
        if (n === 0) {
            result = 0;
        } else if (n === 1) {
            result = 1;
        } else {
            result =
                (memory[ n - 1 ] ? memory[ n - 1 ] : fibonacci(n - 1))
                + (memory[ n - 2 ] ? memory[ n - 2 ] : fibonacci(n - 2));
        }
        memory[ n ] = result;
        return result;
    }

    return fibonacci(m);
}

これでフォボナッチ関数の呼び出し完了とともにmemoryは解放されメモリリークを起こすことはなくなります。

fibonacci-import.ts

import { fibonacciClosure } from "./fibonacci-memory-closure";
console.log(fibonacciClosure(100));