问题描述
每个具有迭代解决方案的问题是否也可以用递归解决方案的
表示？
我试过一个例子，我在尝试更多例子的过程，
随着时间的推移增加其复杂性。这是我尝试过的简单的一个：
#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.
推荐答案
肯定/可以/，如果这是必需的。
-
Richard Heathfield
Usenet是一个奇怪的地方 - dmr 29/7/1999
电子邮件：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)
什么状态？递归将保留返回值。在堆栈帧中，递归函数的每次迭代的
被保留为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
相反：迭代通过在递归时转换状态来工作
可以通过创建新的本地值来工作（同时保留全球
州）。这是价值导向（功能性）的本质。
编程：你永远不会破坏性地覆盖价值，你只需创建新的
新的，并且只在旧的时候重用空间他们是
保证不再使用。
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
这篇关于迭代与递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！