递归创建总和方法

Question

我有这个面试问题，我无法解决它。我已经坐下来思考，但我仍然想不起如何去做。

我有3种方法。我想使用递归将2个数字一起添加，所以我不能使用任何算术运算符，如+， - 等。

3种方法是Sum，Add1，Sub1。

ADD1需要1个整数作为参数并返回1. SUB1的增量该整数做同样的事情，但1.

萨姆方法的减量需要2点的整数，并使用递归它返回2个输入整数的总和。显示实施。

此外，使用Sum函数如何实现一个新函数，该函数将2个整数作为输入并使用递归输出其产品，但不使用算术运算符？

在这两种情况下，整数都是非负数。

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

递归函数Sum：

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

而且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 3

嗯..他们试图雇佣程序员不好？在任何情况下，都可以通过使sum函数接受第二个参数，添加/减少1并调用它自己来完成。

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

Answer 4

这实际上是如何根据第一原理定义自然数算术的;见http://en.wikipedia.org/wiki/Peano_axioms

让我们从头开始做，为什么不呢？

• 零是一个自然
• 零没有前
• 每个自然有一个继任

容易实现：

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

好了，我们可以表示类似的任意整数这个。现在我们该如何做补充？我们定义为除：

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

因此，让我们添加运算符

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

好吧，让我们试试吧。

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 

而且你去了，两个加两个其实是四个。

如果本主题感兴趣，我目前在我的博客上运行了一系列关于从头开始自然和整数算术运算的系列文章，尽管我使用二进制表示而不是一元表示。见

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

更普遍的：问题是用来测试你是否知道递归方法的基本结构;可能你不会让我为你安排它。 C＃中的递归方法都遵循以下模式：

• 我们是否已经知道无递归问题的解决方案？如果是，则解决问题并返回结果。
• 我们不知道解决问题的方法。将问题分解成一个或多个较小的问题。减少必须使问题实际上是更小，即更接近于已知解决方案的问题。否则，递归不会终止。
• 递归地解决每个问题。
• 结合这些问题的解决方案，为更大的问题创建解决方案。
• 返回结果。

这就是我们在加法运算符中所做的。我们首先检查我们是否知道问题的解决方案; a + 0是a。如果我们不知道解决问题的方法，那么我们就会犯一个小问题;如果我们采用第二个加数的先驱，那么我们离我们知道如何解决的问题更近一步。

Answer 5

我讨厌这类面试问题，因为我发现他们很难在面试的相关压力下回答。

这里是Add1，Sub1，Sum，Product都没有正式使用+或 - 符号。

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

你可以直接实现这个类，它可以用于任何类型的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); 
    } 
} 

所以对于整数（或可能的uint）这将是这样的：

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