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

Question

Цитирование из Код завершения 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;
}

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

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

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

Answer 1

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

Answer 2

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

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

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

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

Answer 3

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