How to write a nonrecursive program ?

[960392954]

The Towers of Hanoi is a famous problem about moving a certain number
of disks from one peg to another.I write a recursive program for it.If
you have known it ,you can skip the program.
#include <stdio.h>
void hanoi(int num,char initial,char terminal,char temporary);
void main (){
int num;/*num is the number of disks of the initial peg*/
char a='a',b='b',c='c';
/*a is the initial peg ,c is the terminal peg,b is used as a temporary
peg*/
printf("enter the number of disks:");
scanf("%d",&num);
hanoi(num,a,c,b);
}
void hanoi(int num,char initial,char terminal,char temporary){
if (num==1)
printf("%c==>%c\n",initial,terminal);
else{/*move the disks in a recrusive way*/
hanoi(num-1,initial,temporary,terminal);
printf("%c==>%c\n",initial,terminal);
hanoi(num-1,temporary,terminal,initial);
}
}
I can write a program with a recursive funcation easily.But many books
say that any program that can be implemented recursively can be
implemented iteratively.I don't know how to write a corresponding
iteratively.Could you tell me how to write a nonrecursive program that
have the same funcation with a recursive program
There are many exercises in my book about recursive programs.For most
of them,I find it is hard to write a corresponding iterative
program.Could you tell me what kind of books I need to read?
I am grateful for your help!

 

[user923005]

The Towers of Hanoi is a famous problem about moving a certain number
of disks from one peg to another.I write a recursive program for it.If
you have known it ,you can skip the program.
#include <stdio.h>
void hanoi(int num,char initial,char terminal,char temporary);
void main (){

From the C-FAQ:
1.25b: What's the right declaration for main()?
Is void main() correct?

A: See questions 11.12a through 11.15. (But no, it's not correct.)

        int num;/*num is the number of disks of the initial peg*/
        char a='a',b='b',c='c';
/*a is the initial peg ,c is the terminal peg,b is used as a temporary
peg*/
        printf("enter the number of disks:");
        scanf("%d",&num);
        hanoi(num,a,c,b);}

void hanoi(int num,char initial,char terminal,char temporary){
        if (num==1)
                printf("%c==>%c\n",initial,terminal);
        else{/*move the disks in a recrusive way*/
                hanoi(num-1,initial,temporary,terminal);
                printf("%c==>%c\n",initial,terminal);
                hanoi(num-1,temporary,terminal,initial);
        }}

I can write a program with a recursive funcation easily.But many books
say that any program that can be implemented recursively can be
implemented iteratively.I don't know how to write a corresponding
iteratively.Could you tell me how to write a nonrecursive program that
have the same funcation with a recursive program
There are many exercises in my book about recursive programs.For most
of them,I find it is hard to write a corresponding iterative
program.Could you tell me what kind of books I need to read?

You can convert iteration to recursion by managing your own stack. I
did a non-recursive quicksort that way a long time ago.

If it is only tail recursion, don't worry about it because the
compiler will probably rewrite it as iterative for you anyway.

You can program it directly, or write an abstract stack and push and
pop items.

 

[Harold Aptroot]

The Towers of Hanoi is a famous problem about moving a certain number
of disks from one peg to another.I write a recursive program for it.If
you have known it ,you can skip the program. (snipped)
I can write a program with a recursive funcation easily.But many books
say that any program that can be implemented recursively can be
implemented iteratively.I don't know how to write a corresponding
iteratively.Could you tell me how to write a nonrecursive program that
have the same funcation with a recursive program
There are many exercises in my book about recursive programs.For most
of them,I find it is hard to write a corresponding iterative
program.Could you tell me what kind of books I need to read?
I am grateful for your help!

In this particular case, wikipedia knows all:
http://en.wikipedia.org/wiki/Tower_of_Hanoi#Non-recursive_solution
As to other problems.. It often helps to try to think of a "bottom-up"
algorithm - often it won't be recursive anymore (but no guarantees here)
You could always cheat by emulating a stack in software, but it's cheating.

 

[Andrew Smallshaw]

I can write a program with a recursive funcation easily.But many books
say that any program that can be implemented recursively can be
implemented iteratively.I don't know how to write a corresponding
iteratively.Could you tell me how to write a nonrecursive program that
have the same funcation with a recursive program

Minor niggle - the program you wrote is not recursive in any case
(it does not invoke itself). It is the fucntion hanoi() that is
recursive.

 

[CBFalconer]

.... snip ...

You can convert iteration to recursion by managing your own stack.
I did a non-recursive quicksort that way a long time ago.

If it is only tail recursion, don't worry about it because the
compiler will probably rewrite it as iterative for you anyway.

You mean it MAY rewrite it as interactive, depending on the
compilers capability and the optimization level selected.

 

[Antoninus Twink]

You mean it MAY rewrite it as interactive

You really don't have any idea what you're talking about, do you?

Interactive and iterative are completely different things.

 

[osmium]

You really don't have any idea what you're talking about, do you?

Interactive and iterative are completely different things.

A spell checker sometimes causes nasty substitutions like that. But even if
it did, CBF should know that "will probably" and "may" mean quite similar
things. I think it's lonely in that basement.

 

[user923005]

A spell checker sometimes causes nasty substitutions like that.  But even if
it did, CBF should know that "will probably" and "may" mean quite similar
things.  I think it's lonely in that basement.

I wouldn't be too hard on him. I certainly suffered no offense. I
found quite an interesting dissertation on the towers of Hanoi in
Sedgewick. He shows that it is equivalent to many other problems
(including setting the markings on a ruler). Here is a fascinating
non-recursive version that I found:

#include <stdio.h>
#include <stdlib.h>

int main()
{
char string[25];
unsigned long long n,
one = 1,
x;
retry:
puts("How many disks?");
fflush(stdout);
if (fgets(string, sizeof string, stdin)) {
n = (unsigned long long) atof(string);
if (n == 0)
goto retry;
} else
goto retry;

for (x = 1; x < (one << n); x++)
printf("Move from pole %llu to pole %llu.\n", (x & x - 1) % 3,
(((x | x - 1) + 1) % 3));
return 0;
}

 

[Edward A. Falk]

Aaggh! My eyes! The goggles do nothing!

Seriously, dude. Spaces and blank lines are your friend. Why make the code
hard to read? See below. I'll refrain from nitpicking things like validating
your input or having main() return something useful.

But to answer your question, the usual way to "flatten out" a recursive
algorithm is to maintain a data stack. It can require a little creativity
to convert an algorithm from recursive to something else.

But why bother? Are you planning to implement an algorithm on a machine
or in a language that can't recurse? It's been a while since I last
programmed an IBM 370 or a PDP-8, and I can't imagine that's what you're
looking at.

 

[CBFalconer]

.... snip ...

Aaggh! My eyes! The goggles do nothing!

Seriously, dude. Spaces and blank lines are your friend. Why
make the code hard to read? See below. I'll refrain from
nitpicking things like validating your input or having main()
return something useful.

Please do not top-post. Your answer belongs after (or intermixed
with) the quoted material to which you reply, after snipping all
irrelevant material. See the following links:

<http://www.catb.org/~esr/faqs/smart-questions.html>
<http://www.caliburn.nl/topposting.html>
<http://www.netmeister.org/news/learn2quote.html>
<http://cfaj.freeshell.org/google/> (taming google)
<http://members.fortunecity.com/nnqweb/> (newusers)

 

[Ertugrul Söylemez]

But to answer your question, the usual way to "flatten out" a
recursive algorithm is to maintain a data stack. It can require a
little creativity to convert an algorithm from recursive to something
else.

To "flatten out" a recursive function, i.e. to make it iterative, is a
matter of making it tail-recursive (the recursive call should be the
last thing, the function does before returning something) first. Then
the rest is straightforward.

A tail-recursion is like changing the parameters and then goto-ing to
the beginning of the function. So

int gcd(int x, int y) {
if (y == 0) return x;
return gcd(y, x % y);
}

becomes:

int gcd(int x, int y) {
int tmp;

_start:
if (y == 0) return x;

/* Instead of calling recursively, adjust the parameters. */
tmp = x;
x = y;
y = tmp % y;
goto _start;
}

becomes (for C's sake):

int gcd(int x, int y) {
int tmp;

while(1) {
if (y == 0) return x;

/* Instead of calling recursively, adjust the parameters. */
tmp = x;
x = y;
y = tmp % y;
}
}

This is the general transformation rule. Of course, you can optimize
the gcd function further, but this is the general rule.

By the way, recursion doesn't mean slower code. In many cases,
recursive code can perform even better, particularly if the new
parameters depend directly on the current ones (like above), not on some
intermediary result.


Greets,
Ertugrul.

 

[Nick Keighley]

To "flatten out" a recursive function, i.e. to make it iterative, is a
matter of making it tail-recursive (the recursive call should be the
last thing, the function does before returning something) first.  Then
the rest is straightforward.

A tail-recursion is like changing the parameters and then goto-ing to
the beginning of the function.  So

  int gcd(int x, int y) {
    if (y == 0) return x;
    return gcd(y, x % y);
  }

becomes:

  int gcd(int x, int y) {
    int tmp;

    _start:
    if (y == 0) return x;

    /* Instead of calling recursively, adjust the parameters. */
    tmp = x;
    x = y;
    y = tmp % y;
    goto _start;
  }

becomes (for C's sake):

  int gcd(int x, int y) {
    int tmp;

    while(1) {
      if (y == 0) return x;

      /* Instead of calling recursively, adjust the parameters. */
      tmp = x;
      x = y;
      y = tmp % y;
    }
  }

This is the general transformation rule.  Of course, you can optimize
the gcd function further, but this is the general rule.

but how do you do that to the Tower of Hanoi code the OP
posted?

 

[Richard Tobin]

To "flatten out" a recursive function, i.e. to make it iterative, is a
matter of making it tail-recursive (the recursive call should be the
last thing, the function does before returning something) first.

This is a lot harder when there is more than one recursive call (as
with hanoi), and can be quite tricky even when there's only one if
there is computation to be done after the call (for a simple case,
consider factorial).

-- Richard

 

[Ertugrul Söylemez]

This is a lot harder when there is more than one recursive call (as
with hanoi), and can be quite tricky even when there's only one if
there is computation to be done after the call (for a simple case,
consider factorial).

In most cases, you can easily get around this by just adding an
accumulation parameter:

int factorial(int x, int b) {
if (x == 0) return b;
return factorial(x - 1, b*x);
}


Greets,
Ertugrul.

 

[Richard Tobin]

This is a lot harder when there is more than one recursive call (as
with hanoi), and can be quite tricky even when there's only one if
there is computation to be done after the call (for a simple case,
consider factorial).

[/QUOTE]

In most cases, you can easily get around this by just adding an
accumulation parameter:

int factorial(int x, int b) {
if (x == 0) return b;
return factorial(x - 1, b*x);
}

I'd be interested to see how you algorithmically turn the original
recursive factorial into that, as opposed to coming up with a
completely different, but tail-recursive, method.

Note that the tail-recursive version performs the multiplications in
a different order, so an algorithmic transformation needs to know
about the associativity of multiplication.

-- Richard

 

[Ertugrul Söylemez]

I'd be interested to see how you algorithmically turn the original
recursive factorial into that, as opposed to coming up with a
completely different, but tail-recursive, method.

Note that the tail-recursive version performs the multiplications in a
different order, so an algorithmic transformation needs to know about
the associativity of multiplication.

In functional terms, this is actually the difference between left folds
and right folds. The recursive version is a right fold. Correct would
be to write a left fold in the first place, because the right fold is,
as you said, a completely different algorithm.


Greets,
Ertugrul.

 

[Ertugrul Söylemez]

But to answer your question, the usual way to "flatten out" a
recursive algorithm is to maintain a data stack.  It can require a
little creativity to convert an algorithm from recursive to
something else.

To "flatten out" a recursive function, i.e. to make it iterative, is
a matter of making it tail-recursive (the recursive call should be
the last thing, the function does before returning something)
first.  Then the rest is straightforward.

[...]

but how do you do that to the Tower of Hanoi code the OP posted?

You don't. I was not answering to the OP. I don't know what complexity
the algorithm has, but I would just make it tail-recursive for the last
call and normally recursive for the first, if the complexity allows
that.


Greets,
Ertugrul.