Visualising recursive function calls in Elixir

README.md

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 𝑛?

counting_change.exs

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