一个reddit 线程提出了一个明显有趣的问题：
尾递归函数可以很容易地转换为迭代函数。其他的，可以通过使用显式堆栈进行转换。每个递归都可以转化为迭代吗？
帖子中的（反？）示例是一对：
(define (num-ways x y)
(case ((= x 0) 1)
((= y 0) 1)
(num-ways2 x y) ))
(define (num-ways2 x y)
(+ (num-ways (- x 1) y)
(num-ways x (- y 1))
你总能把递归函数变成迭代函数吗？是的，绝对是，如果有记忆的话，Church-Turing 论文就证明了这一点。通俗地说，它指出可以通过递归函数计算的内容可以通过迭代模型（例如图灵机）计算，反之亦然。论文并没有准确地告诉你如何进行转换，但它确实说这绝对是可能的。
在许多情况下，转换递归函数很容易。Knuth 在“计算机编程的艺术”中提供了几种技术。通常，递归计算的事物可以通过完全不同的方法在更少的时间和空间内进行计算。典型的例子是斐波那契数列或数列。你肯定在你的学位计划中遇到过这个问题。
在这枚硬币的另一面，我们当然可以想象一个编程系统如此先进，以至于将公式的递归定义视为记忆先前结果的邀请，从而提供速度优势，而无需麻烦告诉计算机确切的步骤遵循具有递归定义的公式的计算。Dijkstra 几乎可以肯定地想象过这样一个系统。他花了很长时间试图将实现与编程语言的语义分开。再说一次，他的非确定性和多处理编程语言在实践中的专业程序员之上。
归根结底，许多函数以递归形式更易于理解、阅读和编写。除非有令人信服的理由，否则您可能不应该（手动）将这些函数转换为显式迭代算法。您的计算机将正确处理该作业。
我可以看到一个令人信服的理由。假设您有一个使用超高级语言的原型系统，例如 [穿上石棉内衣] Scheme、Lisp、Haskell、OCaml、Perl 或 Pascal。假设条件是您需要用 C 或 Java 实现。（也许这是政治问题。）然后你当然可以递归地编写一些函数，但如果按字面意思翻译，它们会炸毁你的运行时系统。例如，无限尾递归在 Scheme 中是可能的，但同样的习惯用法会给现有的 C 环境带来问题。另一个例子是使用词法嵌套函数和静态作用域，Pascal 支持但 C 不支持。
在这种情况下，您可能会尝试克服对原始语言的政治阻力。你可能会发现自己重新实现 Lisp 很糟糕，就像 Greenspun（面面相觑）的第十条定律一样。或者您可能会找到一种完全不同的解决方案。但无论如何，肯定有办法的。
是否总是可以为每个递归函数编写一个非递归形式？
是的。一个简单的形式证明是证明μ 递归和非递归演算（如 GOTO）都是图灵完备的。由于所有图灵完备演算在表达能力上是严格等价的，所有递归函数都可以通过非递归图灵完备演算来实现。
不幸的是，我无法在网上找到一个好的、正式的 GOTO 定义，所以这里有一个：
GOTO 程序是在寄存器机器上执行的一系列命令P，使得P是以下之一：
HALT, 停止执行r = r + 1哪里r有寄存器r = r – 1哪里r有寄存器GOTO xx标签在哪里IF r ≠ 0 GOTO xr任何寄存器在哪里，x是一个标签但是，递归函数和非递归函数之间的转换并不总是微不足道的（除非通过手动重新实现调用堆栈）。
有关详细信息，请参阅此答案。
递归在实际的解释器或编译器中被实现为堆栈或类似的结构。因此，您当然可以将递归函数转换为迭代函数，因为它总是这样做的（如果是自动的）。您将只是临时复制编译器的工作，并且可能以一种非常丑陋和低效的方式。
基本上是的，本质上你最终要做的是将方法调用（隐式地将状态推送到堆栈上）替换为显式堆栈推送，以记住“先前调用”已经到达的位置，然后执行“调用方法”反而。
我想通过基本上模拟方法调用，循环、堆栈和状态机的组合可以用于所有场景。这是否会“更好”（更快，或者在某种意义上更有效）通常很难说。
递归函数执行流程可以表示为一棵树。
相同的逻辑可以通过循环来完成，循环使用数据结构遍历该树。
深度优先遍历可以使用栈完成，广度优先遍历可以使用队列完成。
所以，答案是：是的。为什么：https ://stackoverflow.com/a/531721/2128327 。
任何递归都可以在一个循环中完成吗？是的，因为
图灵机通过执行一个循环来完成它所做的一切：
- 获取指令，
- 评价一下，
- 转到 1。
是的，显式使用堆栈（但递归更容易阅读，恕我直言）。
是的，总是可以编写非递归版本。简单的解决方案是使用堆栈数据结构并模拟递归执行。
原则上，总是可以删除递归并用迭代替换它，这种语言对于数据结构和调用堆栈都具有无限状态。这是 Church-Turing 命题的一个基本结论。
给定一种实际的编程语言，答案并不那么明显。问题是很可能有一种语言可以在程序中分配的内存量是有限的，但可以使用的调用堆栈的数量是无限的（32位C，其中堆栈变量的地址不可访问）。在这种情况下，递归更强大只是因为它有更多的内存可以使用；没有足够的显式可分配内存来模拟调用堆栈。有关这方面的详细讨论，请参阅此讨论。
所有可计算函数都可以由图灵机计算，因此递归系统和图灵机（迭代系统）是等价的。
有时替换递归比这容易得多。递归曾经是 1990 年代 CS 中流行的东西，所以从那时起，很多普通开发人员认为如果你用递归解决问题，这是一个更好的解决方案。所以他们会使用递归而不是向后循环以反转顺序，或者类似的愚蠢的事情。所以有时删除递归是一种简单的“呃，这很明显”类型的练习。
现在这不是一个问题，因为时尚已经转向其他技术。
可以将任何递归算法转换为非递归算法，但通常逻辑要复杂得多，这样做需要使用堆栈。事实上，递归本身使用了一个栈：函数栈。
更多详情：https ://developer.mozilla.org/en-US/docs/Web/JavaScript/Guide/Functions
除了显式堆栈之外，将递归转换为迭代的另一种模式是使用蹦床。
在这里，函数要么返回最终结果，要么返回本来会执行的函数调用的闭包。然后，启动（蹦床）函数继续调用返回的闭包，直到达到最终结果。
这种方法适用于相互递归的函数，但恐怕它只适用于尾调用。
我会说是的 - 函数调用只不过是 goto 和堆栈操作（粗略地说）。您需要做的就是模仿在调用函数时构建的堆栈，并执行类似于 goto 的操作（您可以使用没有明确包含 this 关键字的语言来模仿 goto）。
递归只是在堆栈上调用相同的函数，一旦函数消失，它就会从堆栈中删除。因此，人们总是可以使用显式堆栈来管理使用迭代对同一操作的调用。 所以，是的，所有递归代码都可以转换为迭代。
tazzego，递归意味着无论你喜欢与否，一个函数都会调用它自己。当人们谈论是否可以在没有递归的情况下完成某事时，他们的意思是，您不能说“不，那不是真的，因为我不同意递归的定义”作为有效陈述。
考虑到这一点，你说的其他一切都是胡说八道。您说的唯一另一件事不是胡说八道，那就是您无法想象没有调用堆栈的编程。这是几十年来一直在做的事情，直到使用调用堆栈变得流行。旧版本的 FORTRAN 缺少调用堆栈，它们工作得很好。
顺便说一句，存在仅将递归（例如 SML）实现为循环方式的图灵完备语言。也存在图灵完备的语言，它们仅将迭代作为一种循环方式来实现（例如 FORTRAN IV）。Church-Turing 论文证明，在仅递归语言中任何可能的事情都可以在非递归语言中完成，反之亦然，因为它们都具有图灵完备性。
这是一个迭代算法：
def howmany(x,y)
a = {}
for n in (0..x+y)
for m in (0..n)
a[[m,n-m]] = if m==0 or n-m==0 then 1 else a[[m-1,n-m]] + a[[m,n-m-1]] end
end
end
return a[[x,y]]
end