每个递归都可以转化为迭代吗?
-
06-09-2019 - |
题
A 红迪帖子 提出了一个显然很有趣的问题:
尾递归函数可以简单地转换为迭代函数。其他的,可以通过使用显式堆栈进行转换。能 每一个 递归转化为迭代?
帖子中的(反?)示例是一对:
(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))
解决方案
你能随时打开一个递归函数到迭代一个?是的,绝对,和教会图灵论题如果没有记错证明了这一点。在捻术语,它指出什么是可计算通过递归函数是通过迭代模型(如图灵机)可计算并且反之亦然。本文不准确地告诉你该怎么做转换,但它说,这是绝对有可能。
在许多情况下,转换一个递归函数是容易的。克努特提供了“计算机程序设计艺术”的技术。而往往,递归计算的东西可以在更短的时间和空间上完全不同的方法计算。这样做的典型的例子是斐波那契数或其序列。你一定在你的学位计划遇到了这个问题。
在该硬币的另一面,我们可以肯定想象一个编程系统如此先进作为治疗式的递归定义作为邀请memoize的先前结果,从而提供速度益处,而不准确告诉计算机的麻烦其中步骤与递归定义的公式的计算遵循。 Dijkstra算法几乎肯定没有想象这样的系统。他花了很长时间试图分开编程语言的语义的实现。话又说回来,他的不确定性和多编程语言在上述执业专业程序员联盟。
在最后的分析中,许多功能都仅仅是容易理解,阅读和在递归形式写。除非有令人信服的理由,你可能不应该(手动)转换这些功能来显式迭代算法。您的计算机将正确处理工作。
我可以看到一个令人信服的理由。假设你在这样一个超高级语言已经原型系统[穿上石棉内衣的]计划,Lisp语言,哈斯克尔,OCaml中,Perl或帕斯卡。假设条件是这样的,你需要在C或Java的实现。 (也许是政治的。)然后,你可以肯定递归编写的,但其中的一些功能,直译,会爆炸的运行系统。例如,无限大尾递归是可能的方案,但相同的成语引起问题为现有的C环境。另一个例子是使用的词汇嵌套函数和静态范围,该范围Pascal支持但C不
在这种情况下,你可以尝试克服原始语言的政治阻力。你可能会发现自己重新实现Lisp的厉害,在Greenspun的(舌头在脸颊)第十法。或者,你可能会发现一个完全不同的方法来解决。但在任何情况下,有肯定的一种方式。
其他提示
是否总是可以为每个递归函数编写非递归形式?
是的。一个简单的形式化证明就是证明两者 µ 递归 诸如 GOTO 之类的非递归微积分都是图灵完备的。由于所有图灵完备演算在表达能力上都是严格等价的,因此所有递归函数都可以通过非递归图灵完备演算来实现。
不幸的是,我无法在网上找到 GOTO 的良好、正式的定义,所以这里有一个:
GOTO 程序是一个命令序列 磷 执行于 登记机 这样 磷 是以下之一:
HALT
, ,这会停止执行r = r + 1
在哪里r
是任意寄存器吗r = r – 1
在哪里r
是任意寄存器吗GOTO X
在哪里X
是一个标签IF r ≠ 0 GOTO X
在哪里r
是任意寄存器并且X
是一个标签- 一个标签,后跟任何上述命令。
然而,递归函数和非递归函数之间的转换并不总是微不足道的(除非不经意地手动重新实现调用堆栈)。
欲了解更多信息,请参阅 这个答案.
递归被实现为在实际解释编译器或堆叠或类似的构造。所以,你当然可以递归函数转换为一个迭代对应的,因为这是它是如何经常做(如果自动)。您只是在复制编译器的工作在一个特设的,可能在一个非常丑陋和低效的方式。
基本上是的,在本质上你最终不得不做的是替换方法调用(含蓄地按压状态到堆栈中)为显性堆栈推向记得那里的“以前调用”已经得到了到,然后执行“调用方法”来代替。
我想像,一个环路,一个堆栈和一个状态机的组合可以由基本上模拟方法调用被用于所有的场景。这是否将是“好”(或更快,或者在某种意义上更有效)是不是真的有可能在一般的说。
递归函数的执行流程可以用树来表示。
相同的逻辑可以通过循环来完成,它使用数据结构来遍历该树。
深度优先遍历可以使用栈来完成,广度优先遍历可以使用队列来完成。
所以,答案是:是的。为什么: https://stackoverflow.com/a/531721/2128327.
任何递归都可以在单个循环中完成吗?是的,因为
图灵机通过执行单个循环来完成它所做的一切:
- 获取指令,
- 评价一下,
- 转到 1。
是的,它总是可以写一个非递归版本。平凡解是使用一个堆栈数据结构和模拟递归执行。
是,使用显式的堆叠(但递归是更为愉快阅读,IMHO)。
在原则上总是能够去除递归和在具有两个用于数据结构和调用堆栈无限状态的语言与迭代替换它。这是教会-图灵论题的基本结果。
由于实际的编程语言,答案就没有那么明显。的问题是,它是完全可能有一个语言,其中,可以在程序中分配的存储器的量是有限的,但是在那里可以使用的调用堆栈的量是无界的(32位C,其中堆栈变量的地址不可访问)。在这种情况下,递归是更强大,只是因为它有更多的内存可以使用;没有足够明确地分配内存来模拟调用堆栈。有关此的详细论述,请参见这讨论。
有时代替递归比容易得多。递归使用是在1990年的在CS教导时髦的东西,所以有很多从那个时候平均开发商想如果你解决了一些与递归,这是一个更好的解决方案。因此,他们会用递归代替循环向后扭转秩序,或愚蠢之类的东西。所以有时除去递归是一个简单的“咄,这是明显的”运动类型。
这是一个问题较少的现在,作为时尚已经朝向其他技术偏移。
所有可计算函数可以通过图灵机来计算,因此递归系统和图灵机(迭代系统)是等价的。
Appart酒店从显式堆,用于转换成递归迭代另一模式是通过使用一个蹦床的。
在此,函数要么返回最终的结果,或者它本来会执行的函数调用的封闭。然后,发起(蹦床)函数保持调用封闭返回,直到达到最终的结果。
该方法适用于相互递归函数,但恐怕它仅适用于尾调用。
我会说是的 - 函数调用只不过是一个GOTO和出栈操作(粗略地讲)。所有你需要做的是模仿,而调用函数和做一个跳转(您可以模仿与语言goto的不明确有这个关键字太)类似的东西是建立在堆栈中。
是可能的任何递归算法转换成非递归 一个,但往往逻辑更加复杂,这样做需要 使用的堆叠的。事实上,递归本身使用堆栈:在 功能叠层。
更多详细信息: https://developer.mozilla.org / EN-US /文档/网络/的JavaScript /指南/功能
tazzego,递归是指函数将调用本身不管你喜欢还是不喜欢。当人们都在谈论与否的东西可以不递归做了,他们的意思是这样,你不能说“不,这不是真的,因为我不使用递归的定义达成一致”作为一个有效的声明。
考虑到这一点,只是一切你说的是废话。你说是不是废话唯一的另一件事是,你不能没有一个调用堆栈想象编程的想法。这是什么,已经做了几十年,直到使用调用堆栈走红。 FORTRAN的旧版本缺乏调用堆栈和他们的工作就好了。
顺便提及,存在图灵完全语言仅实现递归(例如SML)作为循环的手段。还存在图灵完全语言仅实现迭代循环为(例如FORTRAN IV)的一种手段。教会 - 图灵论题证明,任何可能在一个只有递归的语言可以在非递归语言和VICA,反之亦然的事实,它们都具有图灵完备的财产来完成。
下面是一种迭代算法:
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