Iteration vs. Recursion

[Sathyaish]

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]

Re: Iteration vs. Recursion

Sathyaish said:
[color=blue]
> Can every problem that has an iterative solution also be expressed in
> terms of a recursive solution?[/color]

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.

[color=blue]
> I noted the following:
>
> a. While iteration is linear in time and constant in space, recursion
> is exponential in space.[/color]

Not necessarily. It depends what you're doing and how you're doing it.
[color=blue]
> b. Iteration preserves state, recursion does not.[/color]

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)

[Alan]

Re: Iteration vs. Recursion

Sathyaish wrote:
[color=blue]
> Can every problem that has an iterative solution also be expressed in
> terms of a recursive solution?[/color]

Matter of basic meaning of the two words.[color=blue]
>
> 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:[/color]

You can not test a hypothesis merely by increasing the complexity.
[color=blue]
>
> #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);
> }
>[/color]

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());
....
[color=blue]
>
> I noted the following:
>
> a. While iteration is linear in time and constant in space, recursion
> is exponential in space.
>[/color]

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.

[color=blue]
> b. Iteration preserves state, recursion does not.[/color]

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 "exponentia l".

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 Ægidius Mogensen]

Re: Iteration vs. Recursion

"Sathyaish" <sathyaish@gmai l.com> writes:
[color=blue]
> Can every problem that has an iterative solution also be expressed in
> terms of a recursive solution?[/color]

Yes. The converse is true only if you allow extra variables (of
unbounded size) to be introduced, essentially emulating a recursion
stack.
[color=blue]
> 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.[/color]

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.
[color=blue]
> b. Iteration preserves state, recursion does not.[/color]

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

[Richard Heathfield]

Re: Iteration vs. Recursion

[clc restored]

Alan said:
[color=blue]
> 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());
> ....[/color]

void pewtinace(int i) /* Please Explain Why This Is Not A Counter-Example */
{
if(i > 0)
{
pewtinace(i - 1);
printf("%d", rand());
}
}

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

[amaldev.manuel@gmail.com]

Re: Iteration vs. Recursion

> I noted the following:[color=blue]
>
> a. While iteration is linear in time and constant in space, recursion
> is exponential in space.
>
> b. Iteration preserves state, recursion does not.[/color]

certainly not in the case of backtracking algorithms.

[Julian V. Noble]

Re: Iteration vs. Recursion

Sathyaish wrote:[color=blue]
> Can every problem that has an iterative solution also be expressed in
> terms of a recursive solution?
>[/color]

[ snipped ]
[color=blue]
> I noted the following:
>
> a. While iteration is linear in time and constant in space, recursion
> is exponential in space.[/color]


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/classes/551.jvn.fall01/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

[Torben Ægidius Mogensen]

Re: Iteration vs. Recursion

"Julian V. Noble" <jvn@virginia.e du> writes:

[color=blue]
> 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[/color]

Hardly _all_ about recursion. :-)
[color=blue]
> 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).[/color]

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

[SM Ryan]

Re: Iteration vs. Recursion

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

[raxitsheth@gmail.com]

Re: Iteration vs. Recursion

[color=blue]
>
> 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.[/color]

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)+f ib(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

[Richard Heathfield]

Re: Iteration vs. Recursion

raxitsheth@gmai l.com said:
[color=blue]
> Simple ex. fibonacci
>
> fib(1) = fib(2) = 1
> fib(n) = fib(n-1)+fib(n-2), if n>2
>
> for fib(6)=fib(5)+f ib(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.[/color]

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)

[Alf P. Steinbach]

Re: Iteration vs. Recursion

* Richard Heathfield:[color=blue]
> raxitsheth@gmai l.com said:
>[color=green]
>> Simple ex. fibonacci
>>
>> fib(1) = fib(2) = 1
>> fib(n) = fib(n-1)+fib(n-2), if n>2
>>
>> for fib(6)=fib(5)+f ib(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.[/color]
>
> 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.[/color]

The last one stumps me.

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

[Torben Ægidius Mogensen]

Re: Iteration vs. Recursion

raxitsheth@gmai l.com writes:
[color=blue][color=green]
> >
> > 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.[/color]
>
> 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)+f ib(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 ?[/color]

As Richard Heathfield said, this is not a question of recursion versus
iteration, but a question of using different algorithms. You are not
the only one making this mistake, though. I remember a special issue
of BYTE magazine from 1988 on benchmarks, where the author of an
article on Pascal benchmarks used the naive fibonacci function above
as a benchmark for function calls. The author then thought it would
be neat to compare the running time to a non-recursive implementation
and was flabbergasted by the large difference, concluding that
function calls must be very expensive indeed.

If your iterative fibonacci is

a := 0;
b := 1;
for i:=0 to n do begin
t := a;
a := b;
b := t+b
end;
writeln(b)

then the recursive version you should compare with is:

fib n = fib1 (n,0,1)

fib1 (0,a,b) = b
fib1 (n,a,b) = fib1 (n-1,b,a+b)

which is simpler than the above (it doesn't need the temporary
variable t) and equally fast (assuming a sensible compiler).

Both of the above use O(n) steps to calculate fibonacci of n. The
recursive function below uses O(log(n)) steps. Try writing this
without recursion.

fibo n = fst (h n)

h 0 = (1,0)
h n | even n = (a^2+b^2,b*(2*a-b)) where (a,b) = h (n`div`2)
h n | odd n = (a*(2*b+a),a^2+ b^2) where (a,b) = h (n`div`2)

Note: It will be slower than the simple fib for small n.

Richard also hinted at an O(1) fibonacci function. He probably meant
(phi^n - (1-phi)^n)/sqrt(5), where phi = (sqrt(5)+1)/2. This is,
however, a bit misleading, as this is only O(1) if you can do
arbitrary precision arithmetic in constant time, which is a bit
doubtful. This is also to a lesser extent true for the simpler
versions, as the linear time is assuming that arithmetic operations on
arbitrary-size integers can be done in constant time.

Torben

[Jonathan Bartlett]

Re: Iteration vs. Recursion

You might be interested in an article I wrote for IBM DeveloperWorks on
recursive programming:

http://www-128.ibm.com/developerworks/linux/library/l-recurs.html

Jon
----
Learn to program using Linux assembly language

http://www.cafeshops.com/bartlettpublish.8640017

[Julian V. Noble]

Re: Iteration vs. Recursion

Jonathan Bartlett wrote:[color=blue]
> You might be interested in an article I wrote for IBM DeveloperWorks on
> recursive programming:
>
> http://www-128.ibm.com/developerwork.../l-recurs.html
>
> Jon
> ----
> Learn to program using Linux assembly language
> http://www.cafeshops.com/bartlettpublish.8640017[/color]

Nice article. I sent feedback. I don't agree that you should
keep variables constant throughout a program. That's what a
CONSTANT is for.

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