一个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))
Ian.. 175
你总是可以将递归函数转换为迭代函数吗？是的,绝对,教会 - 图灵论文证明了记忆是否适用.在非专业术语中,它指出通过递归函数可计算的内容可由迭代模型(例如图灵机)计算,反之亦然.论文并没有准确地告诉你如何进行转换,但确实说这绝对是可能的.
在许多情况下,转换递归函数很容易.Knuth在"计算机编程艺术"中提供了几种技术.通常,递归计算的事物可以通过完全不同的方法在更短的时间和空间内计算.这方面的典型例子是斐波纳契数或其序列.你肯定在学位计划中遇到了这个问题.
在这个硬币的另一面,我们当然可以想象一个编程系统如此先进,以便将公式的递归定义视为回忆先前结果的邀请,从而提供速度效益,而无需告诉计算机确切的步骤到哪个步骤的麻烦按照递归定义计算公式.Dijkstra几乎肯定想象过这样一个系统.他花了很长时间试图将实现与编程语言的语义分开.然后,他的非确定性和多处理编程语言在练习专业程序员之上.
归根结底,许多函数更容易理解,读取和以递归形式写入.除非有令人信服的理由,否则您可能不应(手动)将这些函数转换为显式迭代算法.您的计算机将正确处理该作业.
我可以看到一个令人信服的理由.假设你有一个超级高级语言的原型系统,如[ 穿石棉内衣 ] Scheme,Lisp,Haskell,OCaml,Perl或Pascal.假设您需要使用C或Java实现的条件.(也许这是政治.)然后你肯定会有一些递归编写的函数,但字面上翻译会爆炸你的运行时系统.例如,在Scheme中可以进行无限尾递归,但是相同的习惯用法会导致现有C环境出现问题.另一个例子是使用词法嵌套函数和静态范围,Pascal支持但C不支持.
在这种情况下,您可能会尝试克服对原始语言的政治抵制.你可能会发现自己重新实现了Lisp,就像在格林斯普(格言中)的第十条法则中那样.或者您可能只是找到一种完全不同的解决方案.但无论如何,肯定有办法.
你总是可以将递归函数转换为迭代函数吗？是的,绝对,教会 - 图灵论文证明了记忆是否适用.在非专业术语中,它指出通过递归函数可计算的内容可由迭代模型(例如图灵机)计算,反之亦然.论文并没有准确地告诉你如何进行转换,但确实说这绝对是可能的.
在许多情况下,转换递归函数很容易.Knuth在"计算机编程艺术"中提供了几种技术.通常,递归计算的事物可以通过完全不同的方法在更短的时间和空间内计算.这方面的典型例子是斐波纳契数或其序列.你肯定在学位计划中遇到了这个问题.
在这个硬币的另一面,我们当然可以想象一个编程系统如此先进,以便将公式的递归定义视为回忆先前结果的邀请,从而提供速度效益,而无需告诉计算机确切的步骤到哪个步骤的麻烦按照递归定义计算公式.Dijkstra几乎肯定想象过这样一个系统.他花了很长时间试图将实现与编程语言的语义分开.然后,他的非确定性和多处理编程语言在练习专业程序员之上.
归根结底,许多函数更容易理解,读取和以递归形式写入.除非有令人信服的理由,否则您可能不应(手动)将这些函数转换为显式迭代算法.您的计算机将正确处理该作业.
我可以看到一个令人信服的理由.假设你有一个超级高级语言的原型系统,如[ 穿石棉内衣 ] Scheme,Lisp,Haskell,OCaml,Perl或Pascal.假设您需要使用C或Java实现的条件.(也许这是政治.)然后你肯定会有一些递归编写的函数,但字面上翻译会爆炸你的运行时系统.例如,在Scheme中可以进行无限尾递归,但是相同的习惯用法会导致现有C环境出现问题.另一个例子是使用词法嵌套函数和静态范围,Pascal支持但C不支持.
在这种情况下,您可能会尝试克服对原始语言的政治抵制.你可能会发现自己重新实现了Lisp,就像在格林斯普(格言中)的第十条法则中那样.或者您可能只是找到一种完全不同的解决方案.但无论如何,肯定有办法.
是否总是可以为每个递归函数编写一个非递归形式？
是.一个简单的形式证明是,μ递归和非递归演算(如GOTO)都是图灵完备的.由于所有图灵完全计算在其表达能力方面都是严格等同的,因此所有递归函数都可以通过非递归图灵完全计算来实现.
不幸的是,我无法在网上找到GOTO的正式定义,所以这里有一个:
GOTO程序是在寄存器机器上执行的一系列命令P,使得P是以下之一:
HALT,停止执行
r = r + 1在哪里r注册
r = r – 1在哪里r注册
GOTO x哪里x是标签
IF r ? 0 GOTO x哪里r是任何注册,x是一个标签
标签,后跟上述任何命令.
但是,递归函数和非递归函数之间的转换并不总是微不足道的(除非通过无意识的手动重新实现调用堆栈).
有关详细信息,请参阅此答案.
递归在实际的解释器或编译器中实现为堆栈或类似的构造.所以你当然可以将递归函数转换为迭代对应函数,因为它总是如此(如果是自动的).你只是在ad-hoc中复制编译器的工作,可能是非常丑陋和低效的方式.
基本上是的,实质上你最不得不做的是将方法调用(隐式地将状态推入堆栈)替换为显式堆栈推送以记住"先前调用"已经到达的位置,然后执行"被调用的方法"代替.
我想通过基本模拟方法调用,可以将循环,堆栈和状态机的组合用于所有场景.一般来说,这是否会"更好"(在某种意义上更快或更有效)并不是真的可以说.
递归函数执行流可以表示为树.
循环可以完成相同的逻辑,循环使用数据结构遍历该树.
深度优先遍历可以使用堆栈完成,广度优先遍历可以使用队列完成.
所以,答案是:是的.原因:https://stackoverflow.com/a/531721/2128327.
任何递归都可以在一个循环中完成吗？是的,因为
图灵机通过执行单个循环来完成它所做的一切:
取指令,
评估它,
转到1.
是的,明确地使用堆栈(但是递归更令人愉快,恕我直言).
是的,总是可以写一个非递归版本.简单的解决方案是使用堆栈数据结构并模拟递归执行.
京公网安备 11010802040832号 | 京ICP备19059560号-6 