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

> 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 developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.