iterativ vs rekursiv

[Dennis Dahn]

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[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[j] = val;
if (solve(i+1,j,cells))
<- and here!
return true;
}
}
cells[j] = 0; // reset on backtrack
return false;
}

thank you very much for your help!

regards,

dennis

 

[Stefan Z Camilleri]

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[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[j] = val;
if (solve(i+1,j,cells))
<- and here!
return true;
}
}
cells[j] = 0; // reset on backtrack
return false;
}

thank you very much for your help!

regards,

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

 

[Chris Dollin]

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.

 

[Oliver Wong]

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