每个recursion都可以转换成迭代吗？

一个reddit线程提出了一个显然有趣的问题：

尾recursion函数可以平凡地转换成迭代函数。 其他的，可以通过使用明确的堆栈进行转换。 每个recursion都可以转化为迭代吗？

post中的（counter？）例子是一对：

(define (num-ways xy) (case ((= x 0) 1) ((= y 0) 1) (num-ways2 xy) )) (define (num-ways2 xy) (+ (num-ways (- x 1) y) (num-ways x (- y 1)) 

Answer 1

你总是可以把recursion函数变成迭代函数吗？ 是的，绝对的，如果记忆服务的话，教会 – 图灵论文certificate了这一点。 从根本上说，recursion函数可以计算的是迭代模型（如图灵机），反之亦然。 这个论题并没有告诉你如何做这个转换，但是它确实说明了这是完全可能的。

在许多情况下，转换recursion函数很容易。 Knuth在“计算机编程的艺术”中提供了几种技巧。 而且往往recursion计算的东西可以通过一个完全不同的方法在更短的时间和空间中计算出来。 斐波纳契数字或其序列的典型例子。 你的学位计划肯定会遇到这个问题。

在这个硬币的另一面，我们当然可以想象一个如此先进的编程系统，以便将公式的recursion定义作为对先前结果进行记忆的邀请，从而提供速度优势而没有告诉计算机确切的步骤按照recursion定义计算公式。 迪克斯特拉几乎确实想到了这样一个系统。 他花了很长时间试图将实现从编程语言的语义中分离出来。 再次，他的非确定性和多处理程序devise语言在专业程序员之上。

归根结底，许多函数只是简单易懂，recursionforms的读，写。 除非有令人信服的理由，否则您可能不应该（手动）将这些函数转换为明确的迭代algorithm。 您的计算机将正确处理该作业。

我可以看到一个令人信服的理由。 假设你有一个超级高级语言的原型系统，比如[ 穿石棉内衣 ] Scheme，Lisp，Haskell，OCaml，Perl或者Pascal。 假设条件是这样的，你需要在C或Java中的实现。 （也许是政治。）那么你当然可以recursion地写一些函数，但是从字面上来说，这会翻译你的运行时系统。 例如，Scheme中可能有无限的尾recursion，但是相同的习惯用法会导致现有的C环境出现问题。 另一个例子是使用词法嵌套函数和静态作用域，这是Pascal支持的，但是C不支持。

在这种情况下，你可能会试图克服对原文的政治抵制。 你可能会发现自己重新实施了Lisp，就像在Greenspun（第十一章）中的第十个法则一样。 或者你可能会发现一个完全不同的解决scheme。 但无论如何，肯定是有办法的。

Answer 2

为每个recursion函数总是可以写一个非recursion的forms吗？

是。 一个简单的forms化certificate就是显示μrecursion和非recursion演算（如GOTO）都是图灵完备的。 由于所有的图灵完全的结石在expression能力上是严格等价的，所以所有的recursion函数都可以通过非recursion的图灵完全演算来实现。

不幸的是，我无法在网上find一个好的，正式的GOTO定义，所以这里有一个：

GOTO程序是在注册机器上执行的一系列命令P ，使得P是以下之一：

• HALT ，暂停执行
• r = r + 1其中r是任何寄存器
• r = r – 1其中r是任何寄存器
• GOTO x其中x是标签
• IF r ≠ 0 GOTO x其中r是任何寄存器， x是标签
• 一个标签，紧接着上面的任何一个命令。

然而，recursion和非recursion函数之间的转换并不总是微不足道的（除非通过无意识的手动重新实现调用堆栈）。

Answer 3

recursion在实际的解释器或编译器中被实现为堆栈或类似的结构。 所以你当然可以将recursion函数转换为迭代函数， 因为这是总是完成的（如果是自动的） 。 你只是在一个临时的复制编译器的工作，可能是在一个非常丑陋和低效率的方式。

Answer 4

基本上是的，实质上你最终不得不做的是将方法调用（隐式地将状态推入堆栈）变成明确的堆栈推进，以记住“先前调用”已经到达的位置，然后执行“调用方法”代替。

我可以想象，通过基本模拟方法调用，循环，堆栈和状态机的组合可以用于所有场景。 一般来说，这是否会变得更好（在某种意义上，要么更快，要么更有效率）是不可能的。

Answer 5

是的，明确使用一个堆栈（但recursion是更愉快的阅读，恕我直言）。

Answer 6

• recursion函数执行stream程可以表示为一棵树。

• 同样的逻辑可以通过循环完成，循环使用数据结构遍历树。

• 深度优先遍历可以使用堆栈完成，广度优先遍历可以使用队列完成。

所以，答案是：是的。 为什么： https : //stackoverflow.com/a/531721/2128327 。

任何recursion都可以在一个循环中完成吗？ 是的，因为

图灵机通过执行单个循环完成所有工作：

1. 取指令，
2. 评估它，
3. 转到1

Answer 7

是的，总是可以写一个非recursion的版本。 简单的解决scheme是使用堆栈数据结构并模拟recursion执行。

Answer 8

原则上总是可以删除recursion，并用具有无限状态的语言（用于数据结构和调用堆栈）进行迭代来replace它。 这是教会 – 图灵论文的基本结果。

给定一个实际的编程语言，答案不是那么明显。 问题在于，在程序中可以分配的内存量是有限的，但是可以使用的调用堆栈的数量是无限的（32位C，其中堆栈variables的地址不可访问）。 在这种情况下，recursion更加强大，因为它拥有更多的内存。 没有足够的显式可分配内存来模拟调用堆栈。 有关这方面的详细讨论，请参阅此讨论 。

Answer 9

所有可计算的函数都可以由图灵机来计算，因此recursion系统和图灵机（迭代系统）是等价的。

Answer 10

去除recursion是一个复杂的问题，在明确的情况下是可行的。

以下情况是简单的：

• 尾recursion
• 直接线性recursion

Answer 11

来自显式堆栈的另一种将recursion转换为迭代的模式是使用蹦床。

在这里，函数返回最终的结果，或者返回本来会执行的函数调用的closures。 然后，启动（trampolining）函数继续调用返回的闭包，直到达到最终结果。

这种方法适用于相互recursion的函数，但恐怕它只适用于tail-calls。

http://en.wikipedia.org/wiki/Trampoline_(computers）;

Answer 12

有时replacerecursion比这要容易得多。 recursion曾经是20世纪90年代在CS中所教导的时尚事物，所以当时很多普通的开发人员都认为如果用recursion方法解决某些问题，这是一个更好的解决scheme。 所以他们会使用recursion而不是向后循环倒序，或者像这样愚蠢的事情。 所以有时候删除recursion是一个简单的“那，这是显而易见的”types的练习。

现在这个问题不大，因为时尚已经转向了其他技术。

Answer 13

我会说是的 – 一个函数调用不过是一个goto和一个堆栈操作（粗略地说）。 所有你需要做的就是在调用函数的时候模仿构build的堆栈，并且做一些类似的goto（你也可以用没有明确使用这个关键字的语言来模仿gotos）。

Answer 14

看看下面的维基百科条目，你可以用它们作为一个起点，find你的问题的完整答案。

• 计算机科学中的recursion
• 复发关系

遵循一个段落，可能会给你一些启动的提示：

求解一个recursion关系意味着获得一个封闭的解决scheme ：n的非recursion函数。

也看看这个条目的最后一段。

Answer 15

将任何recursionalgorithm转换为非recursionalgorithm是可能的，但是通常逻辑要复杂得多，因此需要使用堆栈。 实际上，recursion本身使用一个堆栈：函数堆栈。

更多细节： https ： //developer.mozilla.org/en-US/docs/Web/JavaScript/Guide/Functions

Answer 16

tazzego，recursion意味着一个函数会自动调用，不pipe你喜不喜欢。 当人们谈论事情是否能够没有recursion的时候，他们是这个意思，你不能说“不，那不是真的，因为我不同意recursion定义”是一个有效的陈述。

考虑到这一点，你所说的一切都是无稽之谈。 你所说的唯一不是无稽之谈就是你不能想象没有一个调用堆栈的编程。 这是几十年来所做的事情，直到使用一个调用堆栈变得stream行。 老版本的FORTRAN没有一个调用堆栈，他们工作得很好。

顺便说一下，存在仅实现recursion（例如SML）作为循环的手段的图灵完备语言。 还有一些Turing完全的语言，它们只是将迭代作为循环的一种手段（例如FORTRAN IV）。 Church-Turing的论文certificate，只有recursion语言的任何可能都可以用非recursion语言来完成，反之亦然，因为它们都具有图灵完备性。

Answer 17

这是一个迭代algorithm：

 def howmany(x,y) a = {} for n in (0..x+y) for m in (0..n) a[[m,nm]] = if m==0 or nm==0 then 1 else a[[m-1,nm]] + a[[m,nm-1]] end end end return a[[x,y]] end 

Answer 18

作业问题，是吧？

我从CS课程中学到的东西是，尾端recursion总是可写为非recursion， 其他types的recursion可能是，但这不是一个绝对的规则。

为了certificate你的答案，你必须这样做，这是你的家庭作业;-)

Answer 19

一个问题：如果这个函数在一个随机的void空间中创build一个副本，而不是调用自己调用这个副本，那么这仍然是recursion吗？（1）我会说是的。

是显式使用堆栈的一种真正的方法来消除recursion？ （2）我会说不。 基本上，我们是不是模仿使用显式recursion时会发生什么？ 我相信我们不能简单地将recursion定义为“自我调用的函数”，因为我在“复制代码”（1）和“显式使用堆栈”（2）中也看到了recursion。

而且，我不明白CT如何certificate所有的recursionalgorithm都可以迭代。 它似乎只是对我说，具有图灵机“力量”的“一切”可以expression所有可以expression的algorithm。 如果图灵机不能recursion，我们确信每个recursionalgorithm都有其对应的转换…图灵机可以recursion吗？ 据我所知，如果可以“实施”（无论如何），那么我们可以说是有的。 有吗？ 我不知道。

我所知道的所有真正的CPU都可以recursion。 老实说，我看不到如何编程为真正的没有一个调用堆栈，我认为这是什么使得recursion可能第一。

避免复制（1）和“模仿堆栈”（2），我们是否certificate每个recursionalgorithm都可以在真实机器上迭代表示？！ 我看不到我们在哪里展示它。