mémoire virtuelle et fonction récursive Fermé

Question

Bonjour,
je pose la question ici faute de trouver de doc sur internet : supposons que mon pc dispose de 1Go de mémoire vive. J'écris une fonction récursive (en C par exemple) qui avant de donner le résultat a besoin de 100 appels à elle-même. Sur combien d'octets est stocké un seul appel récursif en mémoire svp? Je demande ça en fait pour savoir combien d'appels récursifs une mémoire de telle quantitée peut supporter.

merci bcp.

scriptiz · Answer

Compte plutôt le nombre de champs en mémoire.

Exemple pour cette méthode :
public static int factorielle(int n)
{
    return ((n==0)? 1 : n*factorielle(n-1));
}

Si je lui demande la factorielle de 100, il passera 100 fois en mémoire, et donc chaque appel aura son propre entier à retenir : int n.

Ici mon entier est codé sur 32 bits, soit 4 bytes (et on s'en fou qu'il soit signé ^^).

Donc 100 * 4 bytes = 400 bytes.

Soit pour 100 appels (comme tu dis), il m'aura fallu 400 bytes, hors toi avec ton giga de RAM tu possède en réalité environ 1.073.741.824 bytes.

Ce qui fait qu'en théorie tu pourrais faire jusqu'à 268.435.456 appels de ta méthode pour autant que tu travaille avec un entier.

Attention toutefois au récursivités terminales, ici ce n'est pas le cas, mais dans bien des cas une méthode récursive peut être terminale, et pour autant que le langage supporte la récursivité terminale (ce qui n'est par exemple pas le cas du Java), tu y gagnes en mémoire car il ne garde pas le résultat de chaque appel.

Renseigne toi sur les récursivité terminales et quels langages les supportes sur Google ;)

Voilà en espérant avoir été le plus clair possible.

Mémoire virtuelle et fonction récursive

1 réponse

Discussions similaires