Skip to content

Latest commit

 

History

History
366 lines (269 loc) · 10.3 KB

recursion.livemd

File metadata and controls

366 lines (269 loc) · 10.3 KB
Raw

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 programming technique where a function calls itself. This creates a looping effect until some exit condition is met.

Here's an example of a recursive loop that counts down from some integer.

defmodule Recursion do
  def loop(count) do
    if count <= 0 do
      IO.puts(count)
    else
      IO.puts(count)
      loop(count - 1)
    end
  end
end

Recursion.loop(5)

This calls the loop function 5 times. Under the hood, this places 5 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
Loading

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

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 by traversing through data structures. It also enables the preservation of state between function calls.

Here's an example of a recursive function sum/2 that traverses through a list and preserves an accumulator. It looks at every element in the list and adds it to the current accumulator to calculate the sum of all of the elements in the list. When the list is empty, it returns the final accumulator.

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
Loading

Base Cases

Recursive functions often have a base case (also sometimes called an exit condition) where they will stop running and return some value.

Here's another example of the sum/2 function, this time using multiple function clauses to separate out the base case into a separate function call that returns the accumulator.

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
defmodule CountDown do
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
defmodule CountBetween do
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