Design and Analysis of Algorithms

Design Using Recursion 183

8.1 INTRODUCTION

We are already familiar with recursive algorithms and their implementation. It is known that generally a non-

recursive version of the algorithm will execute effi ciently in terms of execution time and memory space due

to the following reasons.

1. The administrative overhead of entering and exiting from a function, every time the call to a recursive

routine is made;

2. Unnecessary stacking and unstacking of local (automatic) variables forced by the HLL compiler, because

it cannot detect which information will be or will not be needed later on (compilers for PROLOG can

detect such unnecessary stacking and avoid them).

3. Redundant recalculation of some values (see examples below) which can be avoided ...