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
implicit val laJblasDouble = axle.jblas.linearAlgebraDoubleMatrix[Double]
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.