#******************Correction TD3*******************
#***************************************************
#****************Exercice1**************
def mafonction(ch,a):
if len(ch)>0:
n=mafonction(ch[1:],a)
if ch[0]==a:
return n+1
else:
return n
else:
return 0
#Test
ch=input("entrer une chaîne de caractère: ")
c=input("entrer un caractère: ")
print (mafonction(ch,c))
#******************Exercice2**********************
def est_trie(T):
if len(T)==0 or len(T)==1:
return True
if T[0]<T[1]:
return est_trie(T[1:])
else:
return False
#Programme principal
#T=[1,2,3,4]#tableau trié
T=[2,6,1,9]#tableau non trié
if est_trie(T)==True:
print("le tableau T=",T,"est trié")
else:
print("le tableau T=",T,"n'est pas trié")
#****************Exercice3***********************
def sum_carre_inv(n):
if n == 1:
return 1
else:
return 1/n**2 + sum_carre_inv(n-1)
#Test
n=int(input("Entrer le nbre de termes à calculer: "))
while(n<1):
n=int(input("entrer un entier strictement positif"))
print("la somme des inverses des carrés des ", n," premiers termes est: ")
print(sum_carre_inv(n))
#****************Exercice4**********************
def Fib (n):
if n==0:
return 0
elif n<=2:
return 1
else:
return Fib(n-1)+Fib(n-2)
#Calcul de 10 premiers termes
for i in range(11):
print("Fib(",i,")= ",Fib(i))
MIP – Informatique 2 : Algorithme 2 /Python
TD3- Récursivité
Exercice 1
Exécution
Détails d’execution
Appels recursifs Valeurs de retour
• 𝑐ℎ = "MOM", 𝑎 = "M", 𝑚𝑎𝑓𝑜𝑛𝑐𝑡𝑖𝑜𝑛("MOM", "M")
• 𝑚𝑎𝑓𝑜𝑛𝑐𝑡𝑖𝑜𝑛("𝑀𝑂𝑀", "𝑀") = 𝑚𝑎𝑓𝑜𝑛𝑐𝑡𝑖𝑜𝑛("OM", "M") + 1
• 𝑙𝑒𝑛(𝑐ℎ) = 3 > 0,
• 𝑐ℎ[1: ] = "𝑂𝑀" 𝑚𝑎𝑓𝑜𝑛𝑐𝑡𝑖𝑜𝑛("𝑀𝑂𝑀", "M") = 1 + 1 = 2
• n=𝑚𝑎𝑓𝑜𝑛𝑐𝑡𝑖𝑜𝑛("𝑂𝑀", "𝑀")
• 𝑐ℎ[0] == "𝑀" --> True
• 𝒓𝒆𝒕𝒖𝒓𝒏 𝒏 + 𝟏
• 𝑐ℎ = "OM", 𝑎 = "M", 𝑚𝑎𝑓𝑜𝑛𝑐𝑡𝑖𝑜𝑛("OM", "M") = 𝑚𝑎𝑓𝑜𝑛𝑐𝑡𝑖𝑜𝑛("𝑀", "𝑀")
• 𝑚𝑎𝑓𝑜𝑛𝑐𝑡𝑖𝑜𝑛("𝑂𝑀", "𝑀")
• 𝑙𝑒𝑛(𝑐ℎ) = 2 > 0, 𝑚𝑎𝑓𝑜𝑛𝑐𝑡𝑖𝑜𝑛("𝑂𝑀", "M") = 1
• 𝑐ℎ[1: ] = "𝑀"
• n=𝑚𝑎𝑓𝑜𝑛𝑐𝑡𝑖𝑜𝑛("𝑀", "𝑀")
• 𝑐ℎ[0] == "𝑂" --> False
• 𝒓𝒆𝒕𝒖𝒓𝒏 𝒏
• 𝑐ℎ = "M", 𝑎 = "M", 𝑚𝑎𝑓𝑜𝑛𝑐𝑡𝑖𝑜𝑛("𝑀", "M") = 𝑚𝑎𝑓𝑜𝑛𝑐𝑡𝑖𝑜𝑛("", "M") + 1
• 𝑚𝑎𝑓𝑜𝑛𝑐𝑡𝑖𝑜𝑛("𝑀", "𝑀")
• 𝑙𝑒𝑛(𝑐ℎ) = 1 > 0,
• 𝑐ℎ[1: ] = "" 𝑚𝑎𝑓𝑜𝑛𝑐𝑡𝑖𝑜𝑛("𝑀", "M") = 0 + 1 = 1
• n=𝑚𝑎𝑓𝑜𝑛𝑐𝑡𝑖𝑜𝑛("", "𝑀")
• 𝑐ℎ[0] == "𝑀" --> True
• 𝒓𝒆𝒕𝒖𝒓𝒏 𝒏 + 𝟏
• 𝑐ℎ = "", 𝑎 = "M", 𝑚𝑎𝑓𝑜𝑛𝑐𝑡𝑖𝑜𝑛("", "M") = 0
• 𝑚𝑎𝑓𝑜𝑛𝑐𝑡𝑖𝑜𝑛("", "𝑀")
• 𝑙𝑒𝑛(𝑐ℎ) = 0,
• 𝒓𝒆𝒕𝒖𝒓𝒏 𝟎 →Condition
d’arrêt
1
La fonction 𝒎𝒂𝒇𝒐𝒏𝒄𝒕𝒊𝒐𝒏(𝒄𝒉, 𝒂) permet de calculer le nombre d’occurrences d’un caractère a
dans une chaîne ch. Dans le programme principal, on a appelé la fonction pour calculer le
nombre d’occurrences du caractère ‘M’ dans la chaîne "MOM". Après trois appels récursifs, on
est arrivée à la condition d’arrêt.
Exercice 2
a. Cas tableau trié T=[1,2,3,4]
Appels récursifs Valeurs de retour
• 𝑇 = [1,2,3,4] 𝑒𝑠𝑡_𝑡𝑟𝑖𝑒([1,2,3,4])
• 𝑒𝑠𝑡_𝑡𝑟𝑖𝑒([1,2,3,4]) = 𝑒𝑠𝑡_𝑡𝑟𝑖𝑒([2,3,4])
• 𝑙𝑒𝑛(𝑇) = 4 > 1,
• 𝑇[0] < 𝑇[1] 𝑒𝑠𝑡_𝑡𝑟𝑖𝑒([1,2,3,4]) = 𝑇𝑟𝑢𝑒
• 𝑇[1 : ] = [2,3,4]
• 𝒓𝒆𝒕𝒖𝒓𝒏 𝒆𝒔𝒕_𝒕𝒓𝒊𝒆([2,3,4])
• 𝑇 = [2,3,4] 𝑒𝑠𝑡_𝑡𝑟𝑖𝑒([2,3,4])
• 𝑒𝑠𝑡_𝑡𝑟𝑖𝑒([2,3,4]) = 𝑒𝑠𝑡_𝑡𝑟𝑖𝑒([3,4])
• 𝑙𝑒𝑛(𝑇) = 3 > 1,
• 𝑇[0] < 𝑇[1] 𝑒𝑠𝑡_𝑡𝑟𝑖𝑒([2,3,4]) = 𝑇𝑟𝑢𝑒
• 𝑇[1 : ] = [3,4]
• 𝒓𝒆𝒕𝒖𝒓𝒏 𝒆𝒔𝒕_𝒕𝒓𝒊𝒆(𝑻[3,4])
• 𝑇 = [3,4] 𝑒𝑠𝑡_𝑡𝑟𝑖𝑒([3,4]) = 𝑒𝑠𝑡_𝑡𝑟𝑖𝑒([4])
• 𝑒𝑠𝑡_𝑡𝑟𝑖𝑒([3,4])
• 𝑙𝑒𝑛(𝑇) = 2 > 1,
• 𝑇[0] < 𝑇[1] 𝑒𝑠𝑡_𝑡𝑟𝑖𝑒([3,4]) = 𝑇𝑟𝑢𝑒
• 𝑇[1 : ] = [4]
• 𝒓𝒆𝒕𝒖𝒓𝒏 𝒆𝒔𝒕_𝒕𝒓𝒊𝒆(𝑻[4])
• 𝑇 = [4] 𝑒𝑠𝑡_𝑡𝑟𝑖𝑒([4]) = 𝑇𝑟𝑢𝑒
• 𝑒𝑠𝑡_𝑡𝑟𝑖𝑒([4])
• 𝑙𝑒𝑛(𝑇) = 1,
• 𝒓𝒆𝒕𝒖𝒓𝒏 𝑻𝒓𝒖𝒆 →Condition d’arrêt
2
b. Cas tableau non trié T=[2,6,1,9]
Appels récursifs Valeurs de retour
• 𝑇 = [2,6,1,9] 𝑒𝑠𝑡_𝑡𝑟𝑖𝑒([2,6,1,9])
• 𝑒𝑠𝑡_𝑡𝑟𝑖𝑒([2,6,1,9]) = 𝑒𝑠𝑡_𝑡𝑟𝑖𝑒([6,1,9])
• 𝑙𝑒𝑛(𝑇) = 4 > 1,
• 𝑇[0] < 𝑇[1] 𝑒𝑠𝑡_𝑡𝑟𝑖𝑒([2,6,1,9]) = 𝐹𝑎𝑙𝑠𝑒
• 𝑇[1 : ] = [6,1,9]
• 𝒓𝒆𝒕𝒖𝒓𝒏 𝒆𝒔𝒕_𝒕𝒓𝒊𝒆([6,1,9])
• 𝑇 = [6,1,9] 𝑒𝑠𝑡_𝑡𝑟𝑖𝑒([6,1,9]) = 𝐹𝑎𝑙𝑠𝑒
• 𝑒𝑠𝑡_𝑡𝑟𝑖𝑒([6,1,9])
• 𝑙𝑒𝑛(𝑇) = 3 > 1,
• 𝑇[0] > 𝑇[1]
• 𝒓𝒆𝒕𝒖𝒓𝒏 𝑭𝒂𝒍𝒔𝒆→condition d’arrêt
