Remarque.

Si une fonction récursive fait appel à elle-même systématiquement pour n'importe quelle valeur du paramètre, le nombre d'appels successifs d'une fonction récursive sera infini. C'est pourquoi, pour certaines valeurs du paramètre, une fonction récursive ne fait pas appel à elle-même.

Remarque.

La définition d'une fonction récursive est donc constituée :

• du traitement d'un ou plusieurs cas de base,
• d'un ou plusieurs appels récursifs.

Le programme ci-dessous est une procédure récursive (cette fonction ne renvoie rien).

def proc_recursive(i): """Précondition : i > 0 affiche les valeurs de i récursivement""" print ("Début de procédure") # cas de base : if i<1: print ("Fin de procédure") # Appel récursif else : print("i =",i) proc_recursive(i-1) print("Retour de procédure") print ("i =",i) proc_recursive(3)

Exécuter le code

• a) Indiquer dans l'ordre, le numéro des lignes exécutées par le programme pour l'appel : proc_recursive(1)
• b) Quelle est la valeur d'arrêt ?

Réponses :

• Modifier le programme afin de faire un 5000 appels récursifs. Avant d'exécuter le programme, ouvrir le gestionnaire des taches et observez l'évolution de la taille mémoire occupée par votre navigateur Internet lors de l'exécution du programme.

La récursivité est gourmande en mémoire car on doit empiler toutes les données (variables, adresses de retour, ...) avant l'appel de la procédure récursive. On parle d'une pile d'exécution. Ces valeurs seront dépilées lors du retour. Notez que la variable i est une variable locale de chaque procédure. La taille de la pile est limitée par l'espace mémoire alloué ici par le navigateur Internet qui est de l'ordre de 5000. Cette taille peut être augmentée avec l'instruction suivante :

import sys
sys.setrecursionlimit('Taille')

Non reconnue sur ce site

La Fonction récursive suivante permet, de calculer la factorielle d'un nombre entier

Rappel : la factorielle d'un entier naturel n est le produit des nombres entiers strictement positifs inférieurs ou égaux à n. Cette opération est notée avec un point d'exclamation, n!.

Exemple : 5! = 5*4*3*2*1

Une boucle for permet de résoudre le problème, mais nous allons résoudre le problème de manière récursive

Avant de programmer on commence par identifier le cas de base ici : si n=1 alors on renvoie 1

Algorithme :

Fonction factorielle
paramètres :
	n : un entier strictement positif et supérieur à 1
retourne un entier :
	le résultat du calcul

début
	# Cas de base :
	si n≤1 alors 
		retourner 1
	# Appel récursif :
	sinon 
		retourner n*factorielle(n-1)
fin

Simulation pour n=3

factorielle (3)
	retourne 3 * factorielle (3-1)
		retourne 2 * factorielle (2-1)
			retourne 1	(n==1 condition de fin)
		2 * 1
	3 * 2 * 1
retourne (6)

Principe de fonctionnement de la pile

Ecrire la fonction récursive factorielle en langage python et testez la fonction avec différentes valeurs de n

Exécuter le code

Exercice 1 ★

Écrire une procédure récursive compte qui :

• prend en paramètre un entier positif n
• affiche les entiers de 0 à n.

Exécuter le code

Exercice 2 ★

Écrire une procédure récursive décompte qui :

• prend en paramètre un entier positif n
• affiche les entiers de n à 0.

Ce programme ne diffère que très peu par rapport à l'exercice 1

Exécuter le code

Exercice 3★

Écrire une fonction récursive somme_entiers qui :

• prend en paramètre un entier positif ou nul n,
• retourne la somme des entiers de 0 à n.

Vérifiez que la somme des n premiers entiers est bien égal à

Exécuter le code

Exercice 4★

Écrire une fonction récursive nombre_de_chiffre qui :

• prend en paramètre un entier n,
• Retourne le nombre de chiffres de n.

Exécuter le code

Exercice 5★★

Écrire une fonction récursive renverse qui :

• prend en paramètre une chaîne de caractères,
• retourne la chaîne de caractères renversée.

Par exemple renverse("ados") devra retourner "soda". Vous pouvez esssayer d'autres mots anacycliques : bons, super, saper, retartiner, trop ...

Rappel sur la manipulation des chaines de caractères:

>>>chaine ="soda"
>>>print(chaine[1:])
oda

Exécuter le code

Exercice 6★★

La suite de Fibonacci est la suite dont les premiers termes valent : 0, 1, 1, 2, 3, 5, 8, 13, . . .

Dans cette suite, chaque terme est la somme des deux précédents.

Écrire une fonction récursive fibo qui :

• prend en paramètre un entier n,
• retourne le terme d'indice n de cette suite.

Par exemple :

fibo(0) devra retourner 0,
fibo(1) devra retourner 1,
fibo(6) devra retourner 8.

Exécuter le code

Exercice 7★★

Ecrire une fonction récursive min_rec qui prend en paramètre un tableau d'entiers tab, un indice de liste indice et indice_min en entier qui représente l'indice du minimum.

La fonction min_rec doit retourner un uplet contenant le plus petit élément de la liste tab et son indice.

def min_rec(tab,indice=?,indice_min=?): '''list[int],int,int ->uplet précondition : une liste non vide hypothèses : indice=1, indice_min = 0 au premier appel de la fonction Retoune le plus petit élément de la liste et son indice''' # condition d'arrêt if ? # appel récursif else: ? print(min_rec([1,2,3,-10,-20])) assert min_rec([1,2,3,-10,-20])==(-20,4) assert min_rec([-20,5,2])==(-20,0) assert min_rec([8,5,0,2])==(0,2) print('La fonction est vérifiée')

Exécuter le code

Exercice 8★

Compléter la fonction recursive rendu_monnaie qui prend en paramètre un entier : une somme à rendre a_rendre et une liste d'entiers de billets et de pièces bp=[100, 50, 20, 10, 5, 2, 1] et qui retourne une liste contenant les billets et pièces à rendre.

Compléter le code Python ci-dessous de la fonction rendu_monnaie.

def rendu_monnaie(a_rendre,bp): ''' ??? ''' if a_rendre == ?: return [] v = bp[?] if v <= ? : return [?] + rendu_monnaie(a_rendre - v,bp) else : return rendu_monnaie(a_rendre, ...) print(rendu_monnaie(268,[100, 50, 20, 10, 5, 2, 1]))

Exécuter le code

Exercice 9★

a) Ecrire une fonction recursive recherche_occurrence qui prend en paramètre une liste d'entiers tabet un entier val.

La fonction retourne un entier qui compte le nombre de fois que val se trouve dans tab.

def recherche_occurrence(tab,val,n=?): ''' précondition : hypothèse : n = ? à l'appel de la fonction représente le nombre d'occurrence ''' print(recherche_occurrence([1,5,8,5,-1],1))

Exécuter le code

b) Ecrire une variante de la fonction récursive précédente que vous nommerez recherche_occurrence2 qui n'utilise plus la variable n

Exercice 10★

Compléter la fonction recursive est_trie qui prend en paramètre une liste d'entiers tab.

La fonction retourne True si le tableau est trié par ordre croissant sinon False.

def est_trie(tab): ''' précondition : ''' if len(tab)< 2 : return ? if tab[0]>tab[1] : return ? else: return est_trie(?) print (est_trie([])) print (est_trie([0,8,9,10,-5]))

Exécuter le code