Как вычисляется факториал?
-
10-07-2019 - |
Вопрос
скажем, есть функция для вычисления факториала (n)
Факториал (7) создает 7 функциональных объектов для каждого из n от 1 до 7
и используйте эти значения, когда это необходимо (для factorial (8), как factorial (7) * 8)
Решение
Это зависит от языка и языковой реализации.
Во многих функциональных языках (например, Haskell) функция гарантированно ничего не изменит; только чтобы вернуть значение. Отсутствие побочных эффектов позволяет языку запоминать / кэшировать или «запоминать» результаты вызовов функций.
В менее изощренном языке 7 различных фреймов вызова функций могут быть помещены в стек и вытолкнуты.
Правильно написанная факториальная функция во многих функциональных языках также будет хвостовой рекурсивной; в этом случае язык может просто перейти с нижней части функции на верхнюю, чтобы избежать создания другого вызова функции. В этом случае язык превращает рекурсивную функцию в цикл «бесплатно».
Другие советы
Зависит от того, что вы говорите о рекурсивной факториальной функции:
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;
}
Может. То, что вы спрашиваете, звучит как памятка - вы сохраняете предыдущие результаты, чтобы ускорить вычисления позже. Так, например, если вы вычислите 9 !, вы можете сохранить значения для 1! .. 9 !, а если вас попросят 8! позже вы можете просто вернуть сохраненное значение. Точно так же, если попросить 10 !, вы можете вычислить 10 × 9! быстро.
Дело в том, что факториал ( n ) растет так быстро, что при больших значениях n вы можете в конечном итоге использовать много памяти, поэтому торговля в пространстве и времени может быть не стоит.
Еще одна функция, которая может эффективно использовать запоминание, - это вычисление чисел Фибоначчи. Р>