Recursive to non-recursive 
Author Message
 Recursive to non-recursive

Does anybody have sample code about using non-recursive algorithm replace a
recursive code, such like visiting a tree structure?

Any response will be very appreciated.

Michael



Sat, 21 Dec 2002 03:00:00 GMT  
 Recursive to non-recursive

Quote:

>Does anybody have sample code about using non-recursive algorithm replace a
>recursive code, such like visiting a tree structure?

There are no C language features that are specifically intended to support this
kind of algorithmic conversion, so this is off topic here.

Try comp.programmer or comp.theory.

--
#exclude <windows.h>



Sat, 21 Dec 2002 03:00:00 GMT  
 Recursive to non-recursive

Quote:

> Does anybody have sample code about using non-recursive algorithm replace a
> recursive code, such like visiting a tree structure?

If you're willing to go out and buy a book, I cover this for the
specific case you're interested in, in the "Binary Trees" chapter
of _C Unleashed_, which should be out in stores very soon.

If you're not willing, I'm putting out detailed information on it
for binary trees pretty soon, too (probably within a week).
Stayed tuned to comp.lang.c for details.



Sat, 21 Dec 2002 03:00:00 GMT  
 Recursive to non-recursive

Quote:

> Does anybody have sample code about using non-recursive algorithm replace a
> recursive code, such like visiting a tree structure?

Kaz is quite right, of course.

Still...

Sedgewick discusses replacing recursion with iteration.

Also, you will be delighted to know that you can get the GNU AVL tree
library from ftp.gnu.org - it's written by our very own Ben Pfaff, and
TTBOMKAB contains no recursive calls whatsoever.

--

Richard Heathfield

"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.

"You will get a wide range of opinion on this ranging from "yes" to
"no"." - Lawrence Kirby, 4 July 2000.

C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
52 K&R Answers: http://users.powernet.co.uk/eton/kandr2/index.html (45
to go)



Sun, 22 Dec 2002 03:00:00 GMT  
 Recursive to non-recursive
 > Does anybody have sample code about using non-recursive algorithm replace a
 > recursive code, such like visiting a tree structure?

For some algorithms it is inherently impossible to replace the recursive
algorithm by a non-recursive one.  Think about the Ackerman function.

For a tree structure, if you add some information to every node, a
non-recursive algorithm is possible.  But there are other newsgroups
dealing with this.
--
dik t. winter, cwi, kruislaan 413, 1098 sj  amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn  amsterdam, nederland; http://www.cwi.nl/~dik/



Sun, 22 Dec 2002 03:00:00 GMT  
 Recursive to non-recursive

Quote:

> > Does anybody have sample code about using non-recursive algorithm replace a
> > recursive code, such like visiting a tree structure?

>For some algorithms it is inherently impossible to replace the recursive
>algorithm by a non-recursive one.  Think about the Ackerman function.

Of course you can transform every recursive algorithm with a
non-recursive one using an explicit stack. That includes
Ackermann. There are turing-complete algorithmic models that do
without any recursion, e.g. the minimalistic PL language (or fortran)
or the Turing-machine itself.

Quote:
>For a tree structure, if you add some information to every node, a
>non-recursive algorithm is possible.  But there are other newsgroups
>dealing with this.

Correct. Followup set.

Stephan

--
-------------------------- It can be done! ---------------------------------

----------------------------------------------------------------------------



Sun, 22 Dec 2002 03:00:00 GMT  
 
 [ 6 post ] 

 Relevant Pages 

1. Non-recursive preprocessor macros?

2. RELEASE: non-recursive qsort

3. Non-recursive preprocessor macros?

4. Non recursive funct for permutation

5. Non-recursive Quick Sort

6. Quicksort non-recursive????????

7. HELP!: non-recursive binary tree inorder traversal algorithm

8. Yet another recursive file find routine (non MFC) - feel free to rip it apart

9. Help needed with non-recursive floodfill

10. Asynchronous socket & recursive receiving

11. how get rid of recursive checkout?

12. Recursive program that evaluate a postfix expression

 

 
Powered by phpBB® Forum Software