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

ThomasBracher 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

dhc02 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.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.