Skip to content

Instantly share code, notes, and snippets.

@tiagopog
Last active July 11, 2018 13:20
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save tiagopog/d3ad700d3a6a693b55b4f004baf69875 to your computer and use it in GitHub Desktop.
Save tiagopog/d3ad700d3a6a693b55b4f004baf69875 to your computer and use it in GitHub Desktop.
Elixir - Body-recursion vs Tail-Recursion for Fibonacci
# Body-recursive
#
# Note: "+" is actually the last call, not calculate/1.
defmodule Fibonacci do
def calculate(x) when x <= 2, do: 1
def calculate(x), do: calculate(x - 1) + calculate(x - 2)
end
# Tail-recursive (Tail Call Optimization)
#
# Note: tail-recursion is triggered since do_calculate/3 calls itself
# at the very end of the function.
defmodule FibonacciTCO do
def calculate(x), do: do_calculate(0, 1, x)
def do_calculate(_, result, 1), do: result
def do_calculate(a, b, x), do: do_calculate(b, a + b, x - 1)
end
Fibonacci.calculate(40) |> IO.puts
FibonacciTCO.calculate(40) |> IO.puts
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment