``````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: collection.mutable.Map[Int, Long] = HashMap(
//   0 -> 0L,
//   1 -> 1L,
//   2 -> 1L,
//   3 -> 2L,
//   4 -> 3L,
//   5 -> 5L,
//   6 -> 8L,
//   7 -> 13L,
//   8 -> 21L,
//   9 -> 34L,
//   10 -> 55L
// )

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(10)
// res2: Long = 55L
``````

## Recursive squaring

Imports

``````import org.jblas.DoubleMatrix

import cats.implicits._

import spire.algebra.EuclideanRing
import spire.algebra.NRoot
import spire.algebra.Rng

import axle._
import axle.jblas._

implicit val eucRingInt: EuclideanRing[Int] = spire.implicits.IntAlgebra
implicit val rngDouble: Rng[Double] = spire.implicits.DoubleAlgebra
implicit val nrootDouble: NRoot[Double] = spire.implicits.DoubleAlgebra
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: 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
}
``````

Demo:

``````fibonacciSubLinear(78)
// res3: Long = 8944394323791464L
``````

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