c++ - 请问循环能代替所有递归吗？

Question

之所以会有这种想法，基于两个理由：

递归本质上是在进行压栈操作，人脑不易理解，尽管很多人都在尝试，相比之下，循环就容易理解多了。

这有一篇文章深入地介绍了递归，http://blog.csdn.net/theknotyouknow/article/details/24435291
循环执行效率比递归高很多。

在知乎上搜了一下，感觉回答的并不是很好，还请各位不吝赐教。

怪我咯 · Answer

能。大学计科有讲这个的。而且反过来也成立。

你想啊，递归调用就是把参数压栈。改成循环，我手动建个栈，每次循环把需要的数据压进去，循环完弹出来不就可以了么。

递归 vs 循环：

人脑不易理解？你看看著名的斐波那契数列的递归定义，写成递归容易还是循环容易？哪个容易理解取决于你的问题的解是怎么表述的。如果你是解的提出者怎么办？习惯了哪个你肯定会自然而然地用哪个。循环在编程界一直是大多数，所以嘛，你明白了？
普通递归总是要压栈的。递归的层数多了，栈就要爆了。怎么办呢，有一种叫尾递归的优化，也叫尾调用。就是每次到返回前的最后一步才进行递归调用，这样的情况就可以保持栈不随着递归过程一直增长。不仅高效，还直观。但是很多问题的尾递归解本身不直观。

高洛峰 · Answer

当然能。

所谓递归无非就是函数（直接或间接）调用自己，所以我们先看一下简单的函数调用。
假设有一个函数长这样：

int foo() {
  int X = 4
  int Y = bar(14);
  return X*Y;
}

你可以把它变成这样：

int foo() {
  foo_stack_frame = gcalloc { X: int; Y: int }
  foo_stack_frame->X = 4;
  foo_stack_frame->Y = bar(14);
  return foo_stack_frame->X * foo_stack_frame->Y;
}

其中gcalloc就是指从GC heap上分配一个什么东西，这里分配的是一个map，用于保存foo的stack frame。
然后，foo可以变成这样：

int foo(continuation C) {
  foo_stack_frame = gcalloc { C: continuation; X: int; Y: int }
  foo_stack_frame->C = C;
  foo_stack_frame->X = 4;
  continuation Next = { foo2, foo_stack_frame };
  return bar(Next, 14);
}

int foo2(continuation C, int Y) {
  foo_stack_frame = C->stack_frame;
  foo_stack_frame->Y = Y;
  continuation Next = foo_stack_frame->C;
  return Next->F(Next, foo_stack_frame->X * foo_stack_frame->Y);
}

这里的continuation你可以认为就是一个“返回地址”，这个等下再说。
你很可能会问，这么一大堆变换到底是在干神马？
嗯，其实这一堆就只变换干了一件事，那就是——把所有的函数调用变成了tail call。
大家都知道，tail call是可以直接优化成goto的，所以我们必须记录下原本的返回地址，把它传递给被tail call的函数，这样它就可以在结束的时候直接返回到最初的调用者那里。
如果对每个函数都做这样的变换，让每个函数调用都是tail call，那我们就彻底干掉了stack，整个程序只用goto就搞定。

PS. 对上面内容有兴趣的童鞋可以去看看 http://en.wikipedia.org/wiki/Continuation-passing_style
PPS. 其实从“理解”这个角度而言，递归往往更容易更清晰，因为它天生就是一个把高复杂度问题分解为低复杂度的过程。

天蓬老师 · Answer

所有递归都能写成尾递归吗？
所有尾递归都能写成循环吗？

如果上面两个问题的答案都是yes，那么就获得了一种构造证明方法。

怪我咯 · Answer

通过栈，所有递归都能变成循环。高级语言只是把语言级别的递归变成实现级别的栈。这个问题在网上有很详细的论文。用google搜recursion iteration会发现相当多的答案。
用栈来实现将递归变成循环并不能带来性能的优化，在同种语言的条件下比较更可能带来性能的损失。
有的递归不需要增加栈。去掉了栈和栈操作可以带来速度和空间两方面的效率提升。这其中的一类叫尾递归，有的语言实现了尾递归优化，也就是自动将尾递归变成循环同时不增加栈。比如lisp，scheme，haskell等很多语言都实现了这种优化，但是大多数动态语言包括python，javascript，ruby都没有，因此这些语言经常会报告递归函数超过最大栈深度的错误。
我正在做的一个语言，其中一个特性是在支持尾递归的优化的同时还要支持某些非尾递归的优化，将递归函数转换成不用栈的循环（当然只是一部分，因为不用栈是不可能将所有函数转换成循环的）。
比如sum = (x) -> if x=0 then return 0 else return x+f(x-1)
这个函数是非尾递归的，因为在递归调用函数之后还做了加法。
转换成尾递归是这种形式：sum = (x, acc) -> if x=0 then return acc else return f(x-1, acc)
现在的某些语言将自动把后面这种函数变成循环，同时栈不增加。也就是类似如下的代码
sum = (x, acc) -> while 1 if x=0 then return acc else acc += x
我做的语言将自动把非尾递归的版本变成如下的循环：
sum = (x) -> sum = 0; while 1 then if x=0 then return sum else x--; f += x
补充说明一点: 我这里提供的并不是伪代码，全部都是我将发布的语言中的合法代码。

大家讲道理 · Answer

不僅loop能夠代替recursion, 而且還可以根據recursion的公式,直接推倒Genrating Function求值.
比如說Fibonacci, f(n)=f(n-1)+f(n-2),他的closed form就是 F(n) = n / (1-n-n^2)

參考:
http://en.wikipedia.org/wiki/Fibonacci_number
http://www.austinrochford.com/posts/2013-11-01-generating-functions-and-fibonacci-numbers.html
http://www.math.cmu.edu/~af1p/Teaching/Combinatorics/Slides/Generating-Functions.pdf