Recursion - Data Structures and Problem Solving Using Java - page 304

The close relation between recursion and stacks tells us that recursive
programs can always be implemented iteractively with an explicit stack. Pre-
sumably our stack will store items that are smaller than an activation record,
so we can also reasonably expect to use less space. The result is slightly faster
but longer code. Modern optimizing compilers have lessened the costs associ-
ated with recursion to such a degree that, for the purposes of speed, removing
recursion from an application that uses it well is rarely worthwhile.

Recursion can
always be removed
by using a stack.
This is occasionally
required to save
space.

7.3.4 too much recursion can be dangerous

In this text we give many examples of the power of recursion. However,
before we look at those examples, you should recognize that recursion is not
always appropriate. For instance, the use of recursion in Figure 7.1 is poor
because a loop would do just as well. A practical liability is that the overhead
of the recursive call takes time and limits the value of n for which the program
is correct. A good rule of thumb is that you should never use recursion as a
substitute for a simple loop.

Do not use recur-
sion as a substitute
for a simple loop.

A much more serious problem is illustrated by an attempt to calculate the
Fibonacci numbers recursively. The Fibonacci numbers are
defined as follows: and ; the i th Fibonacci number equals the
sum of the ( i th - 1) and ( i th - 2) Fibonacci numbers; thus .
From this definition we can determine that the series of Fibonacci numbers
continues: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,

The i th Fibonacci
number is the sum
of the two previous
Fibonacci numbers.

F 0 F 1 , , … F i ,

F 0 = 0 F 1 = 1

F i = F i + F i

- 1 - 2

.

…

The Fibonacci numbers have an incredible number of properties, which
seem always to crop up. In fact, one journal, The Fibonacci Quarterly , exists
solely for the purpose of publishing theorems involving the Fibonacci num-
bers. For instance, the sum of the squares of two consecutive Fibonacci num-
bers is another Fibonacci number. The sum of the first N Fibonacci numbers is
one less than (see Exercise 7.9 for some other interesting identities).
Because the Fibonacci numbers are recursively defined, writing a recur-
sive routine to determine F N seems natural. This recursive routine, shown in
Figure 7.6, works but has a serious problem. On our relatively fast machine, it
takes nearly a minute to compute F 40 , an absurd amount of time considering
that the basic calculation requires only 39 additions.

Do not do redun-
dant work recur-
sively; the program
will be incredibly
inefficient.

F N 2

+

figure 7.6
A recursive routine for
Fibonacci numbers: A
bad idea

1 // Compute the Nth Fibonacci number.
2 // Bad algorithm.
3 public static long fib( int n )
4 {
5 if( n <= 1 )
6 return n;
7 else
8 return fib( n - 1 ) + fib( n - 2 );
9 }