Recursive Sum


Category: Code
Tags:  Ruby recursion

In #ruby on Freenode, platzhirsch asked about how to total an array of Transactions when the Transactions may have parents. The two obvious approaches have pitfalls when there are a lot of Transactions, and he said he expects to have 23 million that may be deeply nested. Here’s his sample code:

class Transaction attr_accessor :amount, :parent

def initialize(amount, parent) self.amount = amount self.parent = parent end end

t1 = Transaction.new(100, nil) t2 = Transaction.new(250, t1) t3 = Transaction.new(300, t2)

current = t3 all = [] while current != nil all << current current = current.parent end total = all.inject(0) { |total, transaction| total + transaction.amount }

Spoiler warning: last chance to solve it for yourself before I dig into the solutions.

This code sample expressed the first obvious solution: build a list of all the transactions. The problem is that you’ll spend RAM and time building a data structure you expect to use once.

One person offered an addition to Transaction to solve it recursively, the second obvious approach:

` class Transaction def total_amount (parent ? parent.total_amount : 0) + amount end end `{lang=”ruby”}

This pitfall is that this risks blowing the stack when Transactions are deeply nested: recurse too many times and you’ll run out of RAM. It’s also super-specialized, if you want to do anything else with every Transaction you’ll have to write another custom method. And despite the specialization, you might end up writing this logic again if you have a collection of child transactions:

t4 = Transaction.new(400, nil)

total = [t3, t4].inject(0) { |sum, t| sum + t.amount }

Here’s my approach:

# because Transaction doesn’t have any logic, I made a shorter version: Transaction = Struct.new(:amount, :parent)

# And I like using powers of two when testing recursion, because the sum # will come out obviously different for different combinations of items: t1 = Transaction.new 1, nil t2 = Transaction.new 2, t1 t3 = Transaction.new 4, t2 t4 = Transaction.new 8, nil

TransactionEnumerator = Struct.new(:collection) do include Enumerable

def each collection.each do |t| yield t yield t while t = t.parent end end end

ts = TransactionEnumerator.new [t3, t4] total = ts.inject(0) { |total, transaction| total + transaction.amount }

This little wrapper doesn’t recurse, doesn’t duplicate Transactions, and doesn’t build a data structure. It can work on any collection of Transactions that exposes each, the sum logic is expressed only once and separately from the control flow, and it provides the powerful Ruby Enumerable interface.

Hope you enjoyed this little puzzle! If you had an alternate solution, please wrap it in <code></code> tags below.

And let me tag on my own fun exercise: add an ID field to Transaction and implement TransactionEnumerator#uniq yield the transactions exactly once, so this returns true (Array has #uniq, but you shouldn’t assume the collection is an Array):

` TransactionEnumerator.new([t1, t1]).uniq == [t1] `{lang=”ruby”}