Elixir fibonacci #1

fib.exs

defmodule Fib do 
  def fib(0) do 0 end
  def fib(1) do 1 end
  def fib(n) do fib(n-1) + fib(n-2) end
end

IO.puts Fib.fib(10)

Thanks for this example! 🚀

one issue with this version is that it is not tail-call-optimized

This one is tail call optimized :)

defmodule Fib do
  def fib(a, _, 0 ) do a end

  def fib(a, b, n) do fib(b, a+b, n-1) end

end
IO.puts Fib.fib(1,1,6)

defmodule Fib do
defp fib(0) do 0 end
defp fib(1) do 1 end
defp fib(n) when n>=0 do
fib(n-1) + fib(n-2)
end
def fibo(x) do
for n<-0..x-1 , do: fib(n)
end
end
Output:
iex(1)>Fib.fibo(4)
[0, 1, 1, 2]

An idiomatic take on this topic :)

defmodule Fib do
    def fib(a, b, n) do
        case n do
            0 ->
                a
            _ ->
                fib(b, a+b, n-1)
        end
    end
end
# Console Output
IO.puts Fib.fib(1,1,7)

Another approach that returns the entire sequence as a list.

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]

A little optimization to @dhc02's approach, which removes ++ operation to list as it's less performant and uses pattern matching for finding the first two elements of the list.

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
    [first_elem, second_elem | _] = list
    fib([first_elem + second_elem | list], n - 1)
  end
end

My two takes using dynamic programming:

defmodule FibDynamicProgramming do
  def fib(n) do
    cache = %{0 => 0, 1 => 1}

    cache =
      Enum.reduce(2..n, cache, fn
        i, acc ->
          Map.put(acc, i, acc[i-2] + acc[i-1])
      end)

    cache[n]
  end
end

IO.inspect(FibDynamicProgramming.fib(10))
55

defmodule FibDynamicProgrammingAgent do
  use Agent

  def start_link(_) do
    Agent.start_link(fn -> %{} end, name: __MODULE__)
  end

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

    for i <- 2..n do
      put(i, get(i-2) + get(i-1))
    end

    get(n)
  end

  defp get(n), do: Agent.get(__MODULE__, fn state -> state[n] end)

  defp put(n, val), do: Agent.update(__MODULE__, fn state -> Map.put(state, n, val) end)
end

FibDynamicProgrammingAgent.start_link(nil)
IO.inspect(FibDynamicProgrammingAgent.fib(10))
55

My take on the issue, heavily inspired by @luizdamim:

defmodule Fibonacci.Map do
    def compute(n) do
      compute(2, n, %{0 => 0, 1 => 1})
    end

    def compute(n, target, map) when n == target do
      map[n - 1] + map[n - 2]
    end

    def compute(n, target, map) do
      value = map[n - 1] + map[n - 2]
      newMap = Map.put(map, n, value)
      compute(n + 1, target, newMap)
    end
  end

@edoardocostantinidev in your examples, does Map function works as same in python or c++? i never try Elixir and im learning from scratch.

@YesIIBr0 Map in this case is data structure that in elixir is documented by this page. Is basically a key-value store

My take with tail call optimization:

defmodule Fibonacci do
  def nth(n) when n <= 1, do: n

  def nth(n) do
    fib(n - 2, 1, 0)
  end

  defp fib(0, minus_1, minus_2) do
    minus_1 + minus_2
  end

  defp fib(n, minus_1, minus_2) do
    fib(n - 1, minus_1 + minus_2, minus_1)
  end
end

I'd never put my version in lol

#!/usr/bin/env elixir

defmodule Fibonacci do
  def nth([n]) when is_binary(n), do: nth(String.to_integer(n)) 
  def nth(n) when n < 1, do: {:error, :undefined}
  def nth(1), do: 0
  def nth(n), do: nth(1, 0, n - 2)
  def nth(last, _last_last, 0), do: last
  def nth(last, last_last, current), do: nth(last + last_last, last, current - 1)
end

# inline "tests"
0 = Fibonacci.nth(1)
2 = Fibonacci.nth(4)
21 = Fibonacci.nth(9)

IO.puts Fibonacci.nth(System.argv())

defmodule Fibonacci do
  def find(n) do
    list = [1, 0]
    fib(list, n)
  end
  
  def fib(_list, n) when n < 0 do
    []
  end

  def fib(_list, 0) do
    [0]
  end

  def fib(list, 1) do
    list
  end

  def fib(list, n) do
    [first_elem, second_elem | _] = list
    fib([first_elem + second_elem | list], n - 1)
  end
end

10 |> Fibonacci.find() |> IO.inspect()

defmodule Fib do
    def run(a, b, n) do
        case n do
            1 ->
                b
            _ ->
                run(b, a + b, n - 1)
        end
    end
end

Fib.run(0,1,10) |> IO.puts()