Как рекурсия делает непредсказуемым использование оперативной памяти?

Цитата из Code Complete 2,

int Factorial( int number ) {
   if ( number == 1 ) {
      return 1;
   }
   else {
      return number * Factorial( number - 1 );
   }
}

Помимо того, что он медленный [1] и делает использование оперативной памяти непредсказуемым [2], рекурсивную версию этой процедуры сложнее понять, чем итеративную версию, которая следует ниже:

int Factorial( int number ) {
   int intermediateResult = 1;
   for ( int factor = 2; factor <= number; factor++ ) {
      intermediateResult = intermediateResult * factor;
   }
   return intermediateResult;
}

Я думаю, что медленная часть связана с ненужными накладными расходами на вызов функций.

Но как рекурсия делает непредсказуемым использование оперативной памяти?

Разве мы не всегда можем предсказать, сколько памяти потребуется (поскольку мы знаем, когда предполагается, что рекурсия закончится)? Я думаю, что это было бы так же непредсказуемо, как итеративный случай, но не более того.


recursion memory-management memory language-agnostic factorial
person Lazer    schedule 02.11.2010    source источник
comment
Обратите внимание, что рекурсия МОЖЕТ выполняться с постоянным временем, ЕСЛИ процедура использует хвостовую рекурсию И если язык поддерживает оптимизацию хвостового вызова. Если вам интересно, посмотрите хвостовую рекурсию.   -  person erjiang    schedule 02.11.2010
comment
Кроме того, на некоторых процессорах, таких как накладные расходы на вызов функции Sparc, очень низкие. А с некоторыми языками программирования, такими как Tcl, вызов функции на самом деле быстрее, чем встроенный код (из-за того, как работает компилятор байтов).   -  person slebetman    schedule 03.11.2010

Ответы (3)


arrow_upward
3
arrow_downward

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

person codymanix    schedule 02.11.2010
comment
вот что я подумал, но почему это может быть непредсказуемо? - person Lazer; 02.11.2010
comment
Я думаю, это просто означает, что зависит от значения во время выполнения. Итеративная версия, которую я могу предсказать, всегда занимает 8 байтов стека (или что-то еще), тогда как я не могу предсказать рекурсивную версию, поскольку она зависит от значения number, переданного во время выполнения. Столь непредсказуемость означает невозможность предсказать постоянное значение во время компиляции. - person Brian; 02.11.2010
comment
Было бы непредсказуемо, если бы вы не знали, сколько раз функция вызывает сама себя, верно? Если функция вызывает себя слишком много раз, у вас будет stackoverflow =) - person gideon; 02.11.2010
comment
@Lazer: Это зависит от вашего алгоритма. Если у вас есть ограничение на то, сколько раз ваша функция будет вызывать сама себя, вы можете предсказать использование памяти. Если нет, то это непредсказуемо. В примере с факториалом ваша функция вызывает себя n - 1 раз, чтобы вычислить n !, поэтому реального ограничения нет. (Конечно, размер n, такой, что n! Может быть выражен как int, не такой большой, и если n больше, мы все равно получим неопределенное поведение.) - person David Thornley; 02.11.2010
comment
@gideon поможет ли увеличить размер резерва стека или размер фиксации стека? - person sameer karjatkar; 11.01.2013

arrow_upward
1
arrow_downward

Разве мы не всегда можем предсказать, сколько памяти потребуется (поскольку мы знаем, когда предполагается, что рекурсия закончится)? Я думаю, что это было бы так же непредсказуемо, как итеративный случай, но не более того.

Нет, не в общем случае. См. Обсуждение проблемы остановки для получения дополнительной информации. А вот рекурсивная версия одной из опубликованных здесь проблем:

void u(int x) {
    if (x != 1) {
        u((x % 2 == 0) ? x/2 : 3*x+1);
    }
}

Это даже хвостовая рекурсия. Поскольку вы не можете предсказать, завершится ли это вообще нормально, как вы можете предсказать, сколько памяти потребуется?

person ldav1s    schedule 04.11.2010

arrow_upward
0
arrow_downward

Если уровень рекурсии станет слишком глубоким, вы взорвете стек вызовов и съедите много памяти в процессе. Это может произойти, если ваше number является «достаточно большим» значением. Вы можете сделать хуже, чем это? Да, если ваша функция выделяет больше объектов при каждом вызове рекурсии.

person darioo    schedule 02.11.2010