I’ve just read yet another article showing how to calculate elements of the Fibonacci sequence in some functional language. I’ll give examples in Scala, though I’m not doing anything very clever linguistically, so they shouldn’t be hard for anyone. Of course, it showed the hopelessly inefficient dual recursion

```
def terrible_fib(n: BigInt): BigInt =
if (n < 0) sys.error("not defined for -ve n")
else if (n == 0) 0
else if (n == 1) 1
else terrible_fib(n - 1) + terrible_fib(n - 2)
```

and a tail-recursive version

```
def tail_fib0(n: BigInt, a: BigInt, b: BigInt): BigInt =
if (n == 0) a
else tail_fib0(n - 1, a + b, a)
def tail_fib(n: BigInt): BigInt =
if (n < 0) sys.error("not defined for -ve n")
else tail_fib0(n, 0, 1)
```

There was also an explicitly iterative version, which isn’t
interestingly different from the tail-recursive version, so
I shan’t bother showing it. Unfortunately, the tail-recursive
version is still rather slow. On my (very old) laptop, it takes
nearly a minute to calculate `tail_fib(1000000)`

. We can do
*much* better.