Exponentiation modulaire très rapide

Question

Bonjour,
Savez vous comment cette algorithme fonctionne réellement?
Je cherche a savoir comment ça se fait que après que la fonction puis soit appelé jusqu'à k=1 alors elle arrive a revenir en arrière et retrouver son chemin pour donner la bonne solution (je cherche donc des caractéristiques propres a python sur les fonctions récursives)
Si quelqu'un peut m'expliquer le principe de cette pile d'éxécution (si c'est bien cela), j'en serait ravi.

Voici le code:
import timea=int(input())k=int(input())n=int(input())hey=time.time() #rajouter pour obtenir le tempsdef puis(a,k,n):    if k==0:       return 1    b=puis(a,(k//2),n)    if k%2==0:        return ((b*b)%n)    return ((b*b*a)%n)print(puis(a,k,n))ho=time.time()print(ho-hey)

Merci d'avance

lespinx · Answer

Bonjour,

A chaque exécution de la boucle récursive il y a sauvegarde du contexte  à cet instant (variables, pointeurs, etc) il y a donc un empilement de zones mémoire.
Il faut qu'il y ai dans le programme une condition de sortie sinon le nombre d'appels récursifs est limité par un paramètre Python et aussi bien sur par la quantité de mémoire disponible.
 
Voir http://igm.univ-mlv.fr/~rispal/W3bis/src/python/cours2/CM_5.pdf

Exponentiation modulaire très rapide

1 réponse

Votre réponse

Discussions similaires