Printable View
which tree traversal method is more efficient? recursive or nonrecursive ?
Most of the people says that nonrecursiv is more efficient.
But i have a book of data structure by Langsam, Augenstein and Tenenbaum which says that recursive is more efficient.
So which is more efficient and by how much difference?
Thanks in advance.
binary tree traversal
Since both approaches are implementing the same algorithm, then it's really down to the skill of the implementer.
It's not like one approach is O(n) and another is O(n*n).
What kind of "efficient" are you talking about?
Recursive can be very efficient to write the code for, but might not perform so well at run-time.
Whereas a non-recursive implementation takes work to get right, but is a lot better at run-time.
Ok. time complexity will remain same. But what about speed of execution? For nonrecursive implementation we have to write push(), pop(), isstackempty(), ...Quote:
Originally Posted by Salem
Since automatic stack is more efficient than that of an user defined, it will result in performance boost(a little). In recursive code(4-5 lines) there is no extra variable,so no variables are pushed onto stack.
Please note one thing that i am talking about only binary tree traversals. Let's not talk about 'recursion vs non recursion'.
I'm not an expert. so please correct me if i'm wrong.
Like I said, quality of implementation.
For every person who can do 'X' smartly, there will be another person who can screw up 'Y' badly enough for someone to come along and say 'X' is better.
> For nonrecursive implementation we have to write push(), pop(), isstackempty(), ...
True, but in an efficient C++ class implementation, these could be inline calls with no call overhead.
You can't judge efficiency simply by counting lines of code, or apparent function calls.
Mostly, the topic is pointless.
- change the programmer
- change the compiler
- change the compiler flags
- change the machine
All of these can have just as big an impact on the performance of the program as choosing one of two ways to implement the same code.
> Ok. time complexity will remain same. But what about speed of execution?
Do you know the difference?
If an O(N) algorithm takes 5 seconds, as written by one programmer, for one machine, is it still O(N) if it takes 10 seconds when written by another programmer for another machine?
If you think the answer is "no", then you're missing the point of what I'm trying to tell you.
Adding to what Salem has said, the academic world doesn't usually represent the real world.
There are a lot of cases where linear algorithms perform superior to other linear algorithms because of some characteristic of the implementation, some tweak of the platform, or just some aspect of the data.
You can build a non-recursive, non-stack based binary tree traversal algorithm in a lot of ways. You can modify the tree as you go. You can use bit twiddling masks. You can use a "visited" flag if the tree has one. You can use a fairly simple iteration scheme if the tree is strictly balanced.
You could improve the non-recursive, stack based implementation. You could swap out a linked list based implementation for an array based version. You could build an outside visited nodes using bit twiddling tricks. You could build a stack based on XOR mathematics and the two facts C guarantees for any object. (I'd probably go this route; that no object has a zero address and that no two objects share an address make the implementation obvious.)
You could even optimize the recursive versions of the algorithm by limiting stack use, keeping the important bits in registers, or using a better function call mechanism. There is a lot of potential depending on your compiler.
At the end of the day, you aren't going to know which is going to be faster for any given situation. You'll just have to try one and see.
Soma