Recursion

Mix.install([
  {:kino, github: "livebook-dev/kino", override: true},
  {:kino_lab, "~> 0.1.0-dev", github: "jonatanklosko/kino_lab"},
  {:vega_lite, "~> 0.1.4"},
  {:kino_vega_lite, "~> 0.1.1"},
  {:benchee, "~> 0.1"},
  {:ecto, "~> 3.7"},
  {:math, "~> 0.7.0"},
  {:faker, "~> 0.17.0"},
  {:utils, path: "#{__DIR__}/../utils"}
])

Navigation

Return Home Report An Issue

Setup

Ensure you type the ea keyboard shortcut to evaluate all Elixir cells before starting. Alternatively you can evaluate the Elixir cells as you read.

Recursion

Recursion is a function that calls itself.

flowchart LR
b[Function] --> a[Function]
a --> b

Recursion creates a loop effect where the function calls itself over and over.

defmodule Recursion do
  def loop(n) do
    if n > 0 do
      IO.puts(n)
      loop(n - 1)
    end
  end
end

Recursion.loop(5)

This calls the loop function 5 times. Under the hood, this places 5 stack frames on the stack.

We trigger a call to IO.puts/2 to show that the loop function has been called 5 times with a different argument.

flowchart LR
  a["loop(n)"]
  b["loop(n - 1)"]
  c["loop(n - 2)"]
  d["loop(n - 3)"]
  e["loop(n - 4)"]
  f["loop(...)"]
  5["loop(5)"]
  4["loop(4)"]
  3["loop(3)"]
  2["loop(2)"]
  1["loop(1)"]
  5 --> 4 --> 3 --> 2 --> 1
  a --> b --> c --> d --> e --> f

Computerphile explains recursion in excellent detail.

Kino.YouTube.new("https://www.youtube.com/watch?v=Mv9NEXX1VHc")

Endless Recursion

We should have some end condition, otherwise, this would run forever. You’ll notice that this Elixir cell never stops running. Under the hood it’s calling Forever.run/0 over and over.

defmodule Forever do
  def run do
    run()
  end
end

Forever.run()

Stack Overflow

Coming from another language, you might be surprised that the endless recursion function doesn’t crash in Elixir. In most programming languages, calling a recursive function puts too many stack frames on the stack, and causes a stack overflow.

That’s because stack memory gets too full (overflowed) storing each stack frame of the recursive call.

Tail Recursion and Tail-Call Optimization

Since functional programming languages rely so much on recursion, Elixir (and Erlang) implement tail-call optimization.

Tail-call optimization circumvents adding new stack frames, instead, it reuses the current stack frame and jumps back to the top of the stack frame. This avoids additional memory consumption.

Body Recursion

Keep in mind that Elixir can only tail-call optimize your recursive function if the last thing it does is call itself. That’s why it’s called tail recursion. Otherwise, if the function calls itself in the body, it’s called body-recursion and is not optimized.

Your Turn

Let’s prove that body-recursion is not optimized. First, open the runtime panel in this livebook. Press s then r to open the settings panel. There you can see the current memory consumption.

Next, uncomment and execute the following Elixir cell that uses body recursion. It’s a nonsense function that doesn’t do anything, however, it will infinitely call itself in the body of the function.

You’ll notice the Process memory consumption will increase, and eventually, the cell will abort. You may need to click the Connect button to reconnect the Elixir runtime.

# defmodule Body do
#   def recursion([head | tail]) do
#     recursion(tail ++ tail) ++ [head]
#   end
# end

# Body.recursion([1,2,3])

Make sure you comment out the code above, otherwise Livebook will keep disconnecting.

Using Recursion

So why is recursion useful? Well, it’s how we achieve a great deal of functionality in Elixir. For example, many functions in the Enum module use recursion under the hood.

Recursion allows us to accomplish enumeration.

For example, we could use recursion to enumerate through and sum the elements in a list.

defmodule Recursion do
  def sum(list, accumulator \\ 0) do
    case list do
      [] -> accumulator
      [head | tail] -> sum(tail, accumulator + head)
    end
  end
end

Recursion.sum([1, 2, 3], 0)

We enumerate through the list by recursively calling sum/2 on the tail of the list and building an accumulator. In this case, the initial accumulator is 0.

Each element in the list adds to the accumulator. 1 + 2 + 3 = 6 so the function returns 6.

flowchart LR
sum1["sum([1, 2, 3], 0)"]
sum2["sum([2, 3], 1)"]
sum3["sum([3], 3)"]
sum4["sum([], 6)"]

sum1 --> sum2 --> sum3 --> sum4 --> 6

Walking through the function we bind list to [1, 2, 3] and accumulator to 0.

  def sum(list, accumulator) do
    case list do
      # [] -> accumulator
      [head | tail] -> sum(tail, accumulator + head)
    end
  end

list is not empty so the program recursively calls sum([2, 3], 0 + 1).

  def sum([1, 2, 3], 0) do
    case [1, 2, 3] do
      # [] -> accumulator
      [1 | [2, 3]] -> sum([2, 3], 0 + 1)
    end
  end

list is still not empty, so the program recursively calls sum([3], 1 + 2).

  def sum([2, 3], 1) do
    case [2, 3] do
      # [] -> accumulator
      [2 | [3]] -> sum([3], 1 + 2)
    end
  end

list is still not empty, so the program recursively calls sum([], 3 + 3).

  def sum([3], 3) do
    case [3] do
      # [] -> accumulator
      [3 | []] -> sum([], 3 + 3)
    end
  end

list is empty, so the program returns the accumulator (6).

  def sum([],  6) do
    case [] do
      [] -> 6
      # [head | tail] -> sum(tail, accumulator + head)
    end
  end

Rather than using case statements, it’s common to use different function clauses to handle the base case. The base case is when the function returns a value instead of making a recursive call.

In the Recursion module, the base case is when the list is empty and sum/2 returns the accumulator.

With multiple function clauses, the Recursion module could instead be implemented like so:

defmodule Recursion do
  def sum([], accumulator), do: accumulator
  def sum([head | tail], accumulator), do: sum(tail, accumulator + head)
end

Recursion.sum([1, 2, 3], 0)

Your Turn

In the Elixir cell below, implement a CustomEnum.map/2 function for lists using recursion. Do not use the Enum module.

CustomEnum.map([1, 2, 3], fn each -> each * 2 end)
[2, 4, 6]

defmodule CustomEnum do
  def map(list, function) do
  end
end

Utils.feedback(:custom_enum_map, CustomEnum)

Commit Your Progress

Run the following in your command line from the project folder to track and save your progress in a Git commit.

$ git add .
$ git commit -m "finish recursion section"