{{ message }}

Instantly share code, notes, and snippets.

Last active Dec 29, 2020
Visualising recursive function calls in Elixir

# Visualising recursive function calls in Elixir

For SICP Exercise 1.14 in Elixir, we'll first implement the `count_change/1` function, which calculates how many different ways there are to make change using half-dollars (50 ¢), quarters (5 ¢), dimes (5 ¢) and pennies (1 ¢) for any given amount of money.

``````iex -r counting_change.exs
Erlang/OTP 23 [erts-11.0.2] [source] [64-bit] [smp:8:8] [ds:8:8:10] [async-threads:1] [hipe]

Interactive Elixir (1.12.0-dev) - press Ctrl+C to exit (type h() ENTER for help)
iex(1)> Counter.count_change(1)
1
iex(2)> Counter.count_change(5)
2
iex(3)> Counter.count_change(10)
4
iex(4)> Counter.count_change(25)
13
iex(5)> Counter.count_change(50)
50
``````

In general, the number of steps required by a tree-recursive process will be proportional to the number of nodes in the tree, while the space required will be proportional to the maximum depth of the tree.

To get an idea of the time and space required to run the function, we'll count the number recursive steps to draw a tree illustrating the generated process by adding `Complexity.with_complexity/1`, a function that counts the calls to the wrapped function:

``````iex -r counting_change.exs
Erlang/OTP 23 [erts-11.0.2] [source] [64-bit] [smp:8:8] [ds:8:8:10] [async-threads:1] [hipe]

Interactive Elixir (1.12.0-dev) - press Ctrl+C to exit (type h() ENTER for help)
iex(1)> Counter.count_change(11)
Elixir.Counter.do_count_change(11, 5) {
Elixir.Counter.do_count_change(11, 4) {
Elixir.Counter.do_count_change(11, 3) {
Elixir.Counter.do_count_change(11, 2) {
Elixir.Counter.do_count_change(11, 1) {
Elixir.Counter.do_count_change(11) {
}=> 0
Elixir.Counter.do_count_change(10, 1) {
Elixir.Counter.do_count_change(10) {
}=> 0
Elixir.Counter.do_count_change(9, 1) {
Elixir.Counter.do_count_change(9) {
}=> 0
Elixir.Counter.do_count_change(8, 1) {
Elixir.Counter.do_count_change(8) {
}=> 0
Elixir.Counter.do_count_change(7, 1) {
Elixir.Counter.do_count_change(7) {
}=> 0
Elixir.Counter.do_count_change(6, 1) {
Elixir.Counter.do_count_change(6) {
}=> 0
Elixir.Counter.do_count_change(5, 1) {
Elixir.Counter.do_count_change(5) {
}=> 0
Elixir.Counter.do_count_change(4, 1) {
Elixir.Counter.do_count_change(4) {
}=> 0
Elixir.Counter.do_count_change(3, 1) {
Elixir.Counter.do_count_change(3) {
}=> 0
Elixir.Counter.do_count_change(2, 1) {
Elixir.Counter.do_count_change(2) {
}=> 0
Elixir.Counter.do_count_change(1, 1) {
Elixir.Counter.do_count_change(1) {
}=> 0
Elixir.Counter.do_count_change(1) {
}=> 1
}=> 1
}=> 1
}=> 1
}=> 1
}=> 1
}=> 1
}=> 1
}=> 1
}=> 1
}=> 1
}=> 1
Elixir.Counter.do_count_change(6, 2) {
Elixir.Counter.do_count_change(6, 1) {
Elixir.Counter.do_count_change(6) {
}=> 0
Elixir.Counter.do_count_change(5, 1) {
Elixir.Counter.do_count_change(5) {
}=> 0
Elixir.Counter.do_count_change(4, 1) {
Elixir.Counter.do_count_change(4) {
}=> 0
Elixir.Counter.do_count_change(3, 1) {
Elixir.Counter.do_count_change(3) {
}=> 0
Elixir.Counter.do_count_change(2, 1) {
Elixir.Counter.do_count_change(2) {
}=> 0
Elixir.Counter.do_count_change(1, 1) {
Elixir.Counter.do_count_change(1) {
}=> 0
Elixir.Counter.do_count_change(1) {
}=> 1
}=> 1
}=> 1
}=> 1
}=> 1
}=> 1
}=> 1
Elixir.Counter.do_count_change(1, 2) {
Elixir.Counter.do_count_change(1, 1) {
Elixir.Counter.do_count_change(1) {
}=> 0
Elixir.Counter.do_count_change(1) {
}=> 1
}=> 1
Elixir.Counter.do_count_change(2, -4) {
}=> 0
}=> 1
}=> 2
}=> 3
Elixir.Counter.do_count_change(1, 3) {
Elixir.Counter.do_count_change(1, 2) {
Elixir.Counter.do_count_change(1, 1) {
Elixir.Counter.do_count_change(1) {
}=> 0
Elixir.Counter.do_count_change(1) {
}=> 1
}=> 1
Elixir.Counter.do_count_change(2, -4) {
}=> 0
}=> 1
Elixir.Counter.do_count_change(3, -9) {
}=> 0
}=> 1
}=> 4
Elixir.Counter.do_count_change(4, -14) {
}=> 0
}=> 4
Elixir.Counter.do_count_change(5, -39) {
}=> 0
}=> 4
--------------------------------------------------------------------------------
Total steps (∝ time):    55
Maximum depth (∝ space): 16
--------------------------------------------------------------------------------
4
``````

## Notes

1. Outside of helping to determine the order of growth for a procedure, would something like this be useful for debugging or understanding recursive functions?
2. Can we implement something like this without having to alter the functions themselves by attaching it after they're compiled?
• Using Erlang's tracer functions comes to mind, but I think they only include the functions' arities, not the arguments themselves.
• Using decorators would almost work to not have to update the functions themselves. We'd still need to add the decorator call to the module, though.
3. Can we use something like this to graph the growth of a function's time and space use with an increasing 𝑛?
 defmodule Complexity do defmacro with_complexity(fun) do quote do arguments = binding() |> Keyword.values() |> Enum.map(&inspect/1) |> Enum.join(", ") {function, _arity} = __ENV__.function [{:current, current} | _] = Complexity.get() indentation = String.duplicate(" ", current) start() IO.puts("#{indentation}#{__MODULE__}.#{function}(#{arguments}) {") return = unquote(fun).() IO.puts("#{indentation}}=> #{return}") finish() return end end def start() do [current: current, steps: steps, space: space] = get() new_current = current + 1 new_complexity = [ current: new_current, steps: steps + 1, space: if(new_current > space, do: new_current, else: space) ] Process.put(:complexity, new_complexity) end def finish() do case get() do [{:current, 1}, {:steps, steps}, {:space, space}] -> IO.puts(String.duplicate("-", 80)) IO.puts("Total steps (∝ time): #{steps}") IO.puts("Maximum depth (∝ space): #{space}") IO.puts(String.duplicate("-", 80)) Process.delete(:complexity) [{:current, current} | _] = complexity -> new_complexity = Keyword.put(complexity, :current, current - 1) Process.put(:complexity, new_complexity) end end def get() do Process.get(:complexity, current: 0, steps: 0, space: 0) end end defmodule Counter do import Complexity def count_change(amount) do do_count_change(amount, 5) end defp do_count_change(0, _kinds_of_coins) do with_complexity(fn -> 1 end) end defp do_count_change(amount, _kinds_of_coins) when amount < 0 do with_complexity(fn -> 0 end) end defp do_count_change(_amount, 0) do with_complexity(fn -> 0 end) end defp do_count_change(amount, kinds_of_coins) do with_complexity(fn -> do_count_change(amount, kinds_of_coins - 1) + do_count_change(amount - first_denomination(kinds_of_coins), kinds_of_coins) end) end defp first_denomination(1), do: 1 defp first_denomination(2), do: 5 defp first_denomination(3), do: 10 defp first_denomination(4), do: 25 defp first_denomination(5), do: 50 end