455,426 Members | 1,789 Online
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 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
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 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]: 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 thecompiler 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 thecompiler 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" #include 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 , <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 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: Try the download section. Nov 19 '08 #10

 P: n/a On 20 Nov, 22:26, Ertugrul Söylemez

 P: n/a In article <20*********************@ertes.de>, Ertugrul SÃ¶ylemez To "flatten out" a recursive function, i.e. to make it iterative, is amatter of making it tail-recursive (the recursive call should be thelast 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.