✨

なぜ末尾再帰を行うのか

2021/04/28に公開

関数型プログラミング

tech

本記事は主に以下のオンライン学習コースにて得た知見をもとに書いています。

総和を求める関数を再帰関数で実装する

次のような関数を考えます。

数列が格納されたリスト（ここでは配列を用いる）を受け取りその総和を求める関数

まずは、この関数を再帰を用いて愚直に書いていきましょう。言語はTypeScriptを使います。
また、次のheadとtailは実装に用いる補助的な関数です。

 const head = <T extends any>(arg: T[]): T => arg[0];
 const tail = <T extends any>(arg: T[]): T[] => arg.slice(1);

愚直な実装

const sum = (nums: number[]): number => {
  if (nums.length === 0) return 0;
  return head(nums) + sum(tail(nums));　// 関数の結果が返却される位置を「末尾」という。
};

以上のコードは末尾再帰が施されていないコードです。
sum([1, 2, 3, 4, 5])が実行されると、次のように計算式が評価待ちのスタックへと積み上がっていきます。

sum([1, 2, 3, 4, 5])
1 + sum(tail([2, 3, 4, 5]))
1 + 2 + sum(tail([3, 4, 5]))
1 + 2 + 3 + sum(tail([4, 5]))
1 + 2 + 3 + 4 + sum(tail([5]))
1 + 2 + 3 + 4 + 5 + sum(tail([]))
1 + 2 + 3 + 4 + 5 + 0 //ここまで展開されてようやく前から順に評価されていく
3 + 3 + 4 + 5 + 0
6 + 4 + 5 + 0
10 + 5 + 0
15 + 0
15 // 答え

これではリストの長さが長くなるとすぐに再帰スタックが溢れてしまいます。（リストの長さが1000だと1001項分の式が積み上がります。）
この問題を解消すべく、評価待ちの式がスタックに積みあがらないようにする実装方法として末尾再帰とよばれるものがあります。

末尾再帰での実装

以下のtailRecSum関数はsum関数を末尾再帰を用いて実装しなおしたものです。
なお引数accはaccumulatorから命名しています。accは計算結果を蓄積していく引数です。

const tailRecSum = (nums: number[]): number => {
  const localSum = (nums: number[], acc: number): number => {
    if (nums.length === 0) return acc;
    return localSum(tail(nums), acc + head(nums)); // 末尾に計算式ではなく再帰を置いている。このような関数を末尾再帰関数などと呼ぶ。計算自体は引数で行う。
  };
  return localSum(nums, 0)
};

このコードは次のように評価されていきます。
localSumの引数に渡される際に毎回足し算の評価が行われるため、評価待ちの計算式が再帰スタックを圧迫することはありません。

tailRecSum([1, 2, 3, 4, 5])
localSum([1, 2, 3, 4, 5], 0)
localSum([2, 3, 4, 5], 0 + 1)
localSum([2, 3, 4, 5], 1)
localSum([3, 4, 5], 1 + 2)
localSum([3, 4, 5], 3)
localSum([4, 5], 3 + 3)
localSum([4, 5], 6)
localSum([5], 6 + 4)
localSum([5], 10)
localSum([], 10 + 5)
localSum([], 15)
15　// 答え

まとめ

愚直に再帰関数を実装すると評価待ちの式によって再帰スタックが簡単に溢れてしまうような実装になることがある。
末尾再帰というテクニックを用いると評価待ちの式を削減することができる。

総和を求める関数を再帰関数で実装する

愚直な実装

末尾再帰での実装

まとめ

Discussion