# Computing Fibonacci Numbers

The following is an example that everyone likes, computing Fibonacci number recursively.

```
using NiLang
@i function rfib(out!, n::T) where T
@routine begin
n1 ← zero(T)
n2 ← zero(T)
n1 += n - 1
n2 += n - 2
end
if (value(n) <= 2, ~)
out! += 1
else
rfib(out!, n1)
rfib(out!, n2)
end
~@routine
end
```

The time complexity of this recursive algorithm is exponential to input `n`

. It is also possible to write a reversible linear time with for loops. A slightly non-trivial task is computing the first Fibonacci number that greater or equal to a certain number `z`

, where a `while`

statement is required.

```
@i function rfibn(n!, z)
@safe @assert n! == 0
out ← 0
rfib(out, n!)
@from n! == 0 while out < z
~rfib(out, n!)
n! += 1
rfib(out, n!)
end
~rfib(out, n!)
out → 0
end
```

In this example, the postcondition `n!=0`

in the `while`

statement is false before entering the loop, and it becomes true in later iterations. In the reverse program, the `while`

statement stops at `n==0`

. If executed correctly, a user will see the following result.

`rfib(0, 10)`

`(55, 10)`

compute which the first Fibonacci number greater than 100.

`rfibn(0, 100)`

`(12, 100)`

and uncompute

`(~rfibn)(rfibn(0, 100)...)`

`(0, 100)`

This example shows how an addition postcondition provided by the user can help to reverse a control flow without caching controls.

*This page was generated using Literate.jl.*