TD 03- La récursivité : Python
Exercice 1 :
La suite de Fibonacci est définie comme suit :
1, 𝑠𝑖 𝑛 < 2
𝐹𝑛 = {
𝐹𝑛−1 + 𝐹𝑛−2 𝑠𝑖𝑛𝑜𝑛
1. Ecrire un programme récursif calculant Fib(n)
Programme
Python
1 def Fib(n):
2 if n <=2:
3 return 1
4 return Fib(n -1)+ Fib(n -2)
5
6 print (Fib (4))
Exercice 2
Soit La suite définie par :
1, 𝑠𝑖 𝑛 < 2
𝑈𝑛 = {
3𝑈𝑛−1 + 𝐹𝑛−2 𝑠𝑖𝑛𝑜𝑛
1. Ecrire un programme récursif permettant de calculer le nième terme de la suite.
Programme(récursive) Programme(itérative)
Python Python
1 def Suite (n): 1 def Suite(n):
2 if n <=2: 2 a=1
3 return 1 3 b=1
4 return 3* Suite (n -1)+ Suite (n -2) 4 for i in range(2,n):
5
5 c=a+3*b
6 print ( Suite (4))
6 a= b
7 b=c
8 return c
#
9 print(Suite(4))
Exercice 3
Un nombre N est pair si (N-1) est impair, et un nombre N est impair si (N-1) est pair.
1. Ecrire deux fonctions récursives mutuelles pair (N)et impair (N) permettant de savoir si un
nombre N est pair et si un nombre N est impair.
Programme(récursive)
Python
1 def Pair (N):
2 if N ==1:
3 return False
4 return Impair (N -1)
5
6 def Impair (N):
7 if N ==1:
8 return True
9 return Pair (N -1)
#
print(Impair(8))
print(Pair(8))
Exercice 4
Soit un tableau X de N entiers.
1. Ecrire une fonction récursive simple permettant de déterminer le maximum du tableau
Programme
Python
1 def maximum (T):
2 if len(T )==1:
3 return T[0]
4 m=len(T )//2
5 max1 = maximum (T[:m])
6 max2 = maximum (T[m:])
7 if max1 > max2 :
8 return max1
9 return max2
10 L=[0,12,70,1,3,9,34,12,4,19]
11
12 print(maximum(L))
Exercice 5
Un tableau X est trié par ordre croissant si x(i) <= x(i + 1)
1. Elaborer un algorithme récursif permettant de vérifier qu’un tableau X est trié ou non
Programme
Python
1 def Esttrier (T):
2 if len(T )==0 or len (T )==1:
3 return True
4 if T[0] <=T [1]:
5 return Esttrier (T [1:])
6 return False
7
8 T=[1 ,2 ,3 ,4 ,4 ,5 ,7 ,8]
9 print ( Esttrier (T))
Exercice 6
Un mot est un palindrome si on peut le lire dans les deux sens de gauche à droite et de droite à
gauche. Exemple KAYAK est un palindrome.
1. Ecrire une fonction récursive permettant de vérifier si un mot est palindrome.
Programme(récursive) Programme(itérative)
Python Python
1 def palindrome (ch ): 1 def inverser(ch):
2 if len(ch )==1: 2 ch_inver =""
3 return True 3 for c in ch:
4 if ch [0]== ch [ -1]: 4 ch_inver = c+ch_inver
5 return palindrome (ch [1: len (ch ) -1]) 5 #
6 return False 6 return ch_inver
7 7 #
8 ch=" KAYAK " 8 def palindrome (ch ):
9 print ( palindrome (ch )) 9 ch_inver = inverser(ch)
10 etat = True
11 for i in range(len(ch)):
12 if ch[i] != ch_inver[i]:
13 etat = False
14 break
15 #
16 return etat
17 #
18 ch="bAYAK"
19 print ( palindrome (ch ))
