```nvec ← ##.fibonacci num                     ⍝ Tail-recursive Fibonacci.
⍝ Leonardo Fibonacci 1170-1250.

An illustration of tail recursion with a left argument accumulator:

fibonacci←{     ⍝ Tail-recursive Fibonacci.
⍺←0 1
⍵=0:⍬⍴⍺
(1↓⍺,+/⍺)∇ ⍵-1
}

Compare this coding with the naïve stack-recursive version:

fib←{
⍵∊0 1:⍵
+/∇¨⍵-1 2
}

Some alternatives:

Nick Nikolov and Jay Foad suggest:

fib ← {⊃(+/,⊃)⍣⍵⊢1}
and:
fib ← +.!∘⌽⍨⍳       ⍝ ⎕io←0

John R. Clark suggests these non-recursive functions:

fib ← {+/{⍵!⌽⍵}(⍳⍵)-⎕io}            ⍝ JRC
and
fib ← {1↓⍎((3×⍵)⍴'⌽+\'),'1 0'}      ⍝ JRC

JRC may be cast as a derived function, using monadic commute:

fib ← +/∘(!∘⌽⍨)∘(-∘⎕io)∘⍳           ⍝ see →tacit←

and JRC may be converted to use the primitive power operator:

fib ← {⍬⍴⌽∘(+\)⍣⍵,0 1}              ⍝ ⍣ is primitive power operator.

or the equivalent derived function, using reduction for power (see →pow←):

fib ← ⍬∘⍴∘⊃∘(⊢∘⌽∘(+\)/)∘(,∘(⊂0 1))∘⍳

In a similar way, power can be applied on the following matrix multiplication:

|1 1|   |A B|   |A+C B+D|
|1 0| × |C D| = | A   B |

to obtain a terse but costly fib function:

fib ← {⊃(+.×⍣⍵)⍨2 2⍴1 1 1 0}

Another simple way is to perform a "hidden scan" with a reduction (see →scan←):

fib ← {⊃{⍵,+/¯2↑⍵}/⍵⍴1}

The following function illustrates the relationship between the  Fibonacci sequ-
ence and rational approximations to the "golden mean" (Phi). See →phinary←.

fib←{1∧+∘÷/0,⍵/1}
│ │   └───── continued fraction: 0 1 1 1 ...
│ └───────── approximation to Phi-1: 0 1 0.5 0.666 ...
└─────────── numerator of rational: 0 1 1 2 3 5 8 13 21 34 ...

Dick Bowman reminds us of Binet's formula, which also uses Phi:

fib ← {((phi*⍵)-(1-phi←.5×1+5*.5)*⍵)÷5*.5}

Peter-Michael Hager suggests this pleasantly symmetrical coding of Binet's form-
ula:

fib←{
p←0.5×1+5*0.5
q←0.5×1-5*0.5
((p*⍵)-q*⍵)÷p-q
}

In the above, constants p and q could be pre-evaluated and bound as the left and
right operands of a dyadic operator:

fib ← (0.5×1+5*0.5) {((⍺⍺*⍵)-⍵⍵*⍵)÷⍺⍺-⍵⍵} (0.5×1-5*0.5)

or:

fib ← (0.5×1+1 ¯1×5*0.5)∘{(-⌿⍺∘.*⍵)÷-/⍺}

As  Binet's formula employs only scalar functions, it may be applied to an array
argument. Using the above definition:

fib (0 1 2)(2 2⍴2+⍳4)
┌─────┬───┐
│0 1 1│2 3│
│     │5 8│
└─────┴───┘

Jane Sullivan extends Binet's formula to the real and complex domains.  A D-cod-
ind of Jane's real-valued function might look like this:

fib←{                                           ⍝ Sullivan
z←0.5×1+s←5*0.5
((z*⍵)-(2○○⍵)×z*-⍵)÷s
}

Ref: Sullivan J. "Functional Extensions to the Fibonacci Sequence", Vector 15.4.

Note that Jane's function is defined for negative arguments:

⎕pp←3 ⋄ fib ¯5 ¯4.5 to 5                        ⍝ fib ¯5 ¯4.5 .. 5
5 0.0513 ¯3 0.083 2 0.134 ¯1 0.217 1 0.352 0 0.569 1 0.92 1 1.49 2 2.41 3 3.9 5

Veli-Matti Jantunen suggests this coding for large Fibonacci numbers, eg >10000.

fib←{⎕ml←3
⍵≤2:1

{(+/∧\⍵='0')↓⍵
},'ZI9'⎕fmt(⍵-2){
⍺>0:(⍺-1)∇(↑⌽⍵)({
∧/⍵<1e9:⍵ ⋄ (1e9|⍵)+1⌽⍵≥1e9
}(↑⍵)+↑⌽⍵) ⋄ ↑⌽⍵
}2⍴⊂(-⌈⍵÷40)↑1
}

Paul Mansour offers this function, which uses OO techniques:

Fibonacci←{⎕io←0        ⍝ First ⍵ fibonacci numbers.
s←⎕NS''             ⍝ Class
s.(f←{⍺←⎕THIS ⋄ ⍺.i<2:⍺.n ⋄ ⊢⍺.n←+/⍺.a[⍺.i-1+⍳2].n}) ⍝ Method
v←⎕NS¨⍵⍴s           ⍝ Collection
v.i←⍳⍵              ⍝ Item number
v.n←⍵↑0 1           ⍝ Initialize
v.a←⊂v              ⍝ Each knows all
v.b←(1+⍳⍵)⍴¨⊂v      ⍝ Each knows self and previous?
v.f 0               ⍝ Compute
}

And finally: "That joke about the Fibonacci sequence was worse than the last two
jokes put together" - JD

Lucas numbers
-------------
Initialising the recursion with 2 1, instead of 0 1, returns the Lucas sequence:

2 1∘fibonacci¨ 0 to 20          ⍝ François Lucas 1842-1891.
2 1 3 4 7 11 18 29 47 76 123 199 322 521 843 1364 2207 3571 5778 9349 15127

http://en.wikipedia.org/wiki/Lucas_number

Fibonacci-based number system
-----------------------------
The Fibonacci sequence may be used as the base of a number system:

fibcode←{               ⍝ fibonacci-coding of number ⍵.

pair←{              ⍝ fib-pair
n←+/⍵           ⍝ next term.
⍺<n:⍵           ⍝ term large enough: finished.
⍺ ∇ 1↓⍵,n       ⍝ next pair
}                   ⍝ :: i j ← n ∇ i j

vec←{               ⍝ ⍺ is accumulator.
n(i j)←⍵        ⍝ remaining number and current fib pair.
i=0:⍺,1         ⍝ exhausted radix list: accumulator, sentinel.
f←(j-i),i       ⍝ next fib pair.
t←n≥j           ⍝ next term and
r←n-t×j         ⍝   remainder.
(t,⍺)∇ r f      ⍝ accumulated fib-coding.
}                   ⍝ :: [b] ← [b] ∇ n(i j)

⍬ vec ⍵,⊂⍵ pair 0 1 ⍝ fi
}

↑⍕∘fibcode¨0 to 10      ⍝ fibonacci coding of 0..10
1
1 1
0 1 1
0 0 1 1
1 0 1 1
0 0 0 1 1
1 0 0 1 1
0 1 0 1 1
0 0 0 0 1 1
1 0 0 0 1 1
0 1 0 0 1 1

See: http://en.wikipedia.org/wiki/Fibonacci_coding

Example:

fibonacci¨⍳10                 ⍝ ⎕io=1: F1 .. F10
1 1 2 3 5 8 13 21 34 55

fibonacci¨ 0 to 9             ⍝ first 10 Fibonacci numbers: F0 ..F9.
0 1 1 2 3 5 8 13 21 34

⍝ compare monitor of tail-recursive version:

fibonacci mdf 20
0 fibonacci←{     ⍝ Tail-recursive Fibonacci.
21     ⍺←0 1
21     ⍵=0:⍬⍴⍺
20     (1↓⍺,+/⍺)∇ ⍵-1
0 }

⍝ ... with monitor of stack-recursive version:

fib mdf 20
0 fib←{
21891     ⍵∊0 1:⍵
10945     +/∇¨⍵-1 2
0 }