|
M←{
f←⍺⍺
i←2+'⋄'⍳⍨t←3↓,⎕CR'f'
0=⎕NC'⍺':⍎' {T←(1+ ⍵)⍴¯1 ⋄ {',(i↑t),'¯1≢T[⍵] :⊃T[⍵] ⋄ ⊃T[⍵] ←⊂',(i↓t),'⍵}⍵'
⍎'⍺{T←(1+⍺,⍵)⍴¯1 ⋄ ⍺{',(i↑t),'¯1≢T[⍺;⍵]:⊃T[⍺;⍵] ⋄ ⊃T[⍺;⍵]←⊂',(i↓t),'⍵}⍵'
}
a. |
The Fibonacci numbers can be written as a double recursion:
fib←{1≥⍵:⍵ ⋄ (∇ ⍵-2)+∇ ⍵-1}
fib¨ ⍳15
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377
(fib ≡ fib M)¨ ⍳15
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Run a benchmark of fib 30
versus fib M 30 .
|
b. |
The binomial coefficient ⍺!⍵
can be computed by a doubly-recursive function:
bc←{(⍺≤0)∨⍵≤⍺:⍺∊0,⍵ ⋄ (⍺-0 1)+.∇ ⍵-1}
(∘.bc ≡ ∘.!)⍨⍳10
1
Run a benchmark of 12 bc 24
versus 12 bc M 24 .
|
c. |
Size ⍺ combinations
of ⍳⍵ can be enumerated by
a doubly-recursive function:
comb←{(⍺=0)∨⍺=⍵:(1,⍺)⍴⍳⍺ ⋄ (0,1+(⍺-1)∇ ⍵-1)⍪1+⍺ ∇ ⍵-1}
Run a benchmark of 8 comb 16
versus 8 comb M 16 .
|
|