Dans les exercices que vous avez réalisés, vous avez souvent éprouvé des difficulté à trouver le cas de base, et le cas similaire plus simple.
En réalité, pour beaucoup, vous n'avez jamais réfléchi de cette façon !
Au lieu de cela, vous avez regardé les exercices précédents, et tenté de vous en inspirer. Cela vous amène à écrire des bouts de codes, qui, si vous avez bien respecté les Types renvoyés, sont plus ou moins correct, mais incomplet, non fonctionnel...
qu'est-ce que j'entend par là ?
1er exemple : Reprenons l'exercice my_range(a,b)
L'énoncé donne les spécifications de la fonction, et on lit :
:returns : list: la liste des entiers de a à b - 1
Il faudra donc que votre cas de base ET votre cas général renvoient toujours une liste. Seule exception, on renvoie None si a > b.
donc si vous écrivez :
- return a + my_range(a,b) vous additionnez un int (a) et une liste -> typeError
- return [ my_range(a,b) ] Vous avez bien compris qu'il faut renvoyer une liste, mais my_range(a,b) est une liste donc ici vous renvoyez une liste contenant une liste, donc une liste de liste, pas une liste d'entiers
2ème exemple : Reprenons l'exercice longeur(chaine)
L'énoncé donne les spécifications de la fonction, et on lit :
:returns : int: le nombre de lettres dans la chaine
Il faudra donc que votre cas de base ET votre cas général renvoient toujours un entier.
donc si vous écrivez :
- return txt[0] + longueur( txt[1:] ) vous additionnez un str (txt[0]) et un int car longueur(txt) est toujours un int -> typeError
- if txt == "" : return "" vous retournez une chaine, pas un int
Dans ce dernier cas, on voit bien que vous avez senti la solution : traiter le premier caractère, puis le reste de la chaine. Bon, vous avez un peu du mal a écrire txt[1:] parce que les chaines de caractères vous ennuient un peu, mais souvent vous avez plus ou moins tenté d'écrire cela.
 | Il est donc important de bien faire attention au type que la fonction retourne et le cas général doit combiner des solution de même types. Une liste + une liste, un int + un int, un str plus un str etc.... |
C'est là que vous pêchez le plus. Imiter un exercice précédent ne fonctionne pas, ils sont tous un peu différent.
Reprenons les :
1er exemple : somme(a,b) doit renvoyer a+b (un int)
on ne peut ajouter/retrancher que 1, on ne sait donc pas additionner a et b.
quelle est le problème trivial ? on pourrait songer à : somme(a,1) qui consiste à ajouter 1 (on sait faire) ou bien à somme(a,0) qui consiste à ne rien ajouter, on sait faire.
alors quel est le cas qui se rapproche un peu de ce cas simple ? c'est quand b diminue et se rapproche de 1 ou de 0. d'ou l'idée de rappeler somme(a,b-1)
Cette étape de réflexion est indispensable, et doit vous mener à écrire :
a+b = a +1 + (b - 1)
il existe 2 façon de l'entendre :
- somme(a,b) = 1 + somme(a,b-1)
- somme(a,b) = somme(a+1,b-1)
les deux sont corrects. Exprimons cela avec une phrase en français :
pour ajouter b à a : j'ajoute 1 puis j'ajoute tout le reste (b-1)
2ème exemple : longueur de la chaine
La phrase en français serait :
c'est 1 + la longueur du reste de la chaine.
la relation de récurrence s'écrira donc :
longueur(txt) = 1 + longeur(txt sans la première lettre)
reste à savoir écrire en python l'expression txt sans la première lettre
3ème exemple : my_range
vous êtes d'accord que nous écrivons de gauche à droite ? donc il est assez peu logique de commencer par la droite....
prenez un exemple quand vous ne voyez pas de suite. Si vous devez écrire range(2,6) vous allez forcément écrire 2 puis 3 puis 4 puis etc... puis 5.
le etc ci-dessus vous indique la réponse ! il indique qu'on répète ce qu'on vient juste de faire jusqu'à la fin de la liste. Ce etc est en fait notre expression pour indiquer une récurrence.
La bonne formulation sera :
Je met 2 dans la liste puis je vais recommencer avec les autres, c'est à dire my_range(3,6)
Si on respecte les types, ce 2 doit être dans une liste : [2]
reste à généraliser, avec a et b au lieu de 2 et 6 :
la liste des entiers de 2 à 5 est [2] + liste des entiers de 3 à 5
En voulant vous inspirer d'un exercice précédent, beaucoup ont écrit quelques chose du genre :
my_range(a,b) = my_range(a,b-1)
pourquoi pas, mais aller de a à b-1 est pareil que aller de a à b-2 et ajouter b-1, vous écrivez de droite à gauche ? C'est un peu malheureux, ça complique inutilement l'exercice, d'autant que vous vous emmêlez dans les b-1....
C'est parce que vous n'avez pas pensé récursif, mais plutôt pensé "comment j'ai fait dans cet autre exercice ?"
3ème exemple : parité de l'entier n
pour cet exercice c'est le cas de base qui peut vous guider. Le problème indique qu'on a pas le droit d'utiliser modulo (%), mais ce qu'on cherche est bien de savoir si n%2 == 0
et c'est trivialement vrai si n = 0
donc on va devoir se rapprocher de ce cas trivial. connaitre la parité de n-1 est en ce sens un peu plus simple que connaitre la parité de n, car on se rapproche de 0.
quel lien existe-t-il entre parité de n, et parité de n-1 ? ben c'est l'opposé:
si n pair n-1 est impair
s n impair n-1 est pair
on peut donc écrire :
partité de n = not ( parité de n-1)
et nous avons notre récurence !
-> return not est_pair(n-1)
un dernier exemple : printInline(a,b)
Cette fonction est en réalité une procédure, elle ne renvoi rien (None). Elle doit au contraire afficher quelques chose.
On est dans une situation similaire quand on dessine, par exemple avec Turtle.
Pour respecter les types on ne pourra en aucun cas écrire quelques chose comme :
printInline(a,b) = quelques chose + printInline(a,b-1)
Car additionner quelques chose et None est impossible !
La fonction doit FAIRE une partie du travail. laquelle ?
Puisque nous devons écrire une liste d'entiers, commençons par le premier :
print(a)
puis continuons avec tous les autres en partant du prochain qui est a+1 : printInline(a+1,b)
restera à régler le problème du retour à la ligne : print(a) induit un retour à la ligne qu'il faudra remplacer par un espace sans retour à la ligne : print(a,end=" ").
reste aussi a trouver quand s'arrêter ! le dernier entier à écrire sera b, donc a doit augmenter (a+1) et on s'arrête quand a == b, et là ont fera juste print(a) sans ajouter un espace cette fois, et sans rappeler la fonction.
| Tout ces exemples sont différents, et il est dangereux de vouloir imiter la solution d'un exercice pour en résoudre un autre, la plupart du temps ça ne va pas fonctionner. Ce qu'il faut faire c'est vraiment penser récursif : je fait en premier ceci puis je recommence avec le reste du problème. |
Exercice 1 :
On veux écrire une fonction qui calcule factoriel n (noté en maths : n!)
on pourrait songer à commencer par la gauche mais on aura un problème :
calculer 
Vous l'avez remarqué, on peut souvent prendre le problème par le haut ou par le bas. par exemple :
longueur(txt) = 1 + longueur(txt[1:]) si je vais de gauche à droite (de bas en haut si je regarde l'indice de 0 à n-1)
mais aussi bien :
longueur(txt) = 1 + longueur(txt[;-1]) si je vais de droite à gauche (de haut en bas si je regarde l'indice de n-1 à 0)
dans un cas j'ai retiré le 1er caractère, dans l'autre cas le dernier, les 2 sont possibles.
Dans notre factorielle ça ne fonctionne pas. Mais pouvez vous exprimer la récurrence en partant du haut ?
Que mettez vous à la place des ... ? (mettre la réponse sans espace, et avec un opérateur
Exercice 2
Proposez un algorithme récursif de calcul du produit de deux entiers naturels a et b en supposant que les seules opérations de base dont vous disposez sont
- la somme de deux entiers a et b : a + b
- soustraire 1 à un entier
On va transformer la multiplication en additions :
Que mettez vous à la place des ... ? (mettre la réponse comme une formule incluant l'appel de produit.
Ne mettre aucun espace dans la réponse.
Exercice 3 : Palindrome
Un palindrome est un mot dont les lettres lues de gauche à droite sont les mêmes que celles lues de droite à gauche.
Les mots radar, elle, été, ici, kayak sont des palindromes.
On veux écrire une fonction qui teste si un mot est un palindrome.
ispalindrome(txt) renvoi True si txt est palindrome et False sinon.
ATTENTION AU TYPE : la fonction renvoie un booléen
le cas général doit donc renvoyer un booléen.
Quand on crée une liste on écrit par exeemple des choses comme :
return [a] + fonction(paramètres)
Dans le cas de booléen ce sera focéement :
return condition1 AND (ou OR) condition2
Vous noterez aussi que si le mot n'a qu'une seule lettre ou aucune lettre, il est forcément un palindrome.
Ecrire l'expression booléenne qu'il vaut tester.
Le cas général s'écrire donc : return condition1 and condition2
Et pour le cas de base, si la chaine est vide ou si la chaine ne contient qu'un caractère, que doit on renvoyer ?
Exercice 4
on veux tester si un lettre apparait dans un mot :
def appartient( lettre:str , mot:str ) -> bool :
Pour le cas général, il sera en deux parties :
On a trouvé la lettre :
dans ce cas :
ou bien on ne 'a pas trouvée :
Mais on pourrait l'écrire en une ligne, avec les même conditions que ci-dessus, mais qu'allez vous écrire entre les deux ?)
