Как вырваться из этого цикла

Question

Я работаю над Project Euler number 5. Я не искал Google, так как это, как правило, приведет к SO с ответом. Итак, это то, что у меня есть:

private int Euler5(int dividend, int divisor) 
    { 
     if (divisor < 21) 
     { 
      // if it equals zero, move to the next divisor 
      if (dividend % divisor == 0) 
      { 
       divisor++; 
       return Euler5(dividend, divisor); 
      } 
      else 
      { 
       dividend++; 
       return Euler5(dividend, 1); // move to the dividend 
      } 
     } 
     // oh hey, the divisor is above 20, so what's the dividend 
     return dividend; 
    } 

На мой взгляд, это имеет смысл. Тем не менее VS2012 дает мне исключение StackOverFlowException, предполагающее, что я не уверен в бесконечном цикле или рекурсии. Мой вопрос: почему это бесконечный цикл? У меня такое чувство, что я пропустил что-то совершенно глупое.

EDIT

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

Answer 1

Конечно, эта логика собирается взорвать стек. Подумайте об этом, если бы вы выполнили эту логику для решения проблемы нахождения наименьшего числа, равномерно делящегося на 1--10, вы должны были по крайней мере на 2520 вызовов в стеке на problem statement:

2520 - это наименьшее число, которое можно разделить на каждое из чисел от 1 до 10 без остатка.

Для 1--20 ответ явно намного больше, и совершенно не удивительно, что вы дуете в стек. Вы должны найти нерекурсивное решение.

Мой вопрос: почему это бесконечный цикл?

Это не так. Размер стека ограничен. Вы делаете слишком много рекурсивных вызовов и в конечном итоге нарушаете максимальный размер стека.

У меня такое чувство, что мне не хватает чего-то совершенно глупого.

Вы пришли к right place.

Answer 2

+1 для ответа Джейсона, который четко объясняет проблему.

Теперь для некоторого решения! Я знаю, по крайней мере, три способа удалить рекурсию из алгоритма:

1. Вместо этого вы можете найти чисто итеративный алгоритм (что может быть трудно для некоторых проблем);
2. Преобразование рекурсивного алгоритма в аналогичный с циклом и использование Stack < T> (или какой-то список) для хранения эквивалента стека вызовов. Это имеет аналогичное пространство, как и оригинальное, но куча может расти намного больше, чем стек!
3. Специальное семейство рекурсивных алгоритмов: tail-recursive. Их можно легко механически изменить, чтобы никогда не переполнять стек. Тебе повезло, это твой случай!

Алгоритм является хвостовой рекурсией, если все его рекурсивные вызовы хвостовых вызовов, что означает, что они являются последней вещью, которую сделали, прежде чем вернуться. Если вам непонятно, посмотрите на Google лучше.

Такие алгоритмы могут быть легко преобразованы путем настройки параметров и использования goto, а не реального вызова. Посмотрите на свой пример снова:

private int Euler5(int dividend, int divisor) 
{ 
    tail_call: 
    if (divisor < 21) 
    { 
     // if it equals zero, move to the next divisor 
     if (dividend % divisor == 0) 
     { 
      divisor++; 
      goto tail_call; // return Eular5(dividend, divisor); 
     } 
     else 
     { 
      dividend++; 
      // return Eular5(dividend, 1); // move to the dividend 
      divisor = 1; 
      goto tail_call; 
     } 
    } 
    // oh hey, the divisor is above 20, so what's the dividend 
    return dividend; 
} 

О, эй! Это точно такая же функция, но с фиксированным размером стека (нет вызова, только переходы). Теперь некоторые скажут: «Ух ... хэто! Они злые! Умри, умри!». Я бы сказал, что это одно из немногих законных целей. В конце концов, если ваш компилятор достаточно умный, он сам выполнит оптимизацию хвостового вызова (F # на самом деле, C# не делает, JIT может сделать это на x64, а не на x86).

Но для тех людей, которых я сказал бы: выглядите немного лучше. Поскольку в конце каждой ветви if/else есть goto, я могу полностью переместить его за пределы «if». Теперь у меня есть что-то вроде «start: if (X) {Y(); goto start;}« Подумайте об этом, это всего лишь цикл while (X) Y() ». Таким образом, вы только что нашли итеративную версию своей функции:

private int Euler5(int dividend, int divisor) 
{ 
    while (divisor < 21) 
    { 
     // if it equals zero, move to the next divisor 
     if (dividend % divisor == 0) 
     { 
      divisor++; 
     } 
     else 
     { 
      dividend++; 
      divisor = 1; 
     } 
    } 
    // oh hey, the divisor is above 20, so what's the dividend 
    return dividend; 
} 

Nice!