Recursion

Mix.install([
  {:jason, "~> 1.4"},
  {:kino, "~> 0.9", override: true},
  {:youtube, github: "brooklinjazz/youtube"},
  {:hidden_cell, github: "brooklinjazz/hidden_cell"}
])

Navigation

Review Questions

Upon completing this lesson, a student should be able to answer the following questions.

• How do we use recursive functions to accomplish enumeration or traverse some data structure until it’s empty?
• What are the performance impacts of tail-recursion vs body-recursion?

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 RecursiveLoop do
  def loop(n) do
    if n > 0 do
      IO.puts(n)
      loop(n - 1)
    end
  end
end

RecursiveLoop.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.

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 RecursiveSum do
  def sum(list, accumulator \\ 0) do
    case list do
      [] -> accumulator
      [head | tail] -> sum(tail, accumulator + head)
    end
  end
end

RecursiveSum.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

Base Cases

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 BaseCaseExample do
  def sum([], accumulator), do: accumulator
  def sum([head | tail], accumulator), do: sum(tail, accumulator + head)
end

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

Your Turn

Create a CountDown module which uses recursion to print all of the values between the provided integer and 0.

CountDown.count(5)

The above would print:

5
4
3
2
1
0

Example Solution

defmodule CountDown do
  def count(0), do: IO.puts(0)
  def count(n) do
    IO.puts(n)
    count(n - 1)
  end
end

Your Turn

Create a CountBetween module which counts up between a starting integer and a finish integer.

CountBetween.count(2, 5)

The above would print:

2
3
4
5

The CountBetween module should handle when the start is greater than the finish.

CountBetween.count(10, 5)

The above would print:

10
9
8
7
6
5

Example Solution

defmodule CountBetween do
  def count(finish, finish), do: IO.puts(finish)
  def count(start, finish) when start < finish do
    IO.puts(start)
    count(start + 1, finish)
  end

    def count(start, finish) when start > finish do
    IO.puts(start)
    count(start - 1, finish)
  end
end

Commit Your Progress

DockYard Academy now recommends you use the latest Release rather than forking or cloning our repository.

Run git status to ensure there are no undesirable changes. Then run the following in your command line from the curriculum folder to commit your progress.

$ git add .
$ git commit -m "finish Recursion reading"
$ git push

We’re proud to offer our open-source curriculum free of charge for anyone to learn from at their own pace.

We also offer a paid course where you can learn from an instructor alongside a cohort of your peers. We will accept applications for the June-August 2023 cohort soon.

Navigation