Correction : principes de la récursivité

La fonction mystère

def f(a, n):
	if n == 0:
		return 0 
	return a + f(a, n-1)
			

Cas de base : lignes 3 et 4

Cas général : ligne 5

La fonction prend 2 paramètres, a et n. Le premier n'est jamais modifié, le deuxième diminue de 1 à chaque appel récursif.

→ exemple pour a = 2 et n = 3 :

→ la fonction fait donc le produit de a par n.

Fonction puissance

Version itérative

def puissance(y:int, x: int)->int:
	p = 1
	for i in range(x):
		p = p * y
	return p
			

Version récursive

Cas général

Prenons l'exemple de x = 4 ( et y n'importe quelle valeur ) :

• y⁴ = y * y * y * y = y * y³ soit : puissance(y, 4) = y * puissance(y, 3)
• y³ = y * y * y = y * y² soit : puissance(y, 3) = y * puissance(y, 2)
• y² = y * y = y * y¹ soit : puissance(y, 2) = y * puissance(y, 1)
• y¹ = y * 1 = y * y⁰ soit : puissance(y, 1) = y * puissance(y, 0)
• y⁰ = 1 : Cas de base !

Donc : y^x = y * y^x-1, soit : puissance(y, x) = y * puissance(y, x - 1)

Cas de base

On arrête la récursion quand x == 0, et on renvoie alors 1.

(Remarque : pour "économiser" un appel récursif, on peut aussi prendre comme cas de base : quand x == 1, renvoyer y...)

Fonction complète

def puis_recurs(y: int, x: int)->int:
	if x == 0 : 
		return 1
	else:
		return y * puis_recurs(y, x-1)
			

Construire une chaîne

Cas général

Prenons par exemple i = 1 et n = 5 : la chaîne renvoyée par la fonction devra donc être "12345"

• '12345' = '1' + "2345" soit : chaine(1, 5) = '1' + chaine(2, 5)
• '2345' = '2' + "345" soit : chaine(2, 5) = '2' + chaine(3, 5)
• '345' = '3' + "45" soit : chaine(3, 5) = '3' + chaine(4, 5)
• '45' = '4' + "5" soit : chaine(4, 5) = '4' + chaine(5, 5)
• '5' = '5', plus rien à concaténer : Cas de base !

On en déduit donc que pour toute valeur de i : chaine(i, n) = i + chaine(i+1, n)

Cas de base

Quand i == n, on renvoie le dernier nombre à concaténer, à savoir n ( ou i, ils sont alors égaux 😏 )

Fonction complète

def chaine(i: int, n: int)->str:
	if i == n:
		return str(i)  # attention au transtypage indispensable int -> str !
	else:
		return str(i) + chaine(i+1, n)	
			

Caractère dans une chaîne

Cas général :

Ici, il faut voir que l'on va se contenter de "parcourir" la chaîne caractère après caractère depuis le premier : pour cela, on appelle la fonction en lui passant comme paramètre à chaque appel récursif, la chaîne, le caractère à rechercher et un troisième paramètre servant de "pointeur d'index" qui sera incrémenté à chaque appel récursif ( ceci jouant donc le rôle d'une itération du type : for caractere in chaine ).

Cas de base :

Il y en a en fait deux ici :

• on parcourt la chaîne caractère après caractère; si on arrive au bout de la chaîne sans avoir trouvé le caractère recherché, c'est donc qu'il n'y est pas et dans ce cas on renvoie False.
• mais on doit aussi arrêter la récursion si on trouve le caractère recherché, qui peut être en n'importe quelle position : à chaque appel récursif, on va donc comparer le premier caractère de la chaîne, à celui recherché : si ils correspondent, on renvoie True.
  Tous les caractères étant "balayés" par la récursion, on les examine bien tous les uns après les autres.

→ fonction complète :

	
def est_dans(ch: str, car: str, n = 0)->bool: # n = index du caractère "en cours", initialisé à 0 par défaut
    if n == len(ch): # cas de base : on est arrivé en bout de chaîne -> caractère pas trouvé
        return False
    if ch[n] == car: # cas de base : caractère d'indice n dans la chaîne == caractère recherché -> caractère trouvé
        return True
    else:
        return est_dans(ch ,car, n+1) # appel récursif en incrémentant n de 1 à chaque appel
        

	
........
    else:
        est_dans(ch ,car, n+1) # appel récursif en incrémentant n de 1 à chaque appel