やわらかテック

興味のあること。業務を通して得られた発見。個人的に試してみたことをアウトプットしています🍵

トップ > JavaScript > JavaScriptでのスマートな再帰関数の書き方【ECMAscript2015以降対応】

JavaScriptでのスマートな再帰関数の書き方【ECMAscript2015以降対応】

JavaScript Elixir

仕事でJavaScriptを書くことが多くなりました。以前より学んできた多くの関数型言語で一般的に使用されている再帰関数をJavaScriptでもスマートに書けないものかなと模索してみました。
「普通にforや、mapを使えば良いのでは？」という問いかけに対する答えは「イエス」です。使う機会があるかは分かりませんですが、参考になればと思います。

JavaScriptで再帰関数が書きにくい理由

元々、再帰関数を書く必要がある場面はかなり少ないかと思います。ツリー構造のようなデータを扱う場合などが該当するでしょうか。多くの場合は前述の通り、forや配列に対してmap関数を実行すれば事足ります。

しかし、その一方で関数型言語では一般的にループ処理のための文法が用意されたおらず、ループ処理を再帰関数で実装する必要があります。その際に再帰関数を実装しやすくしてくれるのはパターンマッチと呼ばれる機能です。広い機能として定義されている事が多いですが、ここでは分かりやすさのため関数の引数でのパターンマッチを一例にしておきます。

(サンプルコードはElixirを用いて記述しました)

sum([], total), do: total
sum([head| tail], total), do: sum(tail, total + head)

二行で記述することが出来ました。
関数が関数を呼び出しますので再帰関数となっています。この関数は第一引数に渡されている配列が空になった時に停止するようになっています。とはいえ、どこにもifの記述はありません。sum関数の第一引数によって実行される処理が変わります。

空配列の場合には第二引数のtotalを返し、空配列ではない時は先頭の要素を取り出して、合計の値に先頭の値を加え、再度、sum関数を呼び出します。この際に先頭要素の値が配列から取り出されているので配列の要素数は-1されています。つまり、いずれは空の配列になるため、totalが帰るということになります。

JavaScriptではこの強力なパターンマッチを使うことが出来ないため、愚直に書けば雑多なコードを書く羽目になります。

const sum = (lst, total) => {
    if(lst.length === 0) {
        return total;
    } else {
        const head = lst[0];
        const tail = lst.slice(1, lst.length);
        return sum(tail, total + head);
    }
}

const main = () => {
    const data = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
    const res = sum(data, 0);
    console.log("result: ", res);
}

main(); # result:  55

最終形態(ぼくのかんがえたさいきょうのさいきかんすう)

多分、これが一番スマートだと思います。

const sum = (lst) => _sum(lst, 0);
const _sum = (lst, accum) => {
    const [h, ...t] = lst;
    return lst.length === 0 ? accum : _sum(t, accum + h);
}

ECMAscript2015からサポートされたDestructuring assignmentsを利用して、先頭の値と、先頭以外の値(配列)に値を束縛します。

const lst = [1, 2, 3, 4, 5]
const [h, ...t] = lst;

h # 1
t # [2, 3, 4, 5]

あとは三項演算子を使って、条件を分岐させます。ここで再帰関数の停止性を保証します。

return lst.length === 0 ? accum : _sum(t, accum + h);

もう少し関数型言語っぽく書いてあげるとこんな感じでしょうか。Array.prototypeに追加して上げても良いですが、やりすぎ感はやはり否めないですね。

const sum = (lst) => _sum(lst, 0);
const _sum = (lst, accum) => lst.length === 0 ? accum : _sum(tail(lst), accum + head(lst));
　
const head = (lst) => {
    const [h, ...t] = lst;
    return h;
}
const tail = (lst) => {
    const [h, ...t] = lst;
    return t;
}

sumだけではなく、reduceもスマートな再帰関数の記述を使って書いてみました。また、このreduceを使って、sumの実装をする事も出来ました。

const reduce = (lst, callback, accum) => {
    const [h, ...t] = lst;
    const next = callback(h, accum);
    return lst.length === 0 ? accum : reduce(t, callback, next);
}

const callback = (h, accum) => accum + h;
const sum = (lst) => reduce(lst, callback, 0);

再帰関数のスマートな書き方の紹介については以上になります。以降、与太話です。

とはいえ

この程度の処理であれば、再帰関数を使わずに、map, filter, reduce を使って実装させてあげれば良いかなと思います。わざわざ、複雑な再帰関数を記述する必要はないかと思います。

const sum = (lst) => lst.reduce((accum, h) => accum + h, 0);

map, filter, reduce の使い方とコンボについては過去の記事にまとめています。

www.okb-shelf.work

www.okb-shelf.work

おまけ(最終形態になるまでの過程)

これが

// var1
const sum = (lst) => _sum(lst, 0);
const _sum = (lst, accum) => {
    if (lst.length === 0) {
        return accum;
    }
    const [h, ...t] = lst;
    return _sum(t, accum + h);
}

こうで

const sum = (lst) => _sum(lst, 0);
const _sum = (lst, accum) => {
    const [h, ...t] = lst
    const next = accum + h
    return t.length === 0 ? next : _sum(t, next);
};

こうじゃ(最終系)

const _sum = (lst, accum) => {
    const [h, ...t] = lst;
    return lst.length === 0 ? accum : _sum(t, accum + h);
}

参考文献