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

Question

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

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

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

Answer 1

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

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

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

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

Answer 2

Он может. То, что вы спрашиваете, звучит как memoization - вы сохраняете предыдущие результаты для ускорения вычислений позже. Так, например, если вы вычислите 9 !, вы можете сохранить значения для 1! .. 9 !, и если вас попросят 8! позже вы можете просто вернуть сохраненное значение. Аналогично, если вас попросят 10 !, вы можете вычислить 10 × 9! быстро.

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

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

Answer 3

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

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

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

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

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