T 3.3 Exercices recursivité

Les classiques

Ces exercices se rapprochent de l'exponentiation. On écrit par exemple des chose comme :

Avec un seul paramètre :

• f(n) = 1 + f(n-1)
• f(n) = 2 * (n-1)
• f(n) = n + f(n-1)
• f(txt) = txt[0] + f(txt[1:])
• f(lst) = [ lst[0] ] + f( lst[1:] )
• f(lst) = lst[0] < lst[1] and f( lst[1:] )

ou avec deux paramètres, on trouvera des choses comme :

• f(a, n) = a * f(a, n-1)
• f(a, n) = 1 + f(a, n-1)
• f(x , lst) = (x == lst[0]) or f(x , lst[1:] ) # ! la fct renvoie un booléen
• f(lettre,txt) = ( lettre == txt[0] ) + f(lettre,txt[1:]) # ! La fct renvoi un int

Pour les booléens il y a parfois quelques subtilités....

f(x , lst) = (x == lst[0]) or f(x , lst[1:] ) # ! la fct renvoie un booléen

rappellez vous que pour évaluer condition1 or condition2 python n'évalue condition2 que si condition1 s'évalue à False.

En d'autres termes, si x==lst[0] est True, on ne fera pas l'appel récursif ! C'est ce qu'on fait dans appartient(x,lst), quand on le trouve, plus besoin de continuer... 

f(lettre,txt) = ( lettre == txt[0] ) + f(lettre,txt[1:]) # ! La fct renvoi un int

bool + bool -> int
bool + int -> int

exemple :
False + False s'évalue à 0 (False est converti en 0, True en 1)
False + 3 s'évalue à 3
True + 1 s'évalue à 2

a = 1
print( (a==1) + 1 )

Dans la récursion cela peut être parfois bien utile, mais on pourrait s'en tirer autrement (et c'est recommandé si ce qui précède ne vous semble pas clair pour vous) :

f(lettre,txt) = ( lettre == txt[0] ) + f(lettre,txt[1:]) # ! La fct renvoi un int

sera identique à :
if lettre == txt[0] :
     n = 0
else :
     n = 1
return n + f(lettre,txt[1:])

c'est juste plus facile de lire le code en une ligne que le code 
de 5 lignes.... 
il est plus élégant, mais recommandé seulement quand on maitrise 
bien les problèmes de typages des expressions.

La chose vraiment à retenir : respectez les types ! Si la fonction renvoie une list, les return (du cas de base comme du cas général) devront renvoyer une list. si on veux construire la list en ajoutant un nombre à chaque appel, le return du cas général sera forcément du genre : return [a] + f(...) Les ... indique qu'on rapelle la fonction avec de nouveaux paramètres (une liste modifiée, ou un paramètre avec une valeur modifiée etc...)

ex 1 - somme de n entiers

Exercice de code : somme

Ecrire une fonction récursives somme qui prendra en argument un nombre n, et qui renvoie la somme des n premiers entiers jusqu'à n.
Exemple : somme(4) renvera 10 (1 + 2 + 3 + 4 = 10)

Vous devez créer un compte et vous connecter avant de poser une question.

def somme(n: int) -> int: """ :param n: int : n positif ou nul :returns: int : la somme des entiers de 0 à n """ pass

Plus d'actions... Réinitialiser code Aide

ex 2 - addition unitaire

Dans cet exercice nous voulons calculer la somme a + b, mais de façon très basique.

Imaginez deux tas, à gauche a cailloux et à droite, b cailloux.

pour ajouter b à a, je passe les cailloux UN PAR UN du tas de droite au tas de gauche.

je compte donc jusqu'à a, puis a chaque cailloux ajouté, j'augmente de 1, et le tas de droite diminue. Quand le tas de droite est vide, je sais combien vaut a + b.

Ce processus est similaire à la fonction récursive demandée ci-dessous.

Exercice de code : Addition unitaire

Ecrire une fonction somme qui renvoi la somme a+b en utilisant seulement les opération +1 ou -1

Exemples:
somme(2,4) renvoie 6 (sans jamais écrire 2+4)

Vous devez créer un compte et vous connecter avant de poser une question.

def somme(a:int , b: int) -> int: """ :param a: int: positif ou nul :param b: int:positif ou nul :returns: int : la somme a + b contrainte : vous ne pouvez que ajouter ou retrancher 1, ce snt les seules opérations autorisées. """ pass print(somme(3,3))

Plus d'actions... Réinitialiser code Aide

ex 3 - longueur

Exercice de code : Longueur d'une chaine

Ecrire une fonction longueur qui renvoi la logueur d'une chaine

CONTRAINTE : vous ne devez pas utiliser for, while ou len.

Vous devez créer un compte et vous connecter avant de poser une question.

def longueur(txt:str) -> int: """ :param txt: str: vide ou non :returns: int : la longueur de la chaine """ pass print(longueur("abc")) print(longueur(""))

Plus d'actions... Réinitialiser code Aide

ex 4 - my_range

Dans cet exercice nous allons écrire un substitut de la fonction range()

Exercice de code : my_range()

Ecrire une fonction my_range qui renvoi une liste contenant les entiers de a à b-1.

CONTRAINTE : vous ne pouvez pas utiliser de boucle for ou while ni de liste en compréhension, ni la fonction range()

Vous devez créer un compte et vous connecter avant de poser une question.

def my_range(a:int , b: int) -> int: """ :param a: int: positif ou nul :param b: int:positif ou nul :returns: list: une liste contenant les entiers de a à b-1 si a > b : la fonction renvoi None si a = b : la fonction renvoie [] """ pass # code de test et validation : for i in my_range(3,5) : print(i) print("my_range(3,3) :",my_range(3,3)) print("my_range(3,2) :",my_range(3,2))

Plus d'actions... Réinitialiser code Aide

Avec des chaînes de charactères

Le principe sera le même : décomposer le problème en une opération simple et une répétition du problème légèrement simplifié.

Dans les exercices qui suivent, essayez de comprendre comment on peut décomposer le problème, cela vous indiquera la solution.

ex 5 - repeteur

Exercice de code : Begaiement

Ecrire une fonction récursive repeat qui prendra en argument un nombre n et une chaine de caractère txt, et qui renvoie une chaine de caractères qui contient n fois la chaine de caractères txt.
Exemple: repeat(5, "bla") renvoie blablablablabla
Aide

Vous devez créer un compte et vous connecter avant de poser une question.

def repeat(n: int, txt: str) -> str: """ :param n: de type entier. Nombre de fois que l'on recopie la chaîne de caractères. :param txt: de type str. Chaine de caractères que l'on doit répéter. """ pass

Plus d'actions... Réinitialiser code Aide

ex 6 - reverse

Exercice de code : retournement

Ecrire une fonction récursive reverse qui prendra en argument une chaine de caractère txt, et qui renvoie la même chaine de caractères écrite à l'envers.
Exemple: reverse("bla") renvoie alb
Aide 1 Aide 2

Vous devez créer un compte et vous connecter avant de poser une question.

def reverse(txt: str) -> str: """ :param n: de type entier. Nombre de fois que l'on recopie la chaîne de caractères. :param txt: de type str. Chaine de caractères que l'on doit retourner. : returns" la chaine retournée >>> reverse("Hello") olleH """ pass

Plus d'actions... Réinitialiser code Aide

ex 7 - Anagrammes

Exercice de code : Anagrammes

Vous devez créer un compte et vous connecter avant de poser une question.

def isanagramme(s1,s2) : """ :params s1 et s2: 2 chaines non vides et non égales :returns:True si les 2 chaines sont anagrammes (mêmes lettres dans un ordre diffrent) """

Plus d'actions... Réinitialiser code Aide

ex 8 - la tête à toto

Dans cet exercice vous pouvez utiliser la méthode replace des objets string :

Testez dans un environnement python ou dans la console pour bien comprendre le fonctionnement de la méthode replace.

exemple

s = 'abacab'
print(s.replace('b','B'))
print(s.replace('b','B',1))
print(s.replace('bac','BAC'))

Quand vous avez bien compris le fonctionnement de replace(), il faut réfléchir au problème sur un cas simple.
Que renverront ces appels :

tete_a_toto('---0---' , 1) ?
tete_a_toto('---0---' , 2) ?
tete_a_toto('---0---' , 0) ?

Que faites vous à chaque fois ?

Exercice de code : La tête à toto

Ecrire une fonction tete_a_toto qui répète n fois la substitution suivante : Remplacer tout les 0 par (0 + 0)


Exemples:
tete_a_toto("0",1) renvoie (0 + 0)
tete_a_toto("0",2) renvoie ((0 + 0) + (0 + 0))
Aide 1

Vous devez créer un compte et vous connecter avant de poser une question.

def tete_a_toto(txt:str , n: int) -> str: """ :param txt: str : chaine de caractère contenant au moins un 0 :param n: de type entier. Nombre de fois que l'on effectue le remplacement des 0 par (0+0). :returns: type str. Chaine de caractères obtenue. """ pass print("0 = ",tete_a_toto("0",3))

Plus d'actions... Réinitialiser code Aide

ex 8 - Affichage récursif

Si vous avez réussit les 2 exercices précédents, celui là devrait vous sembler assez simple.

Exercice de code : Print inline

Affichage d'une suite d'entiers Ecrire une fonction récursive printInLine qui prend 2 arguments i et k, et affiche les entiers entre i et k compris.


Par exemple :
printInLine(2, 5) doit afficher : 2 3 4 5 (séparés par des espaces).
Attention : printInLine ne renvoie rien, elle ne fait que des affichages....

Vous pourrez utiliser print(...,end=...) pour faire ce travail.
Aide 1 Aide 1

Vous devez créer un compte et vous connecter avant de poser une question.

def printInLine(i: int, k: int ) -> None : """ :param i: de type entier. C'est le premier entier affiché :param k: de type entier. C'est le dernier entier affiché :returns: None. """ pass

Plus d'actions... Réinitialiser code Aide

Avec une liste

ex 9 - test tri

Exercice de code : Rangement

Ecrire une fonction récursive estTriee qui prend un argument tableau de type list, et qui renvoie True si le tableau est trié par ordre croissant, False sinon.

Par exemple, Si T1 = [1, 2, 3, 4, 5, 7, 8] et T2 = [1, 3, 2, 4, 5, 7, 8]
print(estTriee(T1)) affichera True
print(estTriee(T2)) affichera False
Aide 1

Vous devez créer un compte et vous connecter avant de poser une question.

def estTriee(tableau: list ) -> bool : """ :param tableau de type list : liste de nombres entiers :returns: de type booléen: True si la liste est triée croissante, False sinon. """ pass

Plus d'actions... Réinitialiser code Aide

Des algos un peu plus complexes

ex 10 - somme digitale

Exercice de code : Somme digitale

La somme digitale d'une nombre n est la somme de ces chiffres. Ecrivez une fonction récursive sommeDigital(n) qui prend en entrée un nombre positif n et retourne sa somme digitale. Par exemple, sommeDigital(2019) retournera 12 car 2 + 0 + 1 + 9 = 12. Indice #1 Indice #2 Indice #3

Vous devez créer un compte et vous connecter avant de poser une question.

def sommeDigital(n): """ :param n: de type int. C'est l'entier dont on va renvoyer la somme de chiffres :returns: de type entier. C'est la somme des chiffres de n """ pass

Plus d'actions... Réinitialiser code Aide

ex 11 - Conversion

On rappelle l'algorithme qui permet de convertir un nombre entier écrit en décimal en une chaine binaire équivalente.

fonction dec2bin(n) :
    chaine = ""
    tant que n est non nul :
        chaine = str(n%2) + chaine # on ajoute le reste de n/2 en tête dans la chaine
        n = n//2 # on recommence avec le quotient de n/2
    fin tant que
    renvoyer chaine
      

Exercice de code : Division successives

Ecrire une fonction récursive dec2bin qui prend un argument un nombre entier, et qui affiche la représentation binaire de ce nombre (en chaine de caractères). Vous utiliserez la méthode des divisions successives par 2.
Par exemple, dec2bin(127) doit afficher 1111111

Vous devez créer un compte et vous connecter avant de poser une question.

def dec2bin(n: int) -> str: """ :param n: de type int. C'est l'entier décimal que l'on va convertir en binaire :returns: de type str. C'est la chaîne de caractères donnant n converti en binaire. """ pass

Plus d'actions... Réinitialiser code Aide

Avec deux fonctions qui s'appellent mutuellement

ex 12 - Exercice Pair Impair

Dans cet exercice, vous ne pouvez utiliser Vous ne devez utiliser les opérateur % et / ou //

Exercice de code : pair impair

Ecrire 2 fonctions récursives est_pair et est_impair, qui s'appeleront mutuellement pour arriver à la solution. La fonction est_pair renvoie True si le nombre n est pair, False sinon, et inversement la fonction est_impair renvoie True si n est impair, False sinon.
On ne peut pas utiliser %,/ ou //.A vous de jouer. Indice

Vous devez créer un compte et vous connecter avant de poser une question.

def est_pair(n: int) -> bool : """ :param n: de type int. :returns: de type bool. Renvoie True si n est pair, False si n est impair """ pass def est_impair(n: int) -> bool: """ :param n: de type int. :returns: de type bool. Renvoie True si n est impair, False si n est pair """ pass

Plus d'actions... Réinitialiser code Aide