Skip to content

Instantly share code, notes, and snippets.

@jeffkreeftmeijer

jeffkreeftmeijer/README.md

Last active Dec 29, 2020
Embed
What would you like to do?
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment