Zenn
💯

「ｺｲﾂ, ﾃﾞｷﾙ...!!」ってなるかもしれない再帰関数の作り方

2022/01/23に公開
3件
JavaScript
TypeScript
function
cs
optimization
tech

再帰関数、使ってますか？

再帰関数は使い方によっては非常にパワフルな味方になる一方で、その実装によってスタックオーバーフローを起こしてしまいかねません。

再帰関数とは

再帰関数とは、その処理内部で再びその関数自身を呼び出すような関数のことを指します。
こんな感じの処理が再帰処理にあたります。

// N の階乗（N!） を求める
function factorial(N: number){
  if (N === 1) return 1
  return N * factorial(N-1)
}
console.log(factorial(5)) // 120 (=5*4*3*2*1)

// 文字列の左側にあるスペースを削除した型を作る TrimLeft 型
type Space = ' ' | '\n' | '\t'
type TrimLeft<S extends string> = S extends `${Space}${infer R}` ? TrimLeft<R> : S
type Trimmed = TrimLeft<'  hoge'> // Trimmed: 'hoge'

この記事を読めば、再帰関数のポテンシャルを最大限生かすように実装でき、他の人から 「コイツ...デキル...!!?!」 ってなるかもしれません（?）

場合によっては数百, 数千倍高速な関数を作ることができます。

（記事の内容としては「末尾最適化」と呼ばれるテクニックになります。ご存じの方はブラウザバックを推奨します 🙏 ）

例題

フィボナッチ数列 （a_n = a_{n-1} + a_{n-2}） （1個前と2個前の和が今の項の値）の 100 番目の値を求めてみましょう。
この漸化式を直接コードに落とし込むと次のようになります。

const fibonacchi = (n) => {
  if (n === 1) return 1;
  if (n === 2) return 1;
  return fibonacchi(n-1) + fibonacchi(n-2)
}
console.log(fibonacchi(100))

これを使って fibonacchi(100) をブラウザで実行しようとすると...
おそらく答えが求まりません😇
ブラウザの JS エンジンのスタック上限に到達してしまうためです。

しかし、この関数実装を後に紹介する手法で最適化すると第1000項目ですら一瞬で求めることができます。

まずはなぜ今の実装だと遅いのかを考えてみましょう。
原因は finobacci 関数1回の呼び出しにつき、2回 fibonacchi 関数を呼び出し、その結果を待っているからです。もう少し詳しく書くと、

  • fibonacchi(100) は fibonacchi(99) と fibonacchi(98) の結果を待つ。
  • fibobacchi(99) は finonacchi(98) と fibonacchi(97) の結果を待つ。
  • fibonacchi(98) は fibonacchi(97) と fibonacchi(96) の結果を待つ。
  • ...

という連鎖が起き、 結果的に破滅的な量のスタックが積まれていくことになります。
最終的にスタックオーバーフローを引き起こしてしまいます。

改善案

問題点は 「再帰のたびにスタックが積まれていくこと」 です。
これを改善する 「末尾再帰」 というテクニックがあります。

誤解を恐れずに簡単に言うと、
「関数の return 部分で その関数自身だけ　を返す」
というものです。

コードで言うと、以下のような実装になります。

function recursive(foo) {
	...
	return recursive(bar)
}

これによって、 recursive(foo) はその返り値の値を待つ必要がなく、次の recursive(bar) に処理を丸投げすることが可能になります。

とにかく、関数の定義と返り値の形状を同じにすることが大事です。
理由の詳細についてはわかりやすい記事がありますのでそちらをご覧ください。

https://qiita.com/pebblip/items/cf8d3230969b2f6b3132

https://rn4ru.com/blog/posts/tail-recursion/

末尾再帰してみる

先ほどのフィボナッチ数列を求める関数を末尾再帰を用いて最適化してみると次のようになります。

const optimized = (n, a0 = 0, a1 = 1) => {
  if (n === 1) return a1;
  return optimized(n-1, a1, a0+a1);
}

引数の数が増えているのはさておき、ポイントは return 部分で optimized(n-1, a1, a0+a1) を返している部分です。
関数定義と返り値の形が同じになっています。これによって末尾再帰が実現されています。

ちなみにこれがどれほど高速かを調べてみると、第40項の計算で約8000倍速い[1]です🚀

自分の目で確かめたい方

ブラウザの console に以下のコードを貼り付けてみましょう。

const measureDuration = (fn) => {
  const start = performance.now();
  const answer = fn()
  const end = performance.now();
  console.log(`duration: ${end - start} milliseconds, ans: ${answer}`);
  return answer
}

const fibonacchi = (n) => {
  if (n === 1) return 1;
  if (n === 2) return 1;
  return fibonacchi(n-1) + fibonacchi(n-2)
}
const optimized = (n, a0 = 0, a1 = 1) => {
  if (n === 1) return a1;
  return optimized(n-1, a1, a0+a1);
}
const N = 40
measureDuration(() => fibonacchi(N))
measureDuration(() => optimized(N))

なぜこうなったかを一緒に見ていきましょう。

どうしてこうなる？

最適化後のコードが何をしているのかをもう一度確認してみます。

const optimized = (n, a0 = 0, a1 = 1) => {...}

なぜこのような形になったのかを追っていきましょう。
考慮すべきことは以下の通りです。

  • 末尾再帰をするために return 部分でその関数だけを呼び出さないといけない
  • フィボナッチ数列は直前の2項から計算できる
  • 関数は状態をもつことができない

フィボナッチ数列を求めるのに、過去の項を知っておく必要があるのにも関わらず、一般に関数は状態を持つことができません。

そこで、引数を使って欲しい情報を引数に持っておくことを考えます。

フィボナッチ数列において必要な情報は直前の2項だけです。
つまり、直前の2項から新しい項を計算し、最新の2項を引数に保存すれば良いわけです。

では、先ほどのコードをもう一度見てみましょう。

const optimized = (n, a0 = 0, a1 = 1): number => {
  if (n === 1) return a1;
  return optimized(n-1, a1, a0+a1);
}

optimized(6)
// = optimized(6, 0, 1)
// = optimized(5, 1, 1)
// = optimized(4, 1, 2)
// = optimized(3, 2, 3)
// = optimized(2, 3, 5)
// = optimized(1, 5, 8)
// = 8

3つの引数のうち後ろ2つが必要な2項を保存しておく引数になっており、これを使いながらフィボナッチ数列を初項から順番に計算していることがわかります。
これによって、関数自体は値を保存せずとも、引数に必要な情報を持っておくことで末尾再帰を実現することができました。

他にも

末尾再帰はフィボナッチ数列に限定的な手法ではありません。

  • 階乗を求める関数
// Bad
const factorial = (n: number): number => {
  if (n===1) return 1;
  return n * factorial(n-1)
}
// Good
const optimized = (n: number, mult=1): number => {
  if (n === 1) return mult;
  return optimized(n-1, mult * n)
}
  • 文字列に含まれるスペースを消す型
type TrimLeft<T extends string> = T extends ` ${infer Rest}` ? TrimLeft<Rest> : T
type Trimmed = TrimLeft<"   hoge">; // hoge

などなど。このように、末尾再帰は様々な部分で生かされています。
特に二つ目の TypeScript の例では、以前は再帰上限が 50 だったのが、この末尾最適化によって、より深い再帰ができるようになりました。（v4.5以降）

https://devblogs.microsoft.com/typescript/announcing-typescript-4-5/?ranMID=43674&ranEAID=rl2xnKiLcHs&ranSiteID=rl2xnKiLcHs-Nu8OJLd0Kmttmkc8witkUw&epi=rl2xnKiLcHs-Nu8OJLd0Kmttmkc8witkUw&irgwc=1&OCID=AID2200057_aff_7795_1243925&tduid=(ir__te0uwketuwkf6gb3tnpxotqtte2xo9ek0xf9wls100)(7795)(1243925)(rl2xnKiLcHs-Nu8OJLd0Kmttmkc8witkUw)()&irclickid=_te0uwketuwkf6gb3tnpxotqtte2xo9ek0xf9wls100#tailrec-conditional

他にもあなたが知らないところで末尾再帰が活かされているかもしれません。

終わりに

再帰関数の最適化手法の一つである「末尾再帰」について説明しました。
これを活かしてよりハイパフォーマンスな再帰関数を作っていきましょう！

参考になった！という方はぜひいいねやtwitterのフォローをよろしくお願いします🙏

（「ソフトウェアデザイン」2月号にて再帰関数が紹介されていましたが、末尾最適化の詳細が省かれていた（紙面の都合上？）ので書きたくなって書きました）

脚注

  1. safari のJSエンジンのみが末尾最適化に対応しているので、 safari で実行することをおすすめします。コメントにて指摘していただきましたが、正確には上記のコードが爆速なのはアルゴリズムの違いによるものです。しかし、本記事では末尾最適化を意識して実装するとアルゴリズム的にも効率的になる、ということを実感していただければと思います。将来的により多くのブラウザが末尾最適化に対応してもらえることを祈りましょう🙏 ↩︎

Discussion

tktk

フィボナッチ数列の計算が早くなったのは末尾再帰最適化の恩恵ではなく、計算量の小さいアルゴリズムへの書き換えになっているからではないでしょうか。ググってみると前者は定義通りのアルゴリズムで、後者は数え上げ式や積み上げ式と呼ばれているアルゴリズムのようです。
また、こちらの資料によると末尾再帰最適化はSafariのみ実装済みで、他の実行環境では実装されていないようです。
事実、本記事内で用意いただいたTS PlaygroundをChromeで開いてN=40000などとすると、optimized()の呼び出しでもスタックオーバーフローが発生します。つまり、Chrome上では末尾再帰最適化がされていないことが確認できます。しかし、Chrome上であってもN=40の場合にoptimized()の計算が早いことから、末尾再帰最適化とは関係がなく、アルゴリズム的に早いだけであることがわかります。

kj455kj455

コメントありがとうございます。
tk さんのおっしゃる通りで、 末尾最適化が safari のみでの実装になっていることをこちらでも確認しました。
こちらの勉強不足で不正確な表現をしてしまいました。該当箇所に追記しておきます。ご指摘ありがとうございました！

pennepenne

試しに以下環境で実行したら固まった。動かなかった


const fibonacchi = (n) => {
  if (n === 1) return 1;
  if (n === 2) return 1;
  return fibonacchi(n-1) + fibonacchi(n-2)
}
console.log(fibonacchi(100))

https://playcode.io/typescript