Recursion to create a Sum Method

Question

I had this for an interview question and I couldn't solve it. I have sat and thought on it but I still can't think of how to do it.

I have 3 methods. I am suppose to add 2 numbers together using recursion so I can't use any arithmetic operators like +, -, etc.

The 3 methods are Sum, Add1, Sub1.

Add1 takes 1 integer as parameter and returns that integer with increment of 1. Sub1 does same thing but decrement of 1.

Sum method takes 2 integers and using recursion it returns the sum of the 2 input integers. Show the implementation.

Also, using the Sum function how can you implement a new function that takes 2 integers as input and outputs their product using recursion but no arithmetic operators?

In both cases the integers are non-negative.

Answer 1

This is in fact how natural number arithmetic is defined from first principles; see http://en.wikipedia.org/wiki/Peano_axioms

Let's do this from scratch why don't we?

• Zero is a natural
• Zero has no predecessor
• Every natural has a successor

Easily done:

sealed class Natural
{
  private Natural predecessor;
  private Natural(Natural predecessor) 
  { 
      this.predecessor = predecessor;
  }

  // Zero has no predecessor
  public readonly static Natural Zero = new Natural(null);

  // Every number has a successor; the predecessor of that number is this number. 
  public Natural Successor() 
  { 
      return new Natural(this);
  }
  public Natural Predecessor()
  {
      return this.predecessor;
  }
  public override string ToString()
  {
    if (this == Zero) 
        return "0";
    else 
        return "S" + this.Predecessor().ToString();
  }

All right, we can represent any integer like this. Now how do we do addition? We define addition as:

a + 0 --> a
a + S(b) --> S(a + b)

So let's add an operator

  public static Natural operator+(Natural a, Natural b)
  {
    if (b == Zero) 
      return a;    
    else
      return (a + b.Predecessor()).Successor();
  }
}

All right, let's try it.

Natural n0 = Natural.Zero;
Natural n1 = n0.Successor();
Natural n2 = n1.Successor();
Console.WriteLine(n0 + n0);
Console.WriteLine(n0 + n1);
Console.WriteLine(n0 + n2);
Console.WriteLine(n1 + n0);
Console.WriteLine(n1 + n1);
Console.WriteLine(n1 + n2);
Console.WriteLine(n2 + n0);
Console.WriteLine(n2 + n1);
Console.WriteLine(n2 + n2); // SSSS0

And there you go, two plus two is in fact four.

If this subject interest you I am at present running a long series on my blog on deriving natural and integer arithmetic from scratch, though I am using a binary representation rather than a unary representation. See

http://ericlippert.com/2013/09/16/math-from-scratch-part-one/

More generally: the question is intended to test whether you know the basic structure of a recursive method; possibly you do not so let me lay it out for you. Recursive methods in C# all follow this pattern:

• Do we already know the solution to the problem without recursion? If yes, then solve the problem and return the result.
• We do not know the solution to the problem. Break the problem down into one or more smaller problems. The reduction must make problems that are actually smaller, that is closer to a problem that has a known solution. Otherwise the recursion doesn't terminate.
• Solve each problem recursively.
• Combine the solutions to those problems to create a solution to the larger problem.
• Return the result.

That's what we do in the addition operator. We first check if we know the solution to the problem; a + 0 is a. If we don't know the solution to the problem then we make a smaller problem; if we take the precedessor of the second summand then we are one step closer to a problem we know how to solve.