Comment la factorielle est-elle calculée?

Question

dire qu'il existe une fonction pour calculer factorielle (n)

Factoriel (7) crée-t-il 7 objets fonction pour n compris entre 1 et 7

et utilisez ces valeurs chaque fois que nécessaire (pour factorielle (8) comme factorielle (7) * 8)

Answer 1

Cela dépend de la langue et de son implémentation.

Dans de nombreux langages fonctionnels (par exemple Haskell), il est garanti qu'une fonction ne change rien; seulement pour renvoyer une valeur. Ce manque d’effets secondaires permet au langage de se souvenir / mettre en cache, ou "mémoriser", les résultats des appels de fonction.

Dans un langage moins sophistiqué, 7 cadres d'appel de fonction distincts peuvent être placés sur la pile et sautés.

Une fonction factorielle correctement écrite dans de nombreux langages fonctionnels serait également récursive; dans ce cas, la langue peut choisir de simplement sauter du bas vers le haut de la fonction pour éviter de créer un autre appel de fonction. Dans ce cas, la langue transforme la fonction récursive en une boucle "gratuite".

Answer 2

Cela dépend, on dirait que vous parlez d'une fonction factorielle récursive:

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

Cette fonction invoquera elle-même récursivement le nombre de fois nécessaire pour calculer la donnée factorielle (n).

La plupart des fonctions récursives peuvent être transformées en une solution itérative en utilisant une pile pour accumuler les résultats consécutifs ...

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

Answer 3

C'est possible. Ce que vous demandez ressemble à de la mémoization - vous stockez les résultats précédents pour accélérer les calculs ultérieurement. Ainsi, par exemple, si vous calculez 9 !, vous pouvez stocker les valeurs pour 1! .. 9 !, et si on vous demande 8! plus tard, vous pouvez simplement renvoyer la valeur stockée. De même, si on vous demande 10 !, vous pouvez calculer 10 × 9! rapidement.

Le fait est que factoriel ( n ) croît si rapidement, pour des valeurs importantes de n , vous pouvez vous retrouver avec beaucoup de stockage, de sorte que le commerce spatio-temporel peut ne pas en valoir la peine.

Une autre fonction qui peut utiliser efficacement la mémorisation est le calcul des nombres Fibonacci.