Почему факторная рекурсивная функция менее эффективна, чем нормальная факторная функция?

Question

У меня есть две функции, которые вычисляют факториал числа n.Я не понимаю, почему «нормальной» функции требуется меньше времени для вычисления факториала числа n.Это нормальная функция:

double factorial(int n) {
    double s = 1;
    while (n > 1) {
        s *= n;
        --n;        
    }

    return s;
}

И это рекурсивная функция:

double factorial(int n) {
    if (n < 2) return 1;
    return n * factorial(n-1);
}

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

Какой из них использовать и почему?

PS: я использую double по мере необходимостиэто вычислить ряд Тейлора е ^ х.

Answer 1

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

Теперь, почему.

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

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

Единственная проблема заключается в том, что, насколько мне известно, очень мало, если какой-либо компилятор C ++ выполняет такую ​​оптимизацию.: - (

Однако, для полноты, идея состоит в том, чтобы убедиться, что существует только один рекурсивный вызов, и что это самое последнее, что происходит. Это называется хвостовая рекурсия . Ваштекущий рекурсивный код,

double factorial( int n )
{
    if( n < 2 ) { return 1; }
    return n*factorial( n-1 );
}

не является хвостово-рекурсивным, потому что после рекурсивного вызова происходит умножение на n.

Чтобы сделать его хвост-рекурсивным, вы можете передать в качестве аргументовинформация, необходимая для выполнения того, что должно быть сделано в конце, здесь *n. Информация, необходимая для этого, - значение n плюс тот факт, что это должно быть сделано. Это означает введение вспомогательной функции с подходящим формальным аргументом:

double factorialScaledBy( double m, int n )
{
    if( n < 2 ) { return m*1; }

    // Same as "n*factorialScaledBy( m, n-1 )", but tail-recursive:
    return factorialScaledBy( n*m, n-1 );  
}

double factorial( int n )
{
    return factorialScaledBy( 1, n );
}

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

Ура и hth.,

Answer 2

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

Answer 3

Лучше всего вообще не рассчитывать факториалы. Если вы вычисляете ряд Тейлора (Маклаурина) exp(x):

   exp(x) = 1 + x/1! + x^2/2! + x^3/3! + x^4/4! + ...

Лучше всего сделать что-то вроде следующего:

   double y = 1.0;
   int i = 1;
   double curTerm = 1.0;
   double eps = 1e-10;  // whatever's desired
   while( fabs(curTerm) > eps)
   {
        curTerm *= x / (double)i;
        y += curTerm;
        ++i;
   }

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

Answer 4

Это, безусловно, связано со структурами данных. Структуры данных - это забавные вещи. Некоторые из них отлично работают при меньших размерах данных, а некоторые лучше при больших размерах данных.

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

См. Это для более подробной информации: http://publib.boulder.ibm.com/infocenter/iadthelp/v6r0/topic/com.ibm.etools.iseries.pgmgd.doc/c0925076137.htm

Answer 5

Вызов функции стоит больше как во времени, так и в пространстве, потому что:

• Аргументы должны быть помещены в стек и возвращено возвращаемое значение. Это стоит времени.
• Каждый вызов потребляет свой собственный «кадр» стека.
  • Это не только предотвращает очень глубокую рекурсию (размер стека ограничен, как правило, несколькими МБ),
  • это также повреждает локальность вашего кэша (потому что вы обращаетесь к разным частям ОЗУ при каждом вызове) и в конечном итоге также стоит времени.

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

Кроме того, хотя это и не относится к делу, «меньше операций» не всегда означает лучшую производительность. Иногда «больше операций» , но с лучшей локальностью могут лучше использовать кэширование и предварительную выборку, которые все современные процессоры реализуют, чтобы скрыть задержку ОЗУ.