Introduction à la réccursivité ..

(Cliquez-ici pour accéder à la version originale de cette discussion avec couleurs et images)





Posted by: sandrine_guillerme

alors ehem..

Oui commencons par le début du commencement:

Soit n un entier positif ou nul .Ecrire une fonction réccursive pour calculer m^n en utilisant :

Si n=0 m^n = 1
si n est paire m^n = m^2(n/2)
si n est impaire m^n=m(m^n-1)


alors si tu as des idées, je suis preneuse,

je l'ai fais lmais c'est juste pour comparer en faite ..

Merci (bien sûr )


Posted by: Rain'

puissance := proc (m,n)
local res:
if n = 0 then res:=1:
elif irem(n,2)=0 then res:=puissance(m^2,n/2):
elif irem(n,2)=1 then res:=m*puissance(m,n-1):
fi:
res;
end:




Posted by: Joker62

Fonction Puissance( m : Reel ; n : Entier )
{
Si n = 0;
Alors retourner m;
Sinon
Puissance(m*m, n-1);
}

Voilà :D


Posted by: Joker62

Ah moi c'est de la récursivité totale !!!
Pas de retour après les appels de fonction :D


Posted by: sandrine_guillerme

Citation:
Posté par Joker62
Ah moi c'est de la récursivité totale !!!
Pas de retour après les appels de fonction :D


Bah oui je vois ça ..

au fait ! t'as pas utilisé la condition pair / impair, ça te fais peur à ce point?


Posted by: sandrine_guillerme

Citation:
Posté par Rain'
puissance := proc (m,n)
local res:
if n = 0 then res:=1:
elif irem(n,2)=0 then res:=puissance(m^2,n/2):
elif irem(n,2)=1 then res:=m*puissance(m,n-1):
fi:
res;
end:



Ah tiens, j'en connais un qui aime Maple .. tssss !

ça sert à rien ce language à la noix

oups, j'ai rien dis..


Posted by: sandrine_guillerme

Citation:
Posté par sandrine_guillerme
Bah oui je vois ça ..

au fait ! t'as pas utilisé la condition pair / impair, ça te fais peur à ce point?



Revenons à ce qu'on disait ..


Posted by: VPE

Proc_truc(m,n)
Si n = 0 alors:
cas n°1
quitter proc
Fin si
Si mod(n,2) = 0 est vrai alors :
cas n°2
Sinon
cas n°3
Fin si
Fin proc


Posted by: sandrine_guillerme

Citation:
Posté par VPE
Proc_truc()
Si n = 0 alors:
cas n°1
quitter proc
Fin si
Si mod(n,2) = 0 est vrai alors :
cas n°2
Sinon
cas n°3
Fin si
Fin proc


Merci,


Mais il me semble justement qu'on a pas le droit d'utiliser mod rem ...

je sais pas..


Posted by: VPE

Proc_m-puissance-n(m,n)
Si n = 0 alors:
retourner 1
quitter proc
Fin si
Si mod(n,2) = 0 est vrai alors :
retourner m^2(n/2)
Sinon
retourner m(m^n-1)
Fin si
Fin proc
Je pense qu'il s'agit bien d'un algorithme récursif et la fonction modulo n'y change rien :)


Posted by: sandrine_guillerme

Ah oki là je vois .. là je suis d'accord, je vois maintenant une réccursivité,

t'aurais pas un lien ou je peux trouver des exos sur la réccursivités (corrigés si possible) pour s'entraîner ?


Merci Bien !


Posted by: VPE

Pas dans l'immédiat mais si d'autres membres ne te dégottent rien j'ai chez mon pére un livre "initiation aux algorithmes de base" dont je pourrai scaner 5 ou 6 pages sur la récursivité avec corrigés
EDIT : j'ai trouvé un doc PDF comportant 2 exos sur la récursivité :
http://staff.umh.ac.be/Melot.Hadrie.../AlgoTP1_a4.pdf
et plus compliqué :
http://brassens.upmf-grenoble.fr/IM...Algo/td8bis.pdf


Posted by: sandrine_guillerme

Ah c'est gentil merci

et puis sinon si tu as le temps, je veux bien les autres exos aussi .. !

Bon courage..


Posted by: ghghgh

Salut,
si tu veux t'entraîner sur des exos où il y a de la récursivité, tu peux voir ça sur le site france-ioi , le site d'entraînement pour l'équipe de france aux ioi...
il y en a ciblé sur la récursivité dans la partie prog C, d'autres dans la partie Caml il me semble, et dans la partie algo, il y en a tout plein, tout plein pour résoudre des problèmes, de graphes, ou autres =)

amuse-toi bien !

Bonne soirée ;)

si t'as besoin d'aide, j'suis là pour t'aider, mon pseudo sur le site -> mic


Posted by: sandrine_guillerme

Simplement Merci..


Je vais voir tout ça .. !


Posted by: ghghgh

dans la partie algo cependant, la récursivité est moins "mathématique", genre calculer des factorielles, puissances... mais plus centrée sur, tu testes toutes les possibilités grâce à ça... puis tu dynamises...

si tu veux plus orienté "maths", t'as l'épreuve semi-numérique I et II, où là tu dois calculer des arrangements, des combinaisons, et ce genre de choses...


Posted by: sandrine_guillerme

Au fait je suis plus intéréssée par la partie algo (c'est le module algo que je passe au fait .. )










-