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]

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.

 

[=?iso-8859-1?q?Torben_=C6gidius_Mogensen?=]

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

 

[Alan]

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

 

[Richard Heathfield]

[clc restored]

Alan said:

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());
....

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

 

[amaldev.manuel]

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.

 

[Julian V. Noble]

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

 

[=?iso-8859-1?q?Torben_=C6gidius_Mogensen?=]

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

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

 

[SM Ryan]

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

 

[raxitsheth]

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 ?

 

[Richard Heathfield]

(e-mail address removed) 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.

 

[Alf P. Steinbach]

* Richard Heathfield:

(e-mail address removed) 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.

The last one stumps me.

 

[=?iso-8859-1?q?Torben_=C6gidius_Mogensen?=]

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 ?

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]

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

 

[Julian V. Noble]

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

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.

 

[James Dow Allen]

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

Not overly impressed with Comp Sci doctorates, eh?

James

 

[Richard Heathfield]

James Dow Allen said:

Not overly impressed with Comp Sci doctorates, eh?

When you've had to teach 'em to program, you don't tend to be too impressed
by the bits of paper that said they already could.

 

[blmblm]

James Dow Allen said:


When you've had to teach 'em to program, you don't tend to be too impressed
by the bits of paper that said they already could.

Point taken, but ....

Do PhD programs in CS even claim to be producing good programmers?
I mean, I can easily imagine legitimate dissertation research that
involves no programming at all, and while you could argue that the
degree program should include a breadth requirement that includes
programming skills, hm .... No, I don't think I would (argue that,
beyond a minimal level that I suspect would still leave the person
in a state in which you would have to "teach 'em to program").

 

[Ben Pfaff]

Do PhD programs in CS even claim to be producing good programmers?

That's not a claim here at Stanford, as far as I know.

 

[Richard Heathfield]

(e-mail address removed) said:

Point taken, but ....

Do PhD programs in CS even claim to be producing good programmers?

If CS grads at least knew a bit of CS, that would be a start.

(I accept that my sample set is probably statistically insignificant, but
they were *all* useless, and 100% is 100% in anybody's language!)