迭代与递归 [英] Iteration vs. Recursion

问题描述

每个具有迭代解决方案的问题是否也可以用递归解决方案的

表示？


我试过一个例子，我在尝试更多例子的过程，

随着时间的推移增加其复杂性。这是我尝试过的简单的一个：


#include< stdio.h>

/ *比较迭代的时间和空间成本

递归* /


const int SOME_CONST = 10;

无效ifoo（）;

void rfoo（int，int，int）;

int main（void）

{

ifoo（）;

rfoo（0,0,5）;

printf（" \ n"）;

返回0;

}


无效ifoo（）

{

int i = 0，x = 0，y = 5;

for（; i< SOME_CONST; i ++）

{

x + = y;

printf（"％d \ t％d \ t％d \ t \ n"，i，x，y）;

}

}

无效rfoo（int i，int x，int y）

{

x + = y;

printf（" \ n％d \\ \\ t％d \ t％d"，i，x，y）;


if（i< SOME_CONST - 1）

rfoo（+ + i，x，y）;

}

我注意到以下内容：


a。虽然迭代在时间上是线性的并且在空间上是常数，但递归

在空间中是指数的。


b。迭代保留状态，递归没有。

Can every problem that has an iterative solution also be expressed in
terms of a recursive solution?

I tried one example, and am in the process of trying out more examples,
increasing their complexity as I go. Here''s a simple one I tried out:

#include<stdio.h>
/* To compare the the time and space cost of iteration against
recursion*/

const int SOME_CONST = 10;
void ifoo();
void rfoo(int, int, int);
int main(void)
{
ifoo();
rfoo(0, 0, 5);
printf("\n");
return 0;
}

void ifoo()
{
int i = 0, x = 0, y = 5;
for(; i < SOME_CONST; i++)
{
x += y;
printf("%d\t%d\t%d\t\n", i, x, y);
}
}
void rfoo(int i, int x, int y)
{
x += y;
printf("\n%d\t%d\t%d", i, x, y);

if (i < SOME_CONST - 1)
rfoo(++i, x, y);
}
I noted the following:

a. While iteration is linear in time and constant in space, recursion
is exponential in space.

b. Iteration preserves state, recursion does not.

推荐答案

Sathyaish说：

Sathyaish said:

每个人都可以具有迭代解决方案的问题也可以用递归解决方案的术语表示？


是的。迭代和递归只是两种不同的方式来说如果我们还没有完成，那么就让我们做更多的事情。递归是

实现迭代的一种方式。迭代是实现递归的一种方式。


我注意到以下内容：

a。虽然迭代在时间上是线性的并且在空间中是恒定的，但递归
在空间中是指数的。


不一定。这取决于你在做什么以及你是如何做的。

b。迭代保留状态，递归不会。

Can every problem that has an iterative solution also be expressed in
terms of a recursive solution?
Yes. Iteration and recursion are just two different ways of saying "if we''re
not finished yet, let''s do it some more". Recursion is one way of
implementing iteration. Iteration is one way of implementing recursion.

I noted the following:

a. While iteration is linear in time and constant in space, recursion
is exponential in space.
Not necessarily. It depends what you''re doing and how you''re doing it.
b. Iteration preserves state, recursion does not.

肯定/可以/，如果这是必需的。

-

Richard Heathfield

Usenet是一个奇怪的地方 - dmr 29/7/1999
http://www.cpax.org.uk

电子邮件：rjh在上面的域名（但显然放弃了www）

It certainly /can/, if that is what is required.
--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

Sathyaish写道：

Sathyaish wrote:

具有迭代解决方案的每个问题是否也可以用递归解决方案的术语表示？


这两个词的基本含义很重要。
我尝试了一个例子，我正在尝试更多的例子，
增加他们的复杂性，因为我走。这是我尝试过的一个简单的例子：


你不能仅仅通过增加复杂性来测试一个假设。

＃include< stdio.h>

/ *比较迭代的时间和空间成本与
递归* /

const int SOME_CONST = 10;
void ifoo（）;
void rfoo（int，int，int）;

int main（void）
{
ifoo（）;
rfoo（0,0， 5）;
printf（" \ n"）;
返回0;
}

无效ifoo（）
{
int i = 0，x = 0，y = 5;
for（; i< SOME_CONST; i ++）
{
x + = y;
printf（"％） d \ t％d \ t％d \\ n"，i，x，y）;
}
}
void rfoo（int i， int x，int y）
{
x + = y;
printf（" \ n％d \ t％d \ t％d"，i，x，y ）;

if（i< SOME_CONST - 1）
rfoo（++ i，x，y）;
}


您已经展示了迭代的示例和递归的示例。只是

因为后者执行与前者相同并不意味着每个
迭代都可以表示为递归。


以下是不能表示为递归的迭代


printf（"％d"，rand（））;

printf（" ％d"，rand（））;

printf（"％d"，rand（））;

printf（"％d"，rand（）） ;

printf（"％d"，rand（））;

....

我注意到以下内容：

虽然迭代在时间上是线性的并且在空间中是恒定的，但递归在空间中是指数的。


以什么方式？太空是什么意思？电脑记忆？这个声明

似乎没有意义。


在一台
多任务计算机上，迭代过程不一定是线性的 - 这些日子大部分都是。


我认为你迷失了一件简单的事情。


b。迭代保留状态，递归不会。

Can every problem that has an iterative solution also be expressed in
terms of a recursive solution?
Matter of basic meaning of the two words.
I tried one example, and am in the process of trying out more examples,
increasing their complexity as I go. Here''s a simple one I tried out:
You can not test a hypothesis merely by increasing the complexity.

#include<stdio.h>
/* To compare the the time and space cost of iteration against
recursion*/

const int SOME_CONST = 10;
void ifoo();
void rfoo(int, int, int);
int main(void)
{
ifoo();
rfoo(0, 0, 5);
printf("\n");
return 0;
}

void ifoo()
{
int i = 0, x = 0, y = 5;
for(; i < SOME_CONST; i++)
{
x += y;
printf("%d\t%d\t%d\t\n", i, x, y);
}
}
void rfoo(int i, int x, int y)
{
x += y;
printf("\n%d\t%d\t%d", i, x, y);

if (i < SOME_CONST - 1)
rfoo(++i, x, y);
}

You have shown an example of an iteration and an example of recursion. Just
because the latter performs the same as the former does not mean that EVERY
iteration can be expressed as a recursion.

The following is an iteration that cannot be expressed as a recursion

printf("%d", rand());
printf("%d", rand());
printf("%d", rand());
printf("%d", rand());
printf("%d", rand());
....

I noted the following:

a. While iteration is linear in time and constant in space, recursion
is exponential in space.

In what way? What do you mean by space? Computer memory? This statement
would seem to be meaningless.

An iterated process would not necessarily be linear in time on a
multitasking computer - which most are these days.

I think you are getting lost over a simple matter.

b. Iteration preserves state, recursion does not.

什么状态？递归将保留返回值。在堆栈帧中，递归函数的每次迭代的
被保留为state状态。当时

的功能。这不是指数。


尝试简化这两个词的基本含义 -


"迭代：重复，状态反复（拉丁语：iterum - 再次）"


迭代是一个重复多次的过程，没有

必然会返回任何东西。

循环是迭代过程。但迭代不一定局限于循环 - 请参阅上面的例子。


递归：行为或返回的实例（拉丁文：recurrere - 再次运行

）简明牛津词典。


递归是一个自称的过程，即。返回自身。

A功能自称为递归。


单词的定义表明它们不是同义词 - 即。事情可能会重复，但不一定涉及任何返回的想法。


简单！


是真的有必要交叉吗？


艾伦

State of what? Recursion will preserve a return value. In the stack frame
of each iteration of a recursive function is preserved the "state" of the
function at that time. This would not be "exponential".

Try to simplify by going to the basic meaning of the two words -

"Iterate: repeat, state repeatedly (Latin: iterum - again)"

Iteration is a process that is repeated a number of times without
necessarily returning to anything.
Loops are iterative processes. But iteration is not necessarily confined
to loops - vide my example above.

"Recursion: the act or an instance of returning (Latin: recurrere - run
again)" Concise Oxford Dictionary.

Recursion is a process that calls itself, ie. returns to itself.
A "function" that calls itself is recursion.

The definition of the words show they are NOT synonymous - ie. things may be
repeated without necessarily involving any idea of "returning".

Simple!

Was it really necessary to cross post??

Alan

" Sathyaish" < SA ******* @ gmail.com>写道：

"Sathyaish" <sa*******@gmail.com> writes:

每个具有迭代解决方案的问题是否也可以用递归解决方案的术语表示？


是的。只有当你允许引入额外的变量（

无限大小）时，反过来才是真的，基本上模拟递归

堆栈。

我尝试了一个例子，我正在尝试更多的例子，
增加他们的复杂性。这是我尝试过的一个简单的方法：

＃include< stdio.h>

/ *比较迭代的时间和空间成本
递归* /

const int SOME_CONST = 10;
void ifoo（）;
void rfoo（int，int，int）;

int main （无效）
{
ifoo（）;
rfoo（0,0,5）;
printf（" \ n"）;
返回0;
}

void ifoo（）
{
int i = 0，x = 0，y = 5;
for（; i< SOME_CONST ; i ++）
{
x + = y;
printf（"％d \ t％d \ t％d \ t \ n"，i，x，y ）;
}
}
void rfoo（int i，int x，int y）
{
x + = y;
printf（" \ n％d \ t％d \ t％d"，i，x，y）;

if（i< SOME_CONST - 1）
rfoo （++ i，x，y）;
}

我注意到以下内容：

a。虽然迭代在时间上是线性的并且在空间中是恒定的，但递归
在空间中是指数的。


你是如何得出这个结论的？你的rfoo函数将在C / /
中使用空间线性的recursice调用次数，但即便如此，因为你的C编译器没有进行尾递归优化

（任何明智的编译器都会），这将使上面的内容在

恒定空间中运行。

b。迭代保留状态，递归不会。

Can every problem that has an iterative solution also be expressed in
terms of a recursive solution?
Yes. The converse is true only if you allow extra variables (of
unbounded size) to be introduced, essentially emulating a recursion
stack.
I tried one example, and am in the process of trying out more examples,
increasing their complexity as I go. Here''s a simple one I tried out:

#include<stdio.h>
/* To compare the the time and space cost of iteration against
recursion*/

const int SOME_CONST = 10;
void ifoo();
void rfoo(int, int, int);
int main(void)
{
ifoo();
rfoo(0, 0, 5);
printf("\n");
return 0;
}

void ifoo()
{
int i = 0, x = 0, y = 5;
for(; i < SOME_CONST; i++)
{
x += y;
printf("%d\t%d\t%d\t\n", i, x, y);
}
}
void rfoo(int i, int x, int y)
{
x += y;
printf("\n%d\t%d\t%d", i, x, y);

if (i < SOME_CONST - 1)
rfoo(++i, x, y);
}
I noted the following:

a. While iteration is linear in time and constant in space, recursion
is exponential in space.
How did you arive at that conclusion? Your rfoo function will in C
use space linear in the number of recursice calls, but even that is
only because your C compiler doesn''t do tail-recursion optimisation
(which any sensible compiler will), which would make the above run in
constant space.
b. Iteration preserves state, recursion does not.

相反：迭代通过在递归时转换状态来工作

可以通过创建新的本地值来工作（同时保留全球

州）。这是价值导向（功能性）的本质。
编程：你永远不会破坏性地覆盖价值，你只需创建新的
新的，并且只在旧的时候重用空间他们是

保证不再使用。


Torben

On the contrary: Iteration works by transforming state while recursion
can work by creating new local values (while preserving the global
state). That is the essense of value-oriented (functional)
programming: You never destructively overwrite values, you just create
new ones and reuse the space for the old ones only when they are
guarateed not to be used anymore.

Torben

这篇关于迭代与递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！