我有这个面试问题，我无法解决。我坐下来思考过，但我仍然想不出该怎么做。
我有3种方法。我想使用递归将 2 个数字加在一起，所以我不能使用任何算术运算符，如 +、- 等。
这 3 个方法是 Sum、Add1、Sub1。
Add1 将 1 个整数作为参数并以 1 的增量返回该整数。 Sub1 执行相同的操作，但减 1。
Sum 方法采用 2 个整数并使用递归返回 2 个输入整数的总和。展示实现。
此外，使用 Sum 函数如何实现一个新函数，该函数将 2 个整数作为输入并使用递归但不使用算术运算符输出它们的乘积？
在这两种情况下，整数都是非负数。
这实际上是从第一原理定义自然数算术的方式；见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 是一个。如果我们不知道问题的解决方案，那么我们会提出一个较小的问题；如果我们采用第二个加法的先行者，那么我们离我们知道如何解决的问题又近了一步。
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));
}
我讨厌这类面试问题，因为我发现在面试的相关压力下很难回答。
这里是 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));
}
你可以直接实现这个类，它适用于任何类型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();
}
}
嗯..他们是在试图雇用糟糕的程序员吗？无论如何，可以通过让 sum 函数获取它的第二个参数、加/减 1 并调用自身来完成。
sum(arg1,arg2)
{
if(arg2>0)
{
new1=Add1(arg1)
new2=Sub1(arg2)
return sum(new1,new2)
}
else{return arg1;}
}
递归函数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));
}