Использование рекурсии для суммирования чисел

Question

Я только что изучал концепцию рекурсии и подумал, что попробую простой пример. В следующем коде я пытаюсь взять числа: 1, 2, 3, 4, 5 и сложить их вместе, используя рекурсию. Я ожидал, что результат будет 15, но мой код возвращает 16.

Что я делаю не так?

Код:

    static void Main(string[] args)
    {

        Console.WriteLine(Sum(5));
        Console.Read();
    }


    static int Sum(int value)
    {
        if (value > 0)
        {
          return value + Sum(value - 1);
        }
        else
        {
            return 1;
        }
    }

Answer 1

Вы возвращаете 1 в предложении else. Вы должны возвращать 0:

else
{
    return 0;
}

Если значение не больше нуля, зачем вам возвращать его на первое место?

Answer 2

Ваш код выполняется следующим образом:

Sum --> 5
  Sum --> 4
    Sum --> 3
      Sum --> 2
        Sum --> 1
          Sum --> 0
          1 <---
        2 <---
      4 <---
    7 <---
  11 <---
16 <---

Проверьте ваш базовый случай.

Answer 3

Другие уже отметили ошибку, и я остановлюсь на рекурсии.

Хотя C # в настоящее время не выполняет оптимизацию хвостового вызова (хотя IL имеет специальную инструкцию tail), стоит упомянуть, что хвостовая рекурсия, как правило, хорошая вещь.

Хвостовая рекурсия - это особый случай рекурсии, в котором последняя операция функции, хвостовой вызов, является рекурсивным вызовом. Поскольку последний вызов является рекурсивным, нет необходимости сохранять кадр стека вызывающей функции, и компилятор может легко использовать эту информацию для генерации машинных инструкций, так что стек вообще не увеличивается. Так что он может превратить рекурсивную функцию в итеративную.

Переписать ваш код для поддержки хвостовой рекурсии можно следующим образом:

static int Sum(int result, int value)
{
    if(value == 0)
        return result;

    return Sum(result + 1, value - 1);
}

Answer 4

static int Sum(int value)
{
    if (value > 0)
    {
        return value + Sum(value - 1);
    }
    else
    {
        return 0; //Change this.
    }
}

Answer 5

Это потому, что когда значение равно 0, вы возвращаете 1. Затем оно добавляется.

Предложение "else" для Sum должно возвращать 0.

Answer 6

int summation(int num){

    if (num==1)
        return 1;

    return summation(num-1)+num;
}

Answer 7

Другие уже ответили на этот вопрос, но когда я работаю с рекурсией, мне нравится проверять, работает ли она, проверять базовый случай и один дополнительный случай. В вашем случае я бы протестировал его с 1, что привело бы к 2. Поскольку это, очевидно, неправильно, вы можете проверить на 0, который не будет использовать какую-либо рекурсию, и поэтому должно быть очевидно, что ошибка лежит в базовом классе.

В целом рекурсию легче рассуждать, так как вы можете перечислить ограниченное количество вещей, которые вам нужно проверить, но изначально это требует прыжка веры, поскольку ваша интуиция будет неправильной. Просто протестируйте крайние случаи и доверяйте математике , она не будет никогда терпеть неудачу.

Answer 8

Я всегда предпочитаю ставить завершающие прецеденты, чтобы они были очевидны, и у меня сильная почти психопатическая ненависть к "if cond then return a else return b" конструкциям. Мой выбор был бы (давая понять, что он не будет работать должным образом для отрицательных чисел):

static unsigned int Sum(unsigned int value) {
    if (value == 0)
        return 0;
    return value + Sum(value - 1);
}

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

Answer 9

Ваше окончательное выражение является предметом спора. Когда значение == 0 (или ниже), оно должно возвращать 0, а не 1. Ради эффективности (что, допустим, здесь, очевидно, не является проблемой, иначе рекурсия не использовалась бы для этой задачи) , вы должны завершить рекурсию со значением == 1 и вернуть литерал 1, чтобы сохранить один ненужный уровень рекурсии.

Answer 10

Я почти уверен, что проблема в том, что вы хотите, чтобы ваша рекурсия завершилась при value == 1, а в данный момент она заканчивается при value == 0.