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.