问题标签 [ackermann]

我最近偶然发现了Ackermann 函数，它使用一种“嵌套递归”来计算一个值。我在 C++ 中实现了我自己的函数，它缓存中间结果以加快计算速度（比较没有缓存的实现）。

问题：

ackermann最终将耗尽堆栈空间。您应该如何实现一个执行“深度递归”（多次调用自身）而不用完堆栈空间的函数？

我的实现：

玩它！

输出：

我写了一个递归版本的阿克曼函数，它工作正常：

然后我尝试迭代地重写代码：

（我不知道如何使用 malloc 使用 2D 数组，所以你会觉得代码很脏......）

但是迭代版本打印了一个错误的答案。例如：

为什么我的迭代代码不起作用？

我编写了代码来计算 Ackermann 函数并存储结果，但在某个随机点它会停止（尽管仅适用于查找版本），正常版本只是运行而不会停止。

不可能是递归限制，可能是字典太大了？不过，它并没有使用太多内存。

这是代码：

这是其中一个输出的最后一部分：

如果我再次运行它：

无需改变任何东西。哦，男孩，我喜欢不一致的结果！值得注意的是，对于较小的值，它运行得非常完美。

编辑：我刚刚尝试过这个在线python解释器，它工作得很好。

编辑2：我试过用另一个版本的python（3.8.2而不是3.7）运行它，它以堆栈溢出错误关闭。问题是它几乎没有使用内存 - 根据任务管理器最多 6.6 MB。

我正在尝试用 C++ 打印 Ackermann 的函数值

前 50 个结果是正确的，但随着数字开始增长，最后一位数字开始打印错误。

例如：

// 将 ack(m, n) 视为 ackermann 函数

case ack(3, 51) should print 18014398509481981 but instead it prints 18014398509481980. The diffence is always between 1 and 3 on the last digit case ack(3, 175) should print 383123885216472214589586756787577295904684780545900544 and it prints 383123885216472214589586756787577295904684780545900541.

我正在尝试打印这些巨大的数字而不将它们存储到变量中，因为我不知道任何可以存储如此大数字的本机 cpp 数据类型，所以我改为直接打印值：

我该怎么做才能打印正确的值？我可以做不同的吗？

为什么会失败？我用 C 语言编写了 Ackermann 的函数，并使用 long 来确保数字不会太小。然而，当我对 m 和 n 超过（包括）4 时，它给了我一个segmentation fault: 11. 有谁知道为什么？

我在考虑 Ackermann 函数，以及是否可以将这个函数扩展到 Python 中的正实数。

我发现有人在 Math Overflow 上询问了这个概念。有人可以写一个连续的阿克曼函数来处理实数吗？我想这样做，所以我可以看到一个介于指数和四分之间的函数。

我目前正在解决一个问题，即在具有尾调用优化支持的 scala 中实现 ackermann 函数的变体，以便堆栈不会溢出。

问题是，我找不到尾调用优化它的方法。有人告诉我 continuation-pass-style(CPS) 会有所帮助，但即使我成功地用 CPS 风格重新实现了它，我仍然迷路了。

阿克曼函数的变化如下：

没有优化的代码是这样的：

另一个试验是这样的：

我试图这样进行尾调用优化：

但是由于类型不匹配，这不会编译。

可能是什么问题呢？我走错方向了吗？小提示和帮助将不胜感激。谢谢 ：）

ps 我得到了提示：为什么 scala 不进行尾调用优化？

根据 Mathoverflow 上的这个问题，如何在 Python 中计算非负实数的 Ackermann 函数？

这是我的整数代码。

我尝试使用 float 并允许它在 0 和 1 之间进入，但它不是连续的。

我正在尝试运行Ackermann 函数¹，但遇到了问题。我试图通过我的命令提示符在 Windows 10 机器上运行程序，在达到值对 (4,0) 后几秒钟，程序停止。我假设是因为它已经用完了可用资源，但我完全不确定。有没有办法解决这个问题？TIA。

我正在使用 MinGw G++ 编译器 [8.1.0]。

这里也是有问题的代码。

我最初以为是因为我使用 VSCode 来访问命令提示符，但是当我直接使用它时没有任何变化。在写这个问题时，我只是想尝试不同的操作系统或 Ubuntu 看看是否有任何区别。

我的目标只是到达 (4,1)，看看现在计算速度有多快。

¹阿克曼函数是一种递归函数，它是作为计算机理论发展起来的，目的是创建一个只能递归计算的函数。

^{编辑 1} @MikeCAT 帮助我意识到我真正在问什么并回答了我的问题。

我很好奇就编译时评估而言，我可以将 gcc 推到多远，所以我让它计算Ackermann函数，特别是输入值为 4 和 1（任何高于此值都是不切实际的）：

（我认为递归深度限制在~16K，但为了安全起见，我用它编译了这个-std=c++20 -fconstexpr-depth=100000 -fconstexpr-ops-limit=12800000000）

毫不奇怪，这会占用大量的堆栈空间（事实上，如果以 8mb 的默认进程堆栈大小运行，它会导致编译器崩溃）并且需要几分钟的时间来计算。然而，它最终会到达那里，所以编译器可以处理它。

之后，我决定尝试使用模板、元函数和部分特化模式匹配来实现 Ackermann 函数。令人惊讶的是，以下实现只需要几秒钟即可评估：

（用 编译-ftemplate-depth=17000）

为什么评估时间会有如此巨大的差异？这些本质上不是等效的吗？我想我可以理解consteval需要更多内存和评估时间的解决方案，因为它在语义上由一堆函数调用组成，但这并不能解释为什么在运行时计算的这个完全相同的（非 consteval）函数只需要比元函数版本（编译时没有优化）。

为什么consteval这么慢？我几乎很想得出结论，它正在由 GIMPLE 解释器或类似的东西进行评估。还有，元功能版怎么会这么快？它实际上并不比优化的机器代码慢多少。