Como é factorial calculado?

Question

dizer que há uma função para calcular fatorial (n)

O fatorial (7) cria 7 função objecto para cada um de n de 1 a 7

e usar esses valores sempre que necessário (por fatorial (8) como como fatorial (7) * 8)

Answer 1

Depende da linguagem e da implementação da linguagem.

Em muitas linguagens funcionais (por exemplo, Haskell), uma função é garantido para a mudança nada; apenas para retornar um valor. Esta falta de efeitos secundários permite a linguagem para se lembrar / cache, ou "memoize", os resultados de chamadas de função.

Em uma linguagem menos sofisticado, 7 quadros de chamada de função distintas pode ser colocado na pilha e bateu fora.

A função fatorial escrito corretamente em muitas linguagens funcionais também seria recursiva cauda; nesse caso, o idioma pode optar por simplesmente pular do fundo da função até o topo para evitar a criação de uma outra chamada de função. Neste caso, a língua é ativar a função recursiva em um loop "de graça".

Answer 2

Depende, parece que você está falando de uma função factorial recursiva:

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

Esta função irá chamar-se recursivamente o número de vezes necessário para calcular o dada fatorial (n).

Na maior parte todas as funções recursiva pode ser transformada em uma solução iterativa usando uma pilha de acumular os resultados consecutivos ...

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

Answer 3

É possível. O que você está pedindo sons como memoization - você armazenar os resultados anteriores para cálculos de velocidade posteriores. Assim, por exemplo, se você calcular 9 !, você pode armazenar os valores para 1! .. 9 !, e se você for solicitado para 8! mais tarde você pode simplesmente devolver o valor armazenado. Da mesma forma, se pediu 10 !, você pode calcular 10 × 9! rapidamente.

A coisa é que fatorial ( n ) cresce tão rapidamente, para grandes valores de n você pode acabar usando um monte de armazenamento, de modo que o comércio espaço-tempo pode não valer a pena.

Outra função que pode usar memoization efetivamente está computando números de Fibonacci.