iterativ vs rekursiv

Thread view:

Dennis Dahn - 26 Jan 2007 20:43 GMT

Hello,

I have a general question, is it possible to turn every rekursiv algorithm
into an iterativ one?

for example this one:

static boolean solve(int i, int j, int[][] cells) {
if (i == 9) {
i = 0;
if (++j == 9)
return true;
}
if (cells[i][j] != 0) // skip filled cells
return solve(i+1,j,cells);
<- here is the rekursiv call

for (int val = 1; val <= 9; ++val) {
if (legal(i,j,val,cells)) {
cells[i][j] = val;
if (solve(i+1,j,cells))
<- and here!
return true;
}
}
cells[i][j] = 0; // reset on backtrack
return false;
}

thank you very much for your help!

regards,

dennis

Reply to this Message

Stefan Z Camilleri - 26 Jan 2007 21:40 GMT

> Hello,
>
[quoted text clipped - 31 lines]
>
> dennis

Hi Dennis

Well given the premise that a Turing Powerful language can perform any
algorithm as any other paradigm, then it follows that recursion algorithms
can be made iterative.

Furthermore, once your code is compiled and linked, it become assembly,
and there is no native support for recursion in assembly, just loops.

Now, given that for recursion to exist all that is needed is a stack adt,
then you can convert ANY recursive algorithm into iterative, given that
you have a stack structure available or else you implement one yourself...
the opposite doesn't necesarily apply.

Hope I've answered your question

Signature

- Stefan Z Camilleri
- www.szc001.com

Reply to this Message

Oliver Wong - 01 Feb 2007 20:53 GMT

> Now, given that for recursion to exist all that is needed is a stack adt,
> then you can convert ANY recursive algorithm into iterative, given that
> you have a stack structure available or else you implement one yourself...
> the opposite doesn't necesarily apply.

Depending on how strict your definition of recursion is, you can take any
iterative algorithm:

label: {
...
...
...
}

And turn it into a recursive one as:

public void recursiveFunction(boolean isBaseCase) {
if (isBaseCase) {
label: {
...
...
...
}
} else {
recursiveFunction(!isBaseCase);
}
}

- Oliver

Reply to this Message

Chris Dollin - 29 Jan 2007 09:01 GMT

> Hello,
>
> I have a general question, is it possible to turn every rekursiv algorithm
> into an iterativ one?

Yes, if you allow the introduction of additional data structures
(specifically, the moral equivalent of a stack).

Some recursive functions can be simply turned into stack-free iterations.
Some recursive functions can be transformed into recursive functions
of that kind (and hence into stack-free iterations).
Some will need a stack.

Signature

Chris "electric hedgehog" Dollin
"- born in the lab under strict supervision -", - Magenta, /Genetesis/

Reply to this Message

iterativ vs rekursiv

Free Magazines