¶ Un module d'aide
Pour cette activité, vous aurez également besoin du fichier python outils_recursivite.py disponible ci-dessous.
Déposez-le dans le même dossier que le sujet du TP. Pour l'importer, il faut écrire la ligne suivante :
from outils_recursivite import trace
Le module permet d'obtenir la trace d'exécution d'une fonction, et ainsi pouvoir observer les différents appels récursifs. Il s'utilise de la manière suivante :
@trace
def mafonction(n):
return
¶ Exercice 1 - Des fonctions récursives
Question 1 - Écrire une fonction récursive factorielle permettant de calculer la factorielle d'un nombre passé en paramètre.
def factorielle(nombre:int) -> int :
Question 2 - Écrire une fonction récursive somme_entier permettant de calculer la somme des nombres entiers de 0 jusqu'au nombre passé en paramètre.
def somme_entier(nombre:int) -> int :
Question 3 - Écrire une fonction récursive puissance permettant de calculer un nombre x à la puissance p.
def puissance(x:int, p:int) -> int :
Question 4 - Tester vos fonction à l'aide du module outils_recursivite.py.
¶ Exercice 2 - Suite de Fibonacci
La suite de Fibonacci est définie comme suit :
Question 1 - Écrire la fonction fibo() permettant de calculer la suite de Fibonacci.
¶ Exercice 3 - Répétition
On souhaite écrire une fonction récursive repeter qui prend en paramètre une chaine de caractère et un nombre entier. Cette fonction permet d'afficher un mot plusieurs fois en fonction des paramètres indiqués.
Question 1 - Écrire la fonction repeter de manière récursive. Pour vous aider, vous pouvez réfléchir aux questions suivantes :
- Quel peut être le cas de base ?
- Que retourne la fonction ?
def repeter(mot, nb_fois):
'''
:param mot: (str) Le mot à afficher
:param nb_fois: (int) Le nombre de fois à répéter
:return: None
'''
pass
¶ Exercice 4 - Intervalle
On souhaite écrire une fonction récursive intervalle qui prend en paramètre deux nombres entiers. Cette fonction affiche les nombres présents dans l'intervalle.
Question 1 - Écrire la fonction intervalle(a,b) de manière récursive.
def intervalle(a,b):
'''
:param a: (int) Nombre de départ
:param b: (int) Nombre de fin
:return: None
'''
pass
¶ Exercice 5 - Appartenance
Question 1 - Écrire une fonction récursive appartient qui prend en paramètre un nombre entier / un caractère et une liste. Cette fonction retourne True si le paramètre est bien présent dans la liste, False sinon.
def appartient(i, liste):
'''
:param i: (int/char) Nombre ou caratère à chercher dans la liste
:param liste: (list) Une liste de valeur
:return: (bool)
'''
pass
¶ Exercice 6 - Palindrome
Un palindrome est un mot qui se lit dans les deux sens comme « kayak » ou « radar ».
Question 1 - Écrire une fonction itérative est_palindrome. Cette fonction prend en paramètre un mot et retourne True si le mot passé en paramètre est un palindrome, False sinon.
def est_palindrome(mot):
'''
:param mot: (str) Le mot
:return: (bool)
'''
pass
Essayons maintenant d'écrire une version récursive. Pour vous aider, le mot « radar » est un palindrome si "r"=="r" et "ada" est un palindrome.
Question 2 - Réfléchir au choix du cas de base.
Question 3 - Écrire une version récursive de la fonction est_palindrome.
def est_palindrome_recursif(mot):
'''
:param mot: (str) Le mot
:return: (bool)
'''
pass
¶ Exercice 7 - Mini et maxi
Question 1 - Écrire une fonction récursive maxi qui prend une liste en paramètre. Cette fonction retourne le nombre maximum de la liste passée en paramètre
def maxi(l):
'''
:param l: (list) Une liste de valeur
:return: (int)
'''
pass
¶ Exercice 8 - Conversion
Question 1 - Compléter la fonction decimal_to_binaire. Cette fonction prend en paramètre en nombre en base 10 et retourne une liste de nombres (0 ou 1) correspondant à la représentation binaire du nombre.
def nombre_en_binaire(nombre):
'''
:param nombre: (int) Le nombre à convertir
:return: (list)
'''
if nombre == ??????:
return ?????
else:
return ?????
¶ Exercice 9 - Les chiffres romains
On souhaite écrire une fonction permettant de donner la valeur d'un nombre écrit en chiffres romains.
On définit les règles suivantes :
- Si le nombre romain a un seul caractère : on retourne la valeur correspondante (I=1, V=5, X=10...)
- Si le premier caractère d'un nombre romain a une valeur inférieure au deuxième : on soustrait cette valeur à la suite des appels récursifs avec le reste des caractères.
- Si le premier caractère d'un nombre romain a une valeur supérieure au deuxième : on additionne cette valeur à la suite des appels récursifs avec le reste des caractères.
Évidemment, pour calculer la suite des calculs, il faut appliquer à nouveau ce principe, ce qui rend ce principe récursif.
Question 1 - Compléter la fonction récursive conversion.
def conversion(t):
'''
:param t: (str)
:return: (int)
'''
pass