user
The **Fibonacci sequence** is a sequence    Fn    of natural numbers defined recursively:

```
      F0 = 0 
      F1 = 1 
      Fn = Fn-1 + Fn-2, if n>1 

```

Task

Write a function to generate the    nth    Fibonacci number.

Solutions can be iterative or recursive (though recursive solutions are generally considered too slow and are mostly used as an exercise in recursion).

The sequence is sometimes extended into negative numbers by using a straightforward inverse of the positive definition:

```
      Fn = Fn+2 - Fn+1, if n<0   

```

support for negative      n      in the solution is optional.

Related tasks

* Fibonacci n-step number sequences‎
* Leonardo numbers

References

* Wikipedia, Fibonacci number
* Wikipedia, Lucas number
* MathWorld, Fibonacci Number
* Some identities for r-Fibonacci numbers
* OEIS Fibonacci numbers
* OEIS Lucas numbers
assistant
(formerly Perl 6)

### List Generator

This constructs the fibonacci sequence as a lazy infinite list.

```
constant @fib = 0, 1, *+* ... *;
```

If you really need a function for it:

```
sub fib ($n) { @fib[$n] }
```

To support negative indices:

```
constant @neg-fib = 0, 1, *-* ... *;
sub fib ($n) { $n >= 0 ?? @fib[$n] !! @neg-fib[-$n] }
```

### Iterative

```
sub fib (Int $n --> Int) {
    $n > 1 or return $n;
    my ($prev, $this) = 0, 1;
    ($prev, $this) = $this, $this + $prev for 1 ..^ $n;
    return $this;
}
```

### Recursive

```
proto fib (Int $n --> Int) {*}
multi fib (0)  { 0 }
multi fib (1)  { 1 }
multi fib ($n) { fib($n - 1) + fib($n - 2) }
```