Recursive functions Vs Non-recursive functions - performance aspect

W

Willem

Richard Harter wrote:
) Yes and no. If you maintain your own stack you are using heap
) storage rather than program stack and the activation records
) should be shorter. In consequence you can go deeper; i.e., you
) will blow out later rather than sooner.

More importantly: You can blow out gracefully!


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
 
K

Keith Thompson

user923005 said:
Conversion to iteration does not help here.
In the conversion, you definitely have to maintain your own stack.

It depends on the algorithm. Some recursive algorithms can be
converted to iterative algorithms that don't require a stack; examples
are Fibonacci numbers and factorials. (For Fibonacci numbers in
particular, the naive recursive algorithm is horribly inefficient.)

Other algorithms, like binary tree traversal, are inherently
recursive, and you need some sort of stack to keep track of what
you've done and what still needs to be done. But as Richard Harter
points out, if you maintain your own stack you can probably store less
information in each node.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,482
Members
44,901
Latest member
Noble71S45

Latest Threads

Top