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

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

А теперь почему.

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

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

Единственная проблема в том, что, насколько мне известно, очень немногие компиляторы 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.,

Лучше всего вообще не вычислять факториалы явно. Если вы вычисляете серию Тейлора (Маклорена) 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;
   }

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

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

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

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

Подробнее см. Здесь: http://publib.boulder.ibm.com/infocenter/iadthelp/v6r0/topic/com.ibm.etools.iseries.pgmgd.doc/c0925076137.htm

Вызов функции стоит дороже как во времени, так и в пространстве, потому что:

• Аргументы нужно поместить в стек, а возвращаемое значение выскочить. На это нужно время.
• Each call consumes its own "frame" of the stack.
  • This does not only prevent you from having very deep recursion (stack size is limited, typically to a few MB),
  • это также повреждает расположение вашего кеша (потому что вы используете разные части ОЗУ при каждом вызове) и, в конечном итоге, также требует времени.

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

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