``````import axle.math._
``````

## Linear using `foldLeft`

``````fibonacciByFold(10)
// res0: Int = 89
``````

## Recursive

``````fibonacciRecursively(10)
// res1: Int = 89
``````

Some alternatives that are not in Axle include

## Recursive with memoization

``````val memo = collection.mutable.Map(0 -> 0L, 1 -> 1L)
// memo: scala.collection.mutable.Map[Int,Long] = Map(1 -> 1, 0 -> 0)

def fibonacciRecursivelyWithMemo(n: Int): Long = {
if (memo.contains(n)) {
memo(n)
} else {
val result = fibonacciRecursivelyWithMemo(n - 2) + fibonacciRecursivelyWithMemo(n - 1)
memo += n -> result
result
}
}
// fibonacciRecursivelyWithMemo: (n: Int)Long

fibonacciRecursivelyWithMemo(10)
// res2: Long = 55
``````

## Recursive squaring

Imports

``````import axle._
import axle.jblas._
import spire.implicits._
import org.jblas.DoubleMatrix

import laJblasDouble._
``````

The fibonacci sequence at N can be generated by taking the Nth power of a special 2x2 matrix. By employing the general-purpose strategy for exponentiation called “recursive squaring”, we can achieve sub-linear time.

``````val base = fromColumnMajorArray(2, 2, List(1d, 1d, 1d, 0d).toArray)
// base: org.jblas.DoubleMatrix = [1.000000, 1.000000; 1.000000, 0.000000]

def fibonacciSubLinear(n: Int): Long = n match {
case 0 => 0L
case _ => exponentiateByRecursiveSquaring(base, n).get(0, 1).toLong
}
// fibonacciSubLinear: (n: Int)Long
``````

Demo:

``````fibonacciSubLinear(78)
// res4: Long = 8944394323791464
``````

Note: Beyond 78 inaccuracies creep in due to the limitations of the `Double` number type.