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

Question

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

int factorial(int n) { 
    if (n == 1) return 1; 
    else return n * factorial(n-1); 
} 

Answer 1

Это неэффективно двумя способами, и вы ударил одного из них:

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

int factorial(int n) 
{ 
    int result = 1; 
    while (n > 0) 
    { 
     result *= n; 
     n--; 
    } 
    return result; 
} 

или, в качестве альтернативы, с for цикла.

Однако, как отмечено в комментариях выше, на самом деле не имеет значения, насколько это эффективно, если int не может даже провести результат. Это действительно должно быть long s, long long s, или даже big-ints.

Вторая неэффективность просто не имеет эффективного алгоритма. This list of factorial algorithms показывает несколько более эффективных способов вычисления факториала путем уменьшения числа числовых операций.

Answer 2

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

Накладные расходы функций - дополнительное время и память, необходимые для правильной настройки вызова функции.

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

Answer 3

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

int factorial(int n) { 
    int res = 1; 
    for (i = 1; i <= n; i++) { 
     res = res * i; 
    } 
    return res; 
} 

Answer 4

Рекурсия медленнее, а также людоед памяти с точки зрения памяти Stack.It это время с работы, чтобы выдвинуть данные в стек и снова, чтобы вытолкнуть его .the главное преимущество рекурсии заключается в том, что алгоритм делает его немного понятным или более «элегантным».

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

int num=4; 
int fact = 1; 
for (;num>1;num--) 
{ 
fact = fact*num; 
} 
//display fact