D a t a s t r u c t u r e s a n d a L g o r I t h m s Annotated Reference with Examples

O(n
2
)
2.
O(n
3
)
93

---

APPENDIX C. RECURSIVE VS. ITERATIVE SOLUTIONS
94
3.
O(2
n
)
If you use recursion for algorithms with any of the above run time efficiency’s
you are inviting trouble. The growth rate of these algorithms is high and in
most cases such algorithms will lean very heavily on techniques like divide and
conquer. While constantly splitting problems into smaller problems is good
practice, in these cases you are going to be spawning a lot of method calls. All
this overhead (method calls don’t come that cheap) will soon pile up and either
cause your algorithm to run a lot slower than expected, or worse, you will run
out of stack space. When you exceed the allotted stack space for a thread the
process will be shutdown by the operating system. This is the case irrespective
of the platform you use, e.g. .NET, or native C++ etc. You can ask for a bigger
stack size, but you typically only want to do this if you have a very good reason
to do so.
C.1
Activation Records
An activation record is created every time you invoke a method. Put simply
an activation record is something that is put on the stack to support method
invocation. Activation records take a small amount of time to create, and are
pretty lightweight.
Normally an activation record for a method call is as follows (this is very
general):
•
The actual parameters of the method are pushed onto the stack
•
The return address is pushed onto the stack
•
The top-of-stack index is incremented by the total amount of memory
required by the local variables within the method
•
A jump is made to the method
In many recursive algorithms operating on large data structures, or algo-
rithms that are inefficient you will run out of stack space quickly. Consider an
algorithm that when invoked given a specific value it creates many recursive
calls. In such a case a big chunk of the stack will be consumed. We will have to
wait until the activation records start to be unwound after the nested methods
in the call chain exit and return to their respective caller. When a method exits
it’s activation record is unwound. Unwinding an activation record results in
several steps:
1.
The top-of-stack index is decremented by the total amount of memory
consumed by the method
2.
The return address is popped off the stack
3.
The top-of-stack index is decremented by the total amount of memory
consumed by the actual parameters

---

APPENDIX C. RECURSIVE VS. ITERATIVE SOLUTIONS
95
While activation records are an efficient way to support method calls they
can build up very quickly. Recursive algorithms can exhaust the stack size
allocated to the thread fairly fast given the chance.
Just about now we should be dusting the cobwebs off the age old example of
an iterative vs. recursive solution in the form of the Fibonacci algorithm. This
is a famous example as it highlights both the beauty and pitfalls of a recursive
algorithm. The iterative solution is not as pretty, nor self documenting but it
does the job a lot quicker. If we were to give the Fibonacci algorithm an input
of say 60 then we would have to wait a while to get the value back because it
has an O(g
n
) run time. The iterative version on the other hand has a O(n)
run time. Don’t let this put you off recursion. This example is mainly used
to shock programmers into thinking about the ramifications of recursion rather
than warning them off.
C.2
Some problems are recursive in nature
Something that you may come across is that some data structures and algo-
rithms are actually recursive in nature. A perfect example of this is a tree data
structure. A common tree node usually contains a value, along with two point-
ers to two other nodes of the same node type. As you can see tree is recursive
in its makeup wit each node possibly pointing to two other nodes.
When using recursive algorithms on tree’s it makes sense as you are simply
adhering to the inherent design of the data structure you are operating on. Of
course it is not all good news, after all we are still bound by the limitations we
have mentioned previously in this chapter.
We can also look at sorting algorithms like merge sort, and quick sort. Both
of these algorithms are recursive in their design and so it makes sense to model
them recursively.
C.3
Summary
Recursion is a powerful tool, and one that all programmers should know of.
Often software projects will take a trade between readability, and efficiency in
which case recursion is great provided you don’t go and use it to implement
an algorithm with a quadratic run time or higher. Of course this is not a rule
of thumb, this is just us throwing caution to the wind. Defensive coding will
always prevail.
Many times recursion has a natural home in recursive data structures and
algorithms which are recursive in nature. Using recursion in such scenarios is
perfectly acceptable. Using recursion for something like linked list traversal is
a little overkill. Its iterative counterpart is probably less lines of code than its
recursive counterpart.
Because we can only talk about the implications of using recursion from an
abstract point of view you should consult your compiler and run time environ-
ment for more details. It may be the case that your compiler recognises things
like tail recursion and can optimise them. This isn’t unheard of, in fact most
commercial compilers will do this. The amount of optimisation compilers can

---