How to write a nonrecursive program ?

[960392954@qq.com]

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,ter minal);
else{/*move the disks in a recrusive way*/
hanoi(num-1,initial,tempo rary,terminal);
printf("%c==>%c \n",initial,ter minal);
hanoi(num-1,temporary,ter minal,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.Cou ld 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]

Re: How to write a nonrecursive program ?

On Nov 14, 6:17 pm, 960392...@qq.co m wrote:

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,ter minal);
        else{/*move the disks in a recrusive way*/
                hanoi(num-1,initial,tempo rary,terminal);
                printf("%c==>%c \n",initial,ter minal);
                hanoi(num-1,temporary,ter minal,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.Cou ld 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]

Re: How to write a nonrecursive program ?

<960392954@qq.c omwrote in message
news:d7c2952e-6c44-4685-b480-5c94ab4dfe11@v1 6g2000prc.googl egroups.com...

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.Cou ld 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]

Re: How to write a nonrecursive program ?

On 2008-11-15, 960392954@qq.co m <960392954@qq.c omwrote:

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.Cou ld 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.

--
Andrew Smallshaw
andrews@sdf.lon estar.org

[CBFalconer]

Re: How to write a nonrecursive program ?

user923005 wrote:

>

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

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home .att.net>
Try the download section.

[Antoninus Twink]

Re: How to write a nonrecursive program ?

On 15 Nov 2008 at 23:16, CBFalconer wrote:

user923005 wrote:

>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

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

Interactive and iterative are completely different things.

[osmium]

Re: How to write a nonrecursive program ?

"Antoninus Twink" wrote:

On 15 Nov 2008 at 23:16, CBFalconer wrote:

>user923005 wrote:

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

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

Re: How to write a nonrecursive program ?

On Nov 15, 4:33 pm, "osmium" <r124c4u...@com cast.netwrote:

"Antoninus Twink" wrote:

On 15 Nov 2008 at 23:16, CBFalconer wrote:

user923005 wrote:
>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

>

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.

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]

Re: How to write a nonrecursive program ?

In article <d7c2952e-6c44-4685-b480-5c94ab4dfe11@v1 6g2000prc.googl egroups.com>,
<960392954@qq.c omwrote:

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.

>#include <stdio.h>
>
>void hanoi(int num, char initial, char terminal, char temporary);
>
>int main ()
>{
> int num; /*num is the number of disks of the initial peg*/
> /*a is the initial peg , c is the terminal peg, b is used as a temporary peg*/
> char a='a', b='b', c='c';
>
> 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);
> }
>}

--
-Ed Falk, falk@despams.r. us.com

http://thespamdiaries.blogspot.com/

[CBFalconer]

Re: How to write a nonrecursive program ?

"Edward A. Falk" wrote:

>

.... 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.htm l>
<http://cfaj.freeshell. org/google/ (taming google)
<http://members.fortune city.com/nnqweb/ (newusers)

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home .att.net>
Try the download section.

[Nick Keighley]

Re: How to write a nonrecursive program ?

On 20 Nov, 22:26, Ertugrul Söylemez <e...@ertes.dew rote:

f...@green.rahu l.net (Edward A. Falk) wrote:
>

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.

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

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.

--
Nick Keighley

[Richard Tobin]

Re: How to write a nonrecursive program ?

In article <20081120232641 .0397db38@ertes .de>,
Ertugrul Söylemez <es@ertes.dewro te:

>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
--
Please remember to mention me / in tapes you leave behind.