Iteration vs. Recursion

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

> 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.

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{}> writes:

> 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.

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

Sathyaish wrote:

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

> 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.

certainly not in the case of backtracking algorithms.

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

[ snipped ]

> I noted the following:
>
> a. While iteration is linear in time and constant in space, recursion
> is exponential in space.


Two remarks:

1. You can read all about recursion in my Computing Prescriptions
column in Computing in Science and Engineering (May/June 2003,
pp. 76-81 (a color version may be found at

http://galileo.phys.virginia.edu/cla...l01/Cprogs.htm


2. Assuming recursion employs a stack, the growth of memory usage
with problem size is logarithmic, not exponential, unless you
are using recursion in a foolish context (to compute Fibonacci
numbers or the like).


--
Julian V. Noble
Professor Emeritus of Physics
University of Virginia

"Julian V. Noble" <jvn{}virginia.edu> writes:


> Two remarks:
>
> 1. You can read all about recursion in my Computing Prescriptions
> column in Computing in Science and Engineering (May/June 2003,
> pp. 76-81 (a color version may be found at
>
> http://galileo.phys.virginia.edu/cla...l01/Cprogs.htm

Hardly _all_ about recursion. :-)

> 2. Assuming recursion employs a stack, the growth of memory usage
> with problem size is logarithmic, not exponential, unless you
> are using recursion in a foolish context (to compute Fibonacci
> numbers or the like).

That is a very imprecise statement. The largest number of stack
frames that are active at any one point can be anywhere between
constant to linear in the total number of recursive calls, but the
number of recursive calls does not need to be linear in the problem
size (as measured by the input size). For example, the recursive
solution to The Towers of Hanoi for N disks uses 2^N-1 calls but stack
depth only N. Additionally, the size of each stack frame may depend
on the input size, so the total space used can be larger than linear
in the number of calls.

Torben

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

Iterative constructions can be easily transformed into recursive ones.
Some recursive constructs cannot be transformed into iterative without
additional variables to simulate the stack.

--
SM Ryan http://www.rawbw.com/~wyrmwif/
We found a loophole; they can't keep us out anymore.

>
> 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.

Missing Basic Stuff,
Question why it would require more time (then linear)?
why required more space ? (coz to preserve the state on stake )

Simple ex. fibonacci

fib(1) = fib(2) = 1
fib(n) = fib(n-1)+fib(n-2), if n>2

for fib(6)=fib(5)+fib(4)=[fib(4)+fib(3)] + [fib(3)+fib(2)] =-........


the basic thing is that fib(3) is calculated two times above.
Normally (not always) recursive one is slow(compare to linear) and/or
would require (more space) because
1. repeated computation done. (as in ex. fib(3) called twice,
2. and same result is stored more than once.

Before using recursive fun. Estimate how much space/time it would take
extra, ?
that is the best way to decide recursive is usable in particular case
or not ?

--
Raxit Sheth

raxitsheth{} said:

> Simple ex. fibonacci
>
> fib(1) = fib(2) = 1
> fib(n) = fib(n-1)+fib(n-2), if n>2
>
> for fib(6)=fib(5)+fib(4)=[fib(4)+fib(3)] + [fib(3)+fib(2)] =-........
>
>
> the basic thing is that fib(3) is calculated two times above.
> Normally (not always) recursive one is slow(compare to linear) and/or
> would require (more space) because
> 1. repeated computation done. (as in ex. fib(3) called twice,
> 2. and same result is stored more than once.

Exercise for the reader: write an iterative version of fib() that is even
less efficient than the recursive version explained above, and use it to
prove that iteration is slow (compared to recursion) and would require more
space.

Exercise for the undergraduate student (or bright 12-year-old): write a
version that calculates fib() without iterating or recursing, thus proving
that both iteration and recursion require unnecessary amounts of space and
time.

Exercise for the post-graduate student: make the non-iterative non-recursive
version less efficient than the least efficient of the versions so far
discussed, thus proving that both iteration and recursion are massively
superior to O(1) techniques.

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