TD5 Récursivité

Télécharger le TD5 Recursivite en pdf

Pages : 1

Page 1 : Informatique IISemestre 2 - 2022/2023TD 5 : RécursivitéExercice 1 Fonction puissance1. Ecrire une fonction itérative powerIt a,b : entier qui retourne ab.2. Donner une définition récursive puis écrire la fonction récursive powerRec a , b : entier qui retourne ab.3. Dessiner l’arbre de récursivité depowerRec 3 , 4 .Exercice 2 Coefficient binomialPour deux entiers naturels n et p tels que 0 p n, les coefficients binomiaux donnent le nombre de sous-ensemblesIls se notentnk.On a les trois propriétés suivantes :p N, n Nn0= 1 etnn= 1 etnp=n 1p 1+n 1pEn utilisant ces formules, écrire une fonction calculant le coefficient binomial de deux entiers sans utiliser de calcul deExercice 3 Fonction récursive pour tableauLes fonctions suivantes doivent être testées dans un programme principal en utilisant un tableau rempli aléatoirement.1. Ecrire une fonction recursive permettant d’afficher un tableau passé en paramètre.2. Ecrire une fonction récursive permettant de trouver le maximum d’un tableau passé en paramètre.3. Ecrire une fonction recursive permettant de compter le nombre d’éléments divisibles par 3 dans un tableau :— En testant les valeurs du tableau en partant de la fin— En testant les valeurs du tableau en partant du débutExercice 4 Somme des entiers1. Écrire une fonction itérative sommeEntiersint a, int b qui retourne la somme de tous les nombres entiers setrouvant entre a et b inclus exemple : a = 7 et b = 10 retourne 7 + 8 + 9 + 10 = 34.2. En effectuant la somme dans l’ordre croissant c’est-à-dire en commençant à sommer les nombres les plus petits, donnerune définition récursive de cette somme puis écrire la fonction sommeEntiersCroissantint a, int b associée quicalcule cette somme on pourra choisir entre récursivité terminale ou non-terminale..3. En parcourant la somme dans le sens décroissant c’est-à-dire en commençant à sommer les nombres les plus grands,donner une définition récursive de cette somme puis écrire la fonction récursive sommeEntiersDecroissantint a,int b qui calcule cette somme.4. Proposer un programme principal pour tester les fonctions construites ci-dessus en prenant des valeurs de paramètresaléatoires entre 100 et 200 pour les paramètres de ces fonctions en ajoutant des conditions si nécessaire.Exercice 5 Somme des chiffres1. Ecrire une fonction itérative qui retourne la somme des chiffres d’un entier composé de plusieurs chiffres.Exemple : somme3Chiffres219 = 122. Modifier la fonction précédente pour qu’elle fonctionne pour n’importe quel nombre entier.Exemple : sommeChiffres3807 = 183. Donner la définition récursive et écrire une version récursive non terminale de la fonction.4. Donner l’arbre de récursivité de votre fonction récursive non terminale avec en argument le nombre 6053.5. Recommencer les 2 points précédents en utilisant une version récursive terminale de la fonction.1 possibles de p élements d’un ensemble à n éléments. factoriel. Quel type de fonction doit-on utiliser ?

Pages : 1