Java

pour la comprendre, il faut que tu te dises que c'est une fonction récursive :

au niveau du return, on appelle de nouveau la fonction mais cette fois avec un n plus petit (divisé par deux si n paire, n-1 sinon)

Donc si on regarde n impaire:
on va retourner
a*p(a,n-1)
Entrons maintenant dans p(a,n-1)
n-1 est pair, on va donc rester constamment dans le deuxieme test désormais.

on aura donc :
x=(a* [p(a,n/2)*p(a,n/2)])
Si on entre à nouveau dans la fonction suivante :
x=(a* [(p(a,(n/2)/2))^4)

etc etc...

Si je ne me suis pas trompé c'est ca (dans le cas d'un n paire enlever le a*)
Tu peux vérifier en prenant un papier et un crayon, c'est le mieux à fair epour les fonctions récursives, en tous cas voila l'idée.

son temps de validité et bien quand tu auras trouvé comment elle fonctionne, tu comprendras vite, à vue de nez je dirais que c'est une n-exponentielle, à confirmer.

(Je n'ai pas pu éditer le message donc si des modos passent par là)

pour la comprendre, il faut que tu te dises que c'est une fonction récursive :

au niveau du return, on appelle de nouveau la fonction mais cette fois avec un n plus petit (divisé par deux si n pair, n-1 sinon)

Donc si on regarde n impaire:
on va retourner
a*p(a,n-1)
Entrons maintenant dans p(a,n-1)
n-1 est pair, on va donc rester constamment dans le deuxieme test désormais.

on aura donc :
x*x=[a* p(a,(n-1)/2) * a*p(a,(n-1)/2)]

un produit

on entre alors dans les deux fonctions :
x*x=[a* p(a,((n-1)/2/2))* p(a,((n-1)/2/2))] *[a* p(a,((n-1)/2/2))* p(a,((n-1)/2/2))]
d'où
x*x=[a* p(a,(n-1)/4)* p(a,(n-1)/4)] *[a* p(a,(n-1)/4)* (a,(n-1)/4)]
2 produits

On entre alors dans 4 fonctions identiques et chacune d'elle nous rammenera un produit de deux fonctions où n sera encore divisé par deux d'où
x*x=(a* [p(a,(n-1)/8)*p(a,(n-1)/8)]*[p(a,(n-1)/8*p(a,(n-1)/8)*(a* [p(a,(n-1)/8*p(a,(n-1)/8)]*[p(a,(n-1)/8*p(a,(n-1)/8])

etc etc
compter les produits :
à chaque appel de fonction, on double le nombre de produits de fonctions:
premiere iteration : un produit ( deux fonctions)
seconde iteration trois produits (4 fonctions)
troisieme : sept produits (8fonctions)
d'ou ( p^2)-1 (+2 si n pair)
avec p nombre d'itérations.
Ce nombre dépend de n;

Tu peux vérifier en prenant un papier et un crayon, c'est le mieux à fair epour les fonctions récursives, en tous cas voila l'idée.

Salut!

Cette fonction calcule a exposant n.

Temps de validité = n (n multiplications car à chaque passage, n est diminué de 1)

;-)
HackTrack

oups désolé^^ je travaille trop :p

le sieur a raison