Next: 6.2 Tail-Recursive Fibonacci Up: 6 Analyzing Algorithms Previous: 6 Analyzing Algorithms

## 6.1 Recursive Fibonacci

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.

Next: 6.2 Tail-Recursive Fibonacci Up: 6 Analyzing Algorithms Previous: 6 Analyzing Algorithms
2002-11-26