Howland [How 1998] used the often studied recursive Fibonacci function to describe recursive and iterative processes. In J, the recursive Fibonacci function is defined as:
fibonacci =. monad define if. y. < 2 do. y. else. (fibonacci y. - 1) + fibonacci y. - 2 end. )
Applying fibonacci to the integers 0 through 10 gives:
fibonacci "0 i.11 0 1 1 2 3 5 8 13 21 34 55
Howland [How 1998] also introduced the idea of a continuation; a monad representing the computation remaining in an expression after evaluating a sub-expression.
Given a compound expression e and a sub-expression f of e, the continuation of f in e is the computation in e, written as a monad, which remains to be done after first evaluating f. When the continuation of f in e is applied to the result of evaluating f, the result is the same as evaluating the expression e. Let c be the continuation of f in e. The expression e may then be written as c f.
Continuations provide a ``factorization'' of expressions into two parts; f which is evaluated first and c which is later applied to the result of f. Continuations are helpful in the analysis of algorithms.
Analysis of the recursive fibonacci definition reveals that each
continuation of fibonacci in fibonacci contains an
application of fibonacci. Hence, since at least one continuation
of a recursive application of fibonacci is not the identity
monad, the execution of fibonacci results in a recursive process.
Define a monad, fib_work, to be the number of times fibonacci
is applied to evaluate fibonacci. fib_work is, itself, a
fibonacci sequence generated by the J definition:
fib_work =. monad define if. y. < 2 do. 1 else. 1 + (fib_work y. - 1) + fib_work y. - 2 end. )
Applying fib_work to the integers 0 through 10 gives:
fib_work "0 i.11 1 1 3 5 9 15 25 41 67 109 177