Introduction à la réccursivité ..

[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 :zen: )

[Joker62]

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

Voilà :D

[Joker62]

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

[sandrine_guillerme]

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

Bah oui je vois ça ..

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

[sandrine_guillerme]

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:

:ptdr: :ptdr:

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

ça sert à rien ce language à la noix

oups, j'ai rien dis..

[sandrine_guillerme]

Bah oui je vois ça ..

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

Revenons à ce qu'on disait .. :mur:

[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

[sandrine_guillerme]

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..

[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 :)

[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 !

[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.Hadrien/algo/AlgoTP1_a4.pdf
et plus compliqué :
http://brassens.upmf-grenoble.fr/IMSS/dciss/Enseignements/IT/Algo/td8bis.pdf

[sandrine_guillerme]

Ah c'est gentil merci :happy2:

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

Bon courage..

[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

[sandrine_guillerme]

Simplement Merci..


Je vais voir tout ça .. !

[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...

[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 .. )