1

直截了当-我一直在学习brainfuck，但我无法绕过其中的递归概念。我已经用谷歌搜索并搜索了论坛 - 如果需要，请提前道歉 - 并没有提出任何结果。

首先，真的有可能吗？

如果有，有例子吗？我会添加任何我能想到的有用的东西。

我特别想用递归来计算斐波那契数，所以如果我们能以此为基础，将会有很大帮助。

4

3 回答 3

5

由于 BF 除了磁带和指针以及非常基本的循环功能之外并没有真正提供任何东西（通常你需要确保指针在它开始的地方结束，这就是所谓的平衡循环。在极少数情况下你可以在没有平衡的情况下进行循环（例如数组），在其中实现递归算法非常困难。您可以尝试在 bf 中模拟“普通”计算机（这完全取决于您如何处理磁带）。我相信 C2BF 项目以这种方式工作（它将 C 编译为brainfuck）。如果我没记错的话，他们会在交替的堆栈/堆对中处理单元组（使某些指针操作有点不同，因为所有内容都必须乘以 2）

所以，在所有这些文本之后，这是我的结论：虽然它真的很困难，但在 Brainfuck 中实现递归算法是可能的。我敦促您记住的是，每个递归算法都可以迭代地完成。您只需要维护自己的堆栈即可。如果您想递归地实现它，这实际上就是您最终要做的事情。但是，如果您将其视为迭代并维护自己的堆栈，而不是递归，它将帮助您了解您实际在做什么，并最终产生更好的设计算法。

于 2012-12-08T23:29:01.570 回答
1

更新：我已经实现了这样的事情。https://github.com/benrap/Assembly2Brainfuck

原始信息：

我还没有实现这样的东西，但我会更新一次。但是，我想到了一个真正的递归函数的实现。首先请注意，brainfuck 只在一个方向上运行代码，因此我们实际上不能使用代码存储进行递归。我们拥有的唯一其他存储方式是代码正在更改的存储。所以实际上，我们必须编写代码将我们的函数保存在存储中，然后读取该存储而不更改它并相应地执行它。这反过来将需要一个堆栈和一些更复杂的东西。

正如我所说，我计划进行这样的实现，所以一旦我有了一个工作原型，我就会更新。希望我的回答就足够了。

于 2018-09-23T17:27:27.000 回答
0

标准 Brainfuck 既没有调用也没有调用堆栈，因此您必须实现自己的堆栈才能进行递归编程。

二维语言 SNUSP 具有与 Brainfuck 相同的运算符和内存模型，但增加了调用堆栈和 ENTER（“@”）和 LEAVE（“#”）指令，允许递归编程。Brainfuck 用于循环的括号替换为反射器（“\”、“/”）、跳过（“！”）和如果为零则跳过（“？”）。例如，这里是斐波那契函数的递归实现：

             /========\    />>+<<-\  />+<-\
fib==!/?!\-?!\->+>+<<?/>>-@\=====?/<@\===?/<#
      |  #+==/     fib(n-2)|+fib(n-1)|
      \=====recursion======/!========/
于 2013-06-20T20:53:35.033 回答