Fibonacci
Compute Fibonacci numbers using the recurrence F(n + 2) = F(n + 1) + F(n), starting from F(0) = 0 and F(1) = 1.
# Fibonacci with a bounded loop and arbitrary-precision integers.func fibonacci(n: Int): Int { let a = 0 let b = 1 let i = 0 while i < n { let next = a + b a = b b = next i = i + 1 } ret a}
let i = 0while i < 10 { print("fib({i}) = {fibonacci(i)}") i = i + 1}Original example: checked output and syntax tree
These records belong to the original downloadable program. Run the editor above to see results for your changes.
fib(0) = 0 fib(1) = 1 fib(2) = 1 fib(3) = 2 fib(4) = 3 fib(5) = 5 fib(6) = 8 fib(7) = 13 fib(8) = 21 fib(9) = 34
Original AST
[
{
"node": {
"FuncDef": {
"name": {
"node": "fibonacci",
"span": [
71,
80
]
},
"params": [
{
"name": {
"node": "n",
"span": [
81,
82
]
},
"type_ann": {
"node": {
"Name": "Int"
},
"span": [
84,
87
]
}
}
],
"ret_type": {
"node": {
"Name": "Int"
},
"span": [
90,
93
]
},
"body": [
{
"node": {
"Let": {
"pattern": {
"node": {
"Binding": {
"node": "a",
"span": [
104,
105
]
}
},
"span": [
104,
105
]
},
"type_ann": null,
"value": {
"node": {
"Int": "0"
},
"span": [
108,
109
]
}
}
},
"span": [
100,
109
]
},
{
"node": {
"Let": {
"pattern": {
"node": {
"Binding": {
"node": "b",
"span": [
118,
119
]
}
},
"span": [
118,
119
]
},
"type_ann": null,
"value": {
"node": {
"Int": "1"
},
"span": [
122,
123
]
}
}
},
"span": [
114,
123
]
},
{
"node": {
"Let": {
"pattern": {
"node": {
"Binding": {
"node": "i",
"span": [
132,
133
]
}
},
"span": [
132,
133
]
},
"type_ann": null,
"value": {
"node": {
"Int": "0"
},
"span": [
136,
137
]
}
}
},
"span": [
128,
137
]
},
{
"node": {
"Expr": {
"node": {
"While": {
"cond": {
"node": {
"BinOp": {
"op": "Lt",
"left": {
"node": {
"Name": "i"
},
"span": [
148,
149
]
},
"right": {
"node": {
"Name": "n"
},
"span": [
152,
153
]
}
}
},
"span": [
148,
153
]
},
"body": [
{
"node": {
"Let": {
"pattern": {
"node": {
"Binding": {
"node": "next",
"span": [
168,
172
]
}
},
"span": [
168,
172
]
},
"type_ann": null,
"value": {
"node": {
"BinOp": {
"op": "Add",
"left": {
"node": {
"Name": "a"
},
"span": [
175,
176
]
},
"right": {
"node": {
"Name": "b"
},
"span": [
179,
180
]
}
}
},
"span": [
175,
180
]
}
}
},
"span": [
164,
180
]
},
{
"node": {
"Assign": {
"target": {
"Name": "a"
},
"value": {
"node": {
"Name": "b"
},
"span": [
193,
194
]
}
}
},
"span": [
189,
194
]
},
{
"node": {
"Assign": {
"target": {
"Name": "b"
},
"value": {
"node": {
"Name": "next"
},
"span": [
207,
211
]
}
}
},
"span": [
203,
211
]
},
{
"node": {
"Assign": {
"target": {
"Name": "i"
},
"value": {
"node": {
"BinOp": {
"op": "Add",
"left": {
"node": {
"Name": "i"
},
"span": [
224,
225
]
},
"right": {
"node": {
"Int": "1"
},
"span": [
228,
229
]
}
}
},
"span": [
224,
229
]
}
}
},
"span": [
220,
229
]
}
]
}
},
"span": [
142,
235
]
}
},
"span": [
142,
235
]
},
{
"node": {
"Ret": {
"keyword": [
240,
243
],
"value": {
"node": {
"Name": "a"
},
"span": [
244,
245
]
}
}
},
"span": [
240,
245
]
}
]
}
},
"span": [
66,
247
]
},
{
"node": {
"Let": {
"pattern": {
"node": {
"Binding": {
"node": "i",
"span": [
253,
254
]
}
},
"span": [
253,
254
]
},
"type_ann": null,
"value": {
"node": {
"Int": "0"
},
"span": [
257,
258
]
}
}
},
"span": [
249,
258
]
},
{
"node": {
"Expr": {
"node": {
"While": {
"cond": {
"node": {
"BinOp": {
"op": "Lt",
"left": {
"node": {
"Name": "i"
},
"span": [
265,
266
]
},
"right": {
"node": {
"Int": "10"
},
"span": [
269,
271
]
}
}
},
"span": [
265,
271
]
},
"body": [
{
"node": {
"Expr": {
"node": {
"Call": {
"callee": {
"node": {
"Name": "print"
},
"span": [
278,
283
]
},
"args": [
{
"node": {
"Interp": {
"parts": [
{
"Lit": "fib("
},
{
"Expr": {
"node": {
"Name": "i"
},
"span": [
290,
291
]
}
},
{
"Lit": ") = "
},
{
"Expr": {
"node": {
"Call": {
"callee": {
"node": {
"Name": "fibonacci"
},
"span": [
297,
306
]
},
"args": [
{
"node": {
"Name": "i"
},
"span": [
307,
308
]
}
],
"args_span": [
306,
309
]
}
},
"span": [
297,
309
]
}
}
]
}
},
"span": [
284,
311
]
}
],
"args_span": [
283,
312
]
}
},
"span": [
278,
312
]
}
},
"span": [
278,
312
]
},
{
"node": {
"Assign": {
"target": {
"Name": "i"
},
"value": {
"node": {
"BinOp": {
"op": "Add",
"left": {
"node": {
"Name": "i"
},
"span": [
321,
322
]
},
"right": {
"node": {
"Int": "1"
},
"span": [
325,
326
]
}
}
},
"span": [
321,
326
]
}
}
},
"span": [
317,
326
]
}
]
}
},
"span": [
259,
328
]
}
},
"span": [
259,
328
]
}
]The loop invariant
Section titled “The loop invariant”Before each iteration, a holds F(i) and b holds F(i + 1). Save their sum, move b into a, then move the sum into b. Incrementing i restores the same relationship for the next iteration.
When i == n, return a. The n == 0 case needs no special branch because the initial value is already correct.
The example calls the function for ten nonnegative indices. The function does not validate negative input; add an explicit result type if your caller may supply it.
KataScript’s Int values are arbitrary precision. The bounded loop also avoids the host-stack limits of deep recursion. It recomputes each requested Fibonacci number independently; a sequence-producing iterator could retain state across requests.
Continue with control flow or the custom iterator.