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

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×9! быстро.

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

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