Skip to content

Instantly share code, notes, and snippets.

@bitwalker
Created March 29, 2016 17:34
Show Gist options
  • Save bitwalker/a4035c870196ae8f628cefad7cbc83bc to your computer and use it in GitHub Desktop.
Save bitwalker/a4035c870196ae8f628cefad7cbc83bc to your computer and use it in GitHub Desktop.
How a body recursive function expands in Elixir
# This is our function definition,
# It is body (not tail) recursive, as it must wait for
# len(tail) to return before the addition can be performed
# on each iteration
def len([]), do: 0
def len([head | tail]), do: 1 + len(tail)
# If we call len([1, 2, 3]), this is what happens
len([1, 2, 3]) == 1 + len([2, 3])
len([2, 3]) == 1 + len([3])
len([3]) == 1 + len([])
len([]) == 0
# Or put another way
len([1, 2, 3]) == 1 + len([2,3]) + len([3]) + len([])
# Expanded..
len([1, 2, 3]) == 1 + 1 + 1 + 0
# Result..
len([1, 2, 3]) == 3
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment