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

Question

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

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

   这有一篇文章深入地介绍了递归，http://blog.csdn.net/theknotyouknow/article/details/24435291

2. 循环执行效率比递归高很多。

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

Answer 1

Yes. The accounting department at the university teaches this. And the reverse is also true.

If you think about it, recursive calls just push parameters onto the stack. To change it to a loop, I manually build a stack, push the required data into it each time it loops, and then pop it out after the loop, right?

Recursion vs loop:

1. Is it difficult for the human brain to understand? Look at the recursive definition of the famous Fibonacci sequence. Is it easier to write it as recursive or cyclic? Which one is easier to understand depends on how the solution to your problem is formulated. What if you were the one who proposed the solution? Once you get used to whichever one you will naturally use. Loops have always been the majority in the programming world, so, you get it?
2. Normal recursion always requires pushing on the stack. If there are too many levels of recursion, the stack will explode. What to do? There is an optimization called tail recursion, also called tail call. That is, the recursive call is made only at the last step before returning. In this case, the stack can be kept from growing along with the recursive process. Not only is it efficient, it’s also intuitive. But the tail-recursive solutions to many problems are not intuitive.

Answer 2

Of course you can.

The so-called recursion is nothing more than a function calling itself (directly or indirectly), so let’s look at simple function calls first.
Suppose there is a function that looks like this:

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

You can change it like this:

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;
}

Where gcalloc refers to allocating something from the GC heap. What is allocated here is a map used to save the stack frame of foo.
Then, foo can become like this:

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);
}

You can think of continuation here as a "return address". We will talk about this later.
You may well ask, what is the point of such a large number of transformations?
Well, in fact, this bunch of transformations only do one thing, and that is-turn all function calls into tail calls.
As we all know, tail call can be directly optimized into goto, so we must record the original return address and pass it to the function called by tail, so that it can return directly to the original caller when it ends. .
If we make this transformation for each function so that each function call is a tail call, then we will completely eliminate the stack and the entire program can be completed using only goto.

PS. Children’s shoes who are interested in the above content can check out http://en.wikipedia.org/wiki/Continuation-passing_style
PPS. In fact, from the perspective of "understanding", recursion is often easier and clearer, because it is inherently a process of decomposing high-complexity problems into low-complexity ones.

Answer 3

1. Can all recursion be written as tail recursion?
2. Can all tail recursion be written as a loop?

If the answer to the above two questions is yes, then a construction proof method is obtained.

Answer 4

With the stack, all recursions can be turned into loops. High-level languages ​​just turn language-level recursion into implementation-level stacks. There are very detailed papers on this issue online. If you search for recursion iteration on Google, you will find quite a few answers.
Using the stack to realize turning recursion into a loop does not bring performance optimization, and it is more likely to cause performance losses when compared under the conditions of the same language.
Some recursions do not require increasing the stack. Removing the stack and stack operations can bring efficiency improvements in both speed and space. One type of this is called tail recursion. Some languages ​​implement tail recursion optimization, which automatically turns tail recursion into a loop without increasing the stack. For example, many languages ​​such as lisp, scheme, and haskell have implemented this optimization, but most dynamic languages ​​including python, javascript, and ruby ​​do not. Therefore, these languages ​​​​often report errors in which recursive functions exceed the maximum stack depth.
One of the features of a language I'm working on is that it not only supports tail-recursive optimization but also supports some non-tail-recursive optimization, converting recursive functions into loops without stacks (of course only part of it, because it's impossible without stacks). Convert all functions to loops).
For example, sum = (x) -> if x=0 then return 0 else return x+f(x-1)
This function is non-tail recursive because addition is done after the recursive call to the function.
The conversion to tail recursion is this form: sum = (x, acc) -> if x=0 then return acc else return f(x-1, acc)
Some current languages ​​will automatically turn the latter function into a loop without increasing the stack. That is code similar to the following
sum = (x, acc) -> while 1 if x=0 then return acc else acc += x
The language I'm making will automatically turn the non-tail recursive version into a loop like this:
sum = (x) -> sum = 0; while 1 then if x=0 then return sum else x--; f += x
One additional note: What I provide here is not pseudocode, it is all legal code in the language I will publish.

Answer 5

Not only can loop replace recursion, but it can also directly overturn the Genrating Function evaluation based on the formula of recursion.
For example, Fibonacci, f(n)=f(n-1)+f(n-2), its closed form is F(n) = n / (1-n-n^2)

Reference:
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

Answer 6

Don’t you think recursion is more like a mathematical formula? f(n)=f(n-1)+f(n-2)
It may not be easy to understand if it is written as a loop

Answer 7

Theoretically it works. However, it is more important that the code is easy to understand

Answer 8

Recursion is an algorithm with a very slow execution speed. My personal suggestion is to use recursion as much as possible without recursion.
For example: f(n)=f(n-1)+f(n-2)
When n=100, the program can no longer run, or even larger. . .
You can try it

Answer 9

Let’s write recursion as a loop, and the function expression needs to be written in the form of f(x)=x的多项式. Simple recursion is fine, but complex recursion is quite laborious to simplify, and it is beyond the capabilities of programmers.

Answer 10

PHP recursion has a depth limit