Рекурсия для создания метода сумм

Question

У меня было это для интервью, и я не мог его решить. Я сидел и думал об этом, но я все еще не могу придумать, как это сделать.

У меня есть 3 метода. Я предполагаю добавить 2 числа вместе, используя рекурсию, поэтому я не могу использовать любые арифметические операторы, такие как +, - и т. Д.

3 метода - это Sum, Add1, Sub1.

Add1 занимает 1 целое число в качестве параметра и возвращает целое число с приращением 1. SUB1 делает то же самое, но декремента 1.

метод Sum занимает 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); 
    } 
} 

Так что для Интс (или, возможно, uints), было бы что-то вроде этого:

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