Skip to content

Instantly share code, notes, and snippets.

@drincruz drincruz/fibonacci.ex
Last active Oct 31, 2018

Embed
What would you like to do?
What Fibonacci looks like in Elixir
defmodule ElixirLab.Fibonacci do
# Recursive
def fib(0), do: 1
def fib(1), do: 1
def fib(n), do: fib(n-1) + fib(n-2)
# Iterative
def iter_fib(0), do: 1
def iter_fib(1), do: 1
def iter_fib(index) do
Enum.reduce(2..index, [1, 1], fn(_i, acc) ->
# Calculate the Fibonacci value
fib_val =
# Take the accumulator
acc
# Flatten the list since we're appending fib_val by a new list
|> List.flatten()
# Sum those values
|> Enum.sum()
[Enum.take(acc, -1), fib_val]
end)
# This is now the previous Fibonacci value and index's value, so just take the last value
|> List.last()
end
end
@ThomasBracher

This comment has been minimized.

Copy link

commented Aug 24, 2017

I prefer the dynamic programming version much better, plus it is more elegant. Although not as readable as the first recursive version, it removes the performance issues.

def fib(0), do: 1
def fib(1), do: 1
def fib(n), do: fib(1, 1, n)

def fib(last, _prev, 1), do: last
def fib(last, prev, n), do: fib(last + prev, last, n - 1)
@dhc02

This comment has been minimized.

Copy link

commented Sep 19, 2018

I find that thinking of the sequence as a sequence, i.e., a list, helps simplify the logic while also lending itself to tail recursion to avoid performance issues:

defmodule Fibonacci do
  def find(nth) do
    list = [1, 1]
    fib(list, nth)
  end

  def fib(list, 2) do
    Enum.reverse(list)
  end

  def fib(list, n) do
    fib([hd(list) + hd(tl(list))] ++ list, n - 1)
  end
end

Usage:

> find 7
[1, 1, 2, 3, 5, 8, 13]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.