問題タブ [ackermann]

I recently stumbled across the Ackermann function, which uses a kind of "nested recursion" to calculate a value. I implemented my own take on the function in C++, which caches intermediate results to speed up the calculation (compare implementation without caching).

Question:

ackermann will run out of stack space eventually. How should you implement a function which does "deep recursion" (calls itself many times), without running out of stack space?

My implementation:

Play with it!

Output:

私は現在、スタックがオーバーフローしないように、末尾呼び出しの最適化をサポートする scala で ackermann 関数のバリエーションを実装するという問題を解決しています。

問題は、末尾呼び出しを最適化する方法が見つからないことです。continuation-pass-style(CPS) が役立つと言われましたが、CPS スタイルで再実装に成功したにもかかわらず、まだ道に迷っています。

アッカーマン関数のバリエーションは次のとおりです。

最適化なしのコードは次のとおりです。

別の試行は次のとおりです。

私はそれを次のように最適化しようとしました：

しかし、これは型の不一致のためにコンパイルされません。

何が問題なのですか？私は間違った方向に進んでいますか？ちょっとしたヒントや手助けをいただければ幸いです。どうも ：）

ps からヒントを得ました:なぜscalaはテールコールの最適化を行わないのですか?

アッカーマン関数¹を実行しようとしていますが、問題が発生しています。Windows 10 マシンでコマンド プロンプトからプログラムを実行しようとしていますが、値のペア (4,0) に達してから数秒後にプログラムが停止します。利用可能なリソースが不足しているためと推測していますが、まったくわかりません。この問題を解決する方法はありますか? ティア。

MinGw G++ コンパイラ [8.1.0] を使用しています。

問題のコードもここにあります。

最初はVSCodeを使ってコマンドプロンプトにアクセスしていたからだと思っていたのですが、そのまま使っても変化なし。この質問を書いている間、違いがあるかどうかを確認するために、別の OS または Ubuntu を試してみることを考えました。

私の目標は、(4,1) に到達して、計算がどれだけ速くなったかを確認することです。

¹アッカーマン関数は、再帰的にしか計算できない関数を作成するためにコンピューター理論として開発された再帰関数です。

^{編集 1} @MikeCAT は、私が本当に求めていることを理解し、質問に答えてくれました。