By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
455,426 Members | 1,789 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 455,426 IT Pros & Developers. It's quick & easy.

How to write a nonrecursive program ?

P: n/a
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!
Nov 15 '08 #1
Share this Question
Share on Google+
11 Replies


P: n/a
On Nov 14, 6:17*pm, 960392...@qq.com 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,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.
Nov 15 '08 #2

P: n/a
<96*******@qq.comwrote in message
news:d7**********************************@v16g2000 prc.googlegroups.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.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_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.

Nov 15 '08 #3

P: n/a
On 2008-11-15, 96*******@qq.com <96*******@qq.comwrote:
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.

--
Andrew Smallshaw
an*****@sdf.lonestar.org
Nov 15 '08 #4

P: n/a
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.
Nov 15 '08 #5

P: n/a
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.

Nov 15 '08 #6

P: n/a
"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.
Nov 16 '08 #7

P: n/a
On Nov 15, 4:33*pm, "osmium" <r124c4u...@comcast.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;
}

Nov 17 '08 #8

P: n/a
In article <d7**********************************@v16g2000prc. googlegroups.com>,
<96*******@qq.comwrote:

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/
Nov 19 '08 #9

P: n/a
"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.html>
<http://cfaj.freeshell.org/google/ (taming google)
<http://members.fortunecity.com/nnqweb/ (newusers)

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

P: n/a
On 20 Nov, 22:26, Ertugrul Söylemez <e...@ertes.dewrote:
f...@green.rahul.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
Nov 21 '08 #11

P: n/a
In article <20*********************@ertes.de>,
Ertugrul Söylemez <es@ertes.dewrote:
>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.
Nov 21 '08 #12

This discussion thread is closed

Replies have been disabled for this discussion.