blob: e36c39d14e33b92ccb007123ceb14e7baceb59f7 (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
[Int] fibs := [1,1];
Int length([Int] xs) {
if (xs.nil) {
return 0;
} else {
return 1 + length(xs.tl);
}
}
Int get([Int] xs, Int i) {
if (i == 0) {
return xs.hd;
} else {
return get(xs.tl, i-1);
}
}
[Int] append([Int] xs, [Int] ys) {
if (xs.nil) {
return ys;
} else {
return xs.hd : append(xs.tl, ys);
}
}
Int fib(Int n) {
if (length(fibs) >= n) {
return get(fibs, n - 1);
} else {
Int fn := fib(n-1) + fib(n-2);
fibs := append(fibs, [fn]);
return fn;
}
}
Int main() {
return fib(92); // Largest to fit in a 64-bit integer
}
|
