Возможно ли переполнение стека с помощью рекурсивной функции? - PullRequest
Новая
       38

Возможно ли переполнение стека с помощью рекурсивной функции?

0 голосов
/ 18 октября 2011

Эта функция имеет некоторые проблемы? 

 unsigned long factorial(unsigned long m)
 {
     return (m == 0) ? 1 : m * factorial(m - 1);
 }

Если я добавлю другую функцию: 

  int myCombina(int q, int p)
  {
      return factorial(q) / ( factorial(q) * factorial(q-p) );
  }

Этот myCombina () неэффективен, потому что в нем должен быть отменен наибольший общий делитель, чтобы найти комбинаторный.

max (факториал (q), факториал (q-p)) можно отменить. Нам нужно только вычислить q x (q-1) ... x (q -k +1).

Есть ли другие проблемы?

Любые комментарии приветствуются.

Спасибо

Ответы [ 3 ]

8 голосов
/ 18 октября 2011

если m очень большое, возможно, переполнение стека.

Переполнение стека не является основной проблемой в вашем коде ... если m очень большое, вы получите целочисленное переполнение , прежде чем переполнение стека.

Вам нужно использовать какой-то тип Bignum, если вы хотите, чтобы это работало для m больше, чем приблизительно 12 (в зависимости от размера unsigned long на вашей платформе).

2 голосов
/ 18 октября 2011

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

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

Ради этого, чтобы превратить его в хвостовой рекурсивный вызов, последний оператор функции должен быть возвращением с результатом, полученным из рекурсивного вызова. Ваш код не может быть оптимизирован, потому что ваш оператор возврата содержит m*factorial(n-1), то есть вы не возвращаете значение рекурсии, но фактически работаете с ним перед возвратом.

Преобразование, чтобы сделать его хвостовым рекурсивным, требует нажатия умножения на рекурсивный вызов, и это обычно выполняется как дополнительный аргумент, который сохраняет временный результат: 

unsigned long factorial_tail_recursive( 
                        unsigned long n,           // number to calculate factorial
                        unsigned long temp_result  // accumulated result
                      ) 
{
   return n == 0? tmp_result 
                : factorial_tail_recursive( n-1, n*temp_result );
}

// syntactic sugar to offer the same interface
unsigned long factorial( unsigned long n ) {
   return factorial_tail_recursive( n, 1 );    // accumulated result initialized to 1
}

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

2 голосов
/ 18 октября 2011

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

...