Как вычисляется факториал?

Question

скажем, есть функция для вычисления факториала (n)

Факториал (7) создает 7 функциональных объектов для каждого из n от 1 до 7

и использовать эти значения при необходимости (для факториала (8) как факториал (7) * 8)

Answer 1

Это зависит от языка и языковой реализации.

Во многих функциональных языках (например, Haskell) функция гарантированно ничего не изменит; только чтобы вернуть значение. Отсутствие побочных эффектов позволяет языку запоминать / кэшировать или «запоминать» результаты вызовов функций.

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

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

Answer 2

Зависит от того, что вы говорите о рекурсивной факториальной функции:

int factorial(int n) {
    return n>=1 ? n * factorial(n-1) : 1;
}

Эта функция сама вызовет рекурсивно количество раз, необходимое для вычисления данного факториала (n).

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

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

Answer 3

Может. То, что вы спрашиваете, звучит как памятка - вы сохраняете предыдущие результаты, чтобы ускорить вычисления позже. Так, например, если вы вычислите 9 !, вы можете сохранить значения для 1! .. 9 !, а если вас попросят 8! позже вы можете просто вернуть сохраненное значение. Точно так же, если попросить 10 !, вы можете вычислить 10 & times; 9! быстро.

Дело в том, что факториал ( n ) растет так быстро, что при больших значениях n вы можете использовать много памяти, поэтому торговля в пространстве и времени может не произойти быть стоящим.

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