Alright, I’ll just analyze the auxiliary space complexity of each working implementation here:
Given the tree–
# 4
# / \
# 2 8
–insert a new value, 1, using both body and tail recursion. Determine for each the time and auxiliary space complexity of this operation.
body recursion
BodyTree.insert(tree, 1)
# STACK FRAME 0
# Aux Space: 0 + other stack frames aux space
# Time: O(1) + other stack frames time
def insert(tree = tree, data = 1) do
if 1 < 4, do: %{tree | left: insert(tree.left, 1)} # ...
end
# STACK FRAME 1
# Aux Space: theta(n/2) or O(n - 1) [tree branch] + other stack frames aux space
# Time: O(1) + other stack frames time
def insert(tree = tree.left, data = 1) do
if 1 < 2, do: %{tree | left: insert(tree.left, 1)} # ...
end
# STACK FRAME 2
# Aux Space: O(1)
# Time: O(1)
def insert(nil = tree.left.left, 1), do: new(1)
In all, inserting into a body recursive BST could take at worst O(n(n-1)/2) auxiliary space if all nodes are along one branch and at worst O(n) time. On average, auxiliary space should be theta(n/2 * (n-1)/2) for a balanced tree and time should be theta(log 2 n).
tail recursion
TailTree.insert(tree, 1)
# STACK FRAME 0.0
# Aux Space: O(1)
# Time: O(1)
def insert(tree = tree, value = 1, []), do: insert(tree, 1, [])
# STACK FRAME 0.1
# Aux Space: O(n) -- adding tree to options list
# Time: O(1)
defp insert(%Tree{value: 4, left: tree.left, right: tree.right} = tree, new_value = 1, ops = []) do
cond do
4 < 1 -> # ...
true -> insert(tree.left, 1, [{:left, tree} | []]
end
end
# STACK FRAME 0.2
# Aux Space: theta(n + n/2), O(2n - 1) -- on last call, ops will be theta(n/2 * (n-1)/2) to O(n(n-1)/2)
# Time: O(1)
defp insert(%Tree{value: 2, left: :leaf, right: :leaf} = tree.left, new_value = 1, ops = [left: tree]) do
cond do
2 < 1 -> # ...
true -> insert(:leaf, 1, [{:left, tree.left} | [left: tree]]
end
end
# STACK FRAME 0.3
# Aux Space: O(1)
# Time: O(1)
defp insert(:leaf, 1, ops = [left: tree.left, left: tree]), do: insert_ops(new(1), ops)
# STACK FRAME 0.4
# Aux Space: from bottom of tree O(1) to top O(n)
# Time: O(1)
defp insert_ops(subtree = %Tree{value: 1, left: :leaf, right: :leaf}, [{side = :left, tree = tree.left} | rest = [left: tree]]),
do: insert_ops(Map.put(tree.left, :left, subtree), [left: tree])
# STACK FRAME 0.5
# Aux Space: from bottom of tree O(1) to top O(n)
# Time: O(1)
defp insert_ops(subtree = %Tree{ tree.left | left: new_node}, [{side = :left, tree = tree} | rest = []]),
do: insert_ops(Map.put(tree, :left, subtree), [])
# STACK FRAME 0.6
# Aux Space: O(1)
# Time: O(1)
defp insert_ops(tree = tree_with_insertion, []), do: tree_with_insertion
Inserting into a tail recursive BST could take at worst O(n(n-1)/2) auxiliary space if all nodes are along one branch and at worst O(n) time. On average, auxiliary space should be theta(n/2 * (n-1)/2) for a balanced tree and time should be theta(log 2 n).
So both have the same performance, albeit the operations involved in making tail recursive calls cumulatively may take longer–copying complex data structures into each new stack frame doesn’t count as extra auxiliary space but takes longer because less is copied over in each body recursive call. This can account for body recursion being 10% faster (as mentioned in the benchmarking blog post). What accounts for tail recursion not being more space efficient is the need for the options list which effectively is explicitly managing the call stack ourselves.
Personally, I find tail recursion easier to follow because it makes each recursive step explicit (whereas with body recursion, one must reason through what will happen in one’s head). However, it does introduce significantly more complex code when applied to non-primitive and non-collective data structures and comes at a slight performance cost.
That said, if performance were really paramount, the code would be written in C (or nowadays maybe Rust or Haskell).
Personally, my takeaway is to first see if there’s a straightforward body-recursive implementation. If it seems like the body recursion will be particularly complex, I will now use the strategy @peerreynders introduced–explicitly managing the call stack myself–to reason through each step. This will initially result in a tail-recursive implementation, but hopefully doing so will allow me to identify the comparatively simpler body-recursive implementation.
I.e. I’m balancing explicitness with simplicity.