The recursive definitions mentioned above all involve trivial
linear recursive processes. The next example illustrates the kind of analysis
a student might perform on a less trivial problem. Consider the standard
recursive definition of the fibonacci function.
fibonacci =: monad define script if. y. < 2 do. y. else. (fibonacci y. - 1) + fibonacci y. - 2 end. )
Program fibonacci (J Version)
Applying
fibonacci to the argument 5 produces a result of 5. Tracing
fibonacci produces the output
traced_fibonacci 5 Entering, input = 5 Entering, input = 4 Entering, input = 3 Entering, input = 2 Entering, input = 1 Leaving, result = 1 Entering, input = 0 Leaving, result = 0 Leaving, result = 1 Entering, input = 1 Leaving, result = 1 Leaving, result = 2 Entering, input = 2 Entering, input = 1 Leaving, result = 1 Entering, input = 0 Leaving, result = 0 Leaving, result = 1 Leaving, result = 3 Entering, input = 3 Entering, input = 2 Entering, input = 1 Leaving, result = 1 Entering, input = 0 Leaving, result = 0 Leaving, result = 1 Entering, input = 1 Leaving, result = 1 Leaving, result = 2 Leaving, result = 5 5
Analyzing the
fibonacci definition, we notice that there are two
recursive calls to fibonacci inside this definition. We next write
the continuations of each of these calls.
monad define 'y. + fibonacci n - 2' monad define '(fibonacci n - 1) + y.'
fibonacci is not tail recursive. In fact, each continuation contains a
recursive call to fibonacci. We also notice, from the traced output, that
fibonacci makes applications of fibonacci to the same argument.
Consider the problem of evaluating fibonacci 3. Two continuations must be
formed.
c1 =: monad define'y. + fibonacci 0' c2 =: monad define'y. + fibonacci 1'
The value of
fibonacci 3 is represented by the expression
c2 c1 1. Next, consider the problem of evaluating fibonacci 4.
Three continuations must be formed.
c1 =: monad define'y. + fibonacci 0' c2 =: monad define'y. + fibonacci 1' c3 =: monad define'y. + fibonacci 2'
The value of
fibonacci 4 is represented by the expression
c3 c2 c1 1.
Next we consider the number of times fibonacci is called while evaluating
fibonacci. Define fib_work to be the number of times fibonacci
is called while evaluating fibonacci. We see that:
fib_work 0 = 1
fib_work 1 = 1
fib_work 2 = 3
fib_work 3 = 5
fib_work 4 = 9
fib_work 5 = 15
It is easy to establish the recurrence formula for fib_work
fib_work n = 1 + (fib_work n - 1) + fib_work n - 2
Assuming that the execution time of
fibonacci is proportional to
fib_work, then the order of fibonacci is
fib_work which is, itself, a fibonacci function. This
analysis leads to a laboratory experiment [How 94] in which students conduct
timing measurements of the number of recursive calls per second a
workstation can make to fibonacci. Since fibonacci would make
1146295688027634168201 recursive calls while evaluating fibonacci 100, a
workstation which can perform 1,000,000 recursive calls per second would require approximately
1146295688027634 seconds (more than 363487 centuries!) to evaluate fibonacci 100.
This laboratory provides the opportunity for students to deal with formal analysis,
experimental measurements, recursion and iteration.