You say addition is O(n^2), but I think you can write an O(n) addition with only increment, recursion, and equality testing.

In Python syntax:

  def add(a, b):
    return add_r(a, b, 0)

  def add_r(a, b, c):
    if b == c: 
      return a
    else:
      return add_r(a, b, c+1) +1