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

You can just implement this class in a straightforward way and it will work for any type T.

public abstract class Summable<T>
{
    public abstract Summable<T> Add1();
    public abstract Summable<T> Sub1();

    public abstract Summable<T> Zero { get; } //Identity for addition
    public abstract Summable<T> One { get; } //Identity for multiplication

    public abstract bool Equals(Summable<T> other);

    public abstract override string ToString();

    public static Summable<T> Sum(Summable<T> x, Summable<T> y)
    {
        if (y == y.Zero)
            return x;

        if (x == y.Zero)
            return y;

        else
            return Sum(x.Add1(), y.Sub1());
    }

    public static Summable<T> Multiply(Summable<T> x, Summable<T> y)
    {
       var zero = x.Zero;
        var one = x.One;

        if (x == zero || y == zero)
            return zero;

        if (y == one)
            return x;
        if (x == one)
            return y;

        return Sum(x, Multiply(x, y.Sub1()));
    }

    public static bool Equal(Summable<T> x, Summable<T> y)
    {
        if (object.ReferenceEquals(x, null) || object.ReferenceEquals(y, null))
            return false;

        return x.Equals(y);
    }

    public static bool operator ==(Summable<T> x, Summable<T> y)
    {
        return Equal(x, y);
    }

    public static bool operator !=(Summable<T> x, Summable<T> y)
    {
        return !Equal(x, y);
    }
}

So for ints (or probably uints) it would be something like this:

public sealed class Int : Summable<int>
{
    protected int n;

    public Int(int n)
    {
       if(n < 0)
           throw new ArgumentException("n must be a non negative."); 

       this.n = n;
    }

    public override Summable<int> Add1()
    {
        return new Int(n + 1);
    }

    public override Summable<int> Sub1()
    {
        return new Int(n - 1);
    }

    public override Summable<int> Zero
    {
        get
        {
            return new Int(0);
        }
    }

    public override Summable<int> One
    {
        get
        {
            return new Int(1);
        }
    }

    public override bool Equals(Summable<int> other)
    {
        var x = other as Int;

        if (Object.ReferenceEquals(x, null))
            return false;

        return this.n == x.n;
    }

    public override string ToString()
    {
        return n.ToString();
    }
}

Answer 2

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.

Answer 3

Recursive function Sum:

int Sum(int n1, int n2) {
  if (n2 == 0) return n1;
  return Sum(add1(n1), sub1(n2));
}

And Prod:

int Prod(int n1, int n2) {
  if(n1 == 1) return n2;
  if(n2 == 1) return n1;
  n2 = Sub(n2);
  return Sum(n1, Prod(n1, n2));
}

Answer 4

I hate these sorts of interview questions because I find them very hard to answer under the associated pressures of an interview.

Here is Add1, Sub1, Sum, Product all done without any formal use of the + or - symbol.

    static int Add1(int value) {
        return System.Threading.Interlocked.Increment(ref value);
        }

    static int Sub1(int value) {
        return System.Threading.Interlocked.Decrement(ref value);
        }

    static int Sum(int value1, int value2) {
        return RecursiveAdd(value1, value2);
        }

    static int Product(int value1, int value2) {
        return RecursiveProduct(value1, value2);
        }

    static int RecursiveAdd(int v1, int v2) {
        if (v2 == 0) { return v1; }
        v2 = Sub1(v2);
        v1 = Add1(v1);
        return RecursiveAdd(v1, v2);
        }

    static int RecursiveProduct(int v1, int v2) {
        if (v2 == 0) { return 0; }
        v2 = Sub1(v2);
        return RecursiveAdd(v1, RecursiveProduct(v1, v2));
        }

Answer 5

Add1(value) {
  return value + 1;
}

Sub1(value) {
  return value - 1;
}

Sum(value1 , value2) {
   if(value2 == 0) {
       return value1;
   }
   value1 = Add1(value1);
   value2 = Sub1(value2);
   return Sum(value1, value2);
}

Prod(value1, value2) {
    if(value2 == 0) {
       return 0;
   }
   value2 = Sub1(value2);

   return Sum(value1, Prod(value1, value2));
}

Answer 6

Hmm.. are they trying to hire bad programmers? In any event, could be done by having the sum function take its second arguments, add/decrement 1 and call itself.

sum(arg1,arg2)
{
if(arg2>0)
{
new1=Add1(arg1)
new2=Sub1(arg2)
return sum(new1,new2)
}
else{return arg1;}
}