Come viene calcolato il fattoriale?

Question

indica che esiste una funzione per calcolare fattoriale (n)

Il factorial (7) crea 7 oggetti funzione per ciascuno di n da 1 a 7

e usa quei valori quando è necessario (per factorial (8) come factorial (7) * 8)

Answer 1

Dipende dalla lingua e dall'implementazione della lingua.

In molti linguaggi funzionali (ad esempio Haskell), una funzione non cambia nulla; solo per restituire un valore. Questa mancanza di effetti collaterali consente al linguaggio di ricordare / memorizzare nella cache, o "memoize", i risultati delle chiamate di funzione.

In un linguaggio meno sofisticato, 7 frame di chiamate di funzioni distinte potrebbero essere posizionati nello stack e saltati fuori.

Una funzione fattoriale correttamente scritta in molti linguaggi funzionali sarebbe anche ricorsiva alla coda; in tal caso la lingua potrebbe scegliere di saltare semplicemente dalla parte inferiore della funzione verso l'alto per evitare di creare un'altra chiamata di funzione. In questo caso la lingua sta trasformando la funzione ricorsiva in un ciclo "gratuito".

Answer 2

Dipende, sembra che tu stia parlando di una funzione fattoriale ricorsiva:

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

Questa funzione si richiamerà ricorsivamente il numero di volte necessario per calcolare il dato factorial (n).

Per lo più tutte le funzioni ricorsive possono essere trasformate in una soluzione iterativa usando uno stack per accumulare i risultati consecutivi ...

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

Answer 3

Può. Quello che stai chiedendo suona come memoization : memorizzi i risultati precedenti per velocizzare i calcoli in seguito. Ad esempio, se si calcola 9 !, è possibile memorizzare i valori per 1! .. 9 !, e se ti viene chiesto 8! in seguito puoi semplicemente restituire il valore memorizzato. Allo stesso modo, se richiesto per 10 !, è possibile calcolare 10 & # 215; 9! rapidamente.

Il fatto è che il fattoriale ( n ) cresce così rapidamente, per grandi valori di n puoi finire usando un sacco di spazio di archiviazione, quindi il commercio spazio-temporale potrebbe non essere utile.

Un'altra funzione che può utilizzare efficacemente la memoizzazione è il calcolo dei numeri di Fibonacci.