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

On Nov 14, 6:17*pm, [e-mail] 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]

<96*******@qq.c omwrote in message
news:d7******** *************** ***********@v16 g2000prc.google groups.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_o...rsive_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]

On 2008-11-15, 96*******@qq.co m <96*******@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
an*****@sdf.lon estar.org

[CBFalconer]

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]

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]

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

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]

In article <d7************ *************** *******@v16g200 0prc.googlegrou ps.com>,
<96*******@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, fa**@despams.r. us.com
http://thespamdiaries.blogspot.com/

[CBFalconer]

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