Recursion to create a sum method

Question

I had this for an interview, and I could not solve it. I sat and thought about it, but I still can’t figure out how to do it.

I have 3 methods. I suppose adding 2 numbers together using recursion, so I cannot use any arithmetic operators like +, -, etc.

3 methods: Sum, Add1, Sub1.

Add1 takes 1 integer as a parameter and returns this integer in increments of 1. Sub1 does the same, but decrement 1.

The Sum method takes 2 integers, and using recursion, it returns the sum of two input integers. Show 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 does not have arithmetic operators?

In both cases, the integers are non-negative.

Answer 1

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 2

This is actually how the arithmetic of natural numbers is determined from first principles; see http://en.wikipedia.org/wiki/Peano_axioms

Let's do it from scratch, why not?

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

Easy 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(); } 

Well, we can represent any integer like this. Now how do we make an addition? We define the 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(); } } 

Well, let him try.

 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 are actually four.

If this topic interests you, I am currently launching a long series on my blog that I get natural and whole arithmetic from scratch, although I use a binary representation rather than a unary representation. Cm.

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

More generally: the question is intended to verify whether you know the basic structure of a recursive method; perhaps you will not 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 so, solve the problem and return the result.
• We do not know the solution to the problem. Divide the problem into one or more smaller problems. Reduction should create problems that are actually smaller, which is closer to a problem that has a known solution. Otherwise, the recursion does not end.
• Solve each problem recursively.
• Combine solutions to these problems to create a solution to a larger problem.
• Return the result.

This is what we do in the add statement. First we check if we know the solution to the problem; a + 0 is a. If we do not know the solution to the problem, we make the smaller problem; if we take the predecessor of the second term, then we are one step closer to the problem that we know how to solve.

Answer 3

Recursive Sum function:

 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

Hmm .. are they trying to hire bad programmers? In any case, this can be done if the sum function accepts its other arguments, adds / decreases 1, and calls itself.

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

Answer 5

I hate such interviews because I find them very difficult to respond under the appropriate pressure of the interview.

Here is Add1, Sub1, Sum, Product all done without the 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 6

You can simply implement this class in a simple 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 == xn; } public override string ToString() { return n.ToString(); } }