I have two different ways to traverse a tree adt that essentially do the same thing except one is a recursive function and the other is iterative. How could I compare the efficiency between them?

RECURSIVE

``````inorder(node)
if node.left  ≠ null then inorder(node.left)
print node.value
if node.right ≠ null then``````

ITERATIVE

``````inorder(node)
while hasleftchild(node) do
node = node.left
do
visit(node)
if (hasrightchild(node)) then
node = node.right
while hasleftchild(node) do
node = node.left
else
while node.parent ≠ null and node == node.parent.right do
node = node.parent
node = node.parent
while node ≠ null``````

## Recommended Answers

> How could I compare the efficiency between them?
Use a profiler.

In big-O terms, the algorithm is the same, so the complexity is the same.

Generally speaking, iterative solutions tend to be more efficient, but you also have to write more code to make it work.

## All 2 Replies

> How could I compare the efficiency between them?
Use a profiler.

In big-O terms, the algorithm is the same, so the complexity is the same.

Generally speaking, iterative solutions tend to be more efficient, but you also have to write more code to make it work.

Simple recursive functions (and a smart compiler) may turn out to be iterative for free.
http://en.wikipedia.org/wiki/Tail_call

Put a start time and end time before the start and end of the function. You should start seeing differences in speed of execution after the number of nodes in the tree cross a certain threshold.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of 1.21 million developers, IT pros, digital marketers, and technology enthusiasts learning and sharing knowledge.