Récursivité d'ordre 1 sur une chaîne — décrire la récurrence, puis la programmer

Idée : sur un tableau, ce n'est pas le tableau qui rétrécit — il reste le même en mémoire. C'est le nombre de cases encore à additionner qui décroît : la récurrence porte sur k, pas sur T.

1. Relation. Cas d'arrêt : Som(T, 0) = 0, la somme d'aucune case. Cas général, pour k ≥ 1 : Som(T, k) = Som(T, k - 1) + T[k - 1]. Un seul appel récursif : récurrence d'ordre 1 ; la grandeur qui décroît est k, qui perd 1 à chaque appel et atteint 0 en k appels.

2. Écriture. TDOL : T tableau d'entiers, k entier avec 0 ≤ k ≤ n.

DEF FN Som(T : tab ; k : entier) : entier
Début
  Si k = 0 alors
    Retourner 0
  Sinon
    Retourner Som(T, k - 1) + T[k - 1]
  Fin Si
Fin Som

def som(T, k):
    if k == 0:
        return 0
    return som(T, k - 1) + T[k - 1]

print(som([4, -2, 7, 1], 4))   # 10

3. Trace de Som(T, 4). Descente : Som(T,4) attend Som(T,3) + 1 ; Som(T,3) attend Som(T,2) + 7 ; Som(T,2) attend Som(T,1) + (-2) ; Som(T,1) attend Som(T,0) + 4 ; Som(T,0) = 0. Remontée : Som(T,1) = 4, Som(T,2) = 2, Som(T,3) = 9, Som(T,4) = 10, ce que confirme 4 - 2 + 7 + 1 = 10.

4. Cas d'arrêt déplacé. Pour n = 4 la version du camarade donne le même 10 : elle s'arrête une marche plus haut, sur Som(T,1) = T[0] = 4, et la remontée est identique. Le défaut n'apparaît que sur le bord : avec n = 0, k vaut 0, le test k = 1 échoue, la fonction s'appelle avec k = -1, puis -2… Le test d'arrêt n'est jamais rencontré : les appels s'empilent jusqu'au débordement de pile, et T[k - 1] désigne au passage une case qui n'existe pas. Un cas d'arrêt doit être placé sur la valeur que la suite décroissante atteint réellement, pas sur la première valeur utile.

Idée : la chaîne ch est ici une donnée qu'on recopie, pas la grandeur qu'on réduit. Ce qui doit décroître, c'est le nombre de copies restant à écrire.

1. Relation. Cas d'arrêt : Rep(ch, 0) = "". Cas général, pour n ≥ 1 : Rep(ch, n) = ch + Rep(ch, n - 1). La grandeur qui décroît est n, de 1 en 1 ; ch ne change jamais. Ordre 1.

2. Écriture. TDOL : ch chaîne, n entier avec n ≥ 0.

DEF FN Rep(ch : chaîne ; n : entier) : chaîne
Début
  Si n = 0 alors
    Retourner ""
  Sinon
    Retourner ch + Rep(ch, n - 1)
  Fin Si
Fin Rep

def rep(ch, n):
    if n == 0:
        return ""
    return ch + rep(ch, n - 1)

print(rep("ab", 3))   # ababab
print(rep("ab", 0))   # (chaîne vide)

3. Cas d'arrêt à n = 1. Pour n = 3 la réponse est correcte : ch + (ch + ch) donne bien "ababab". Mais pour n = 0 le test n = 1 n'est pas vérifié, l'appel se poursuit avec n = -1, -2, … et ne rencontre jamais l'arrêt : débordement de pile. Le cas n = 0 est le bon parce qu'il est la valeur que la décroissance atteint depuis n'importe quel n ≥ 0, et parce que la chaîne vide est l'élément neutre de la concaténation, exactement comme 1 l'est de la multiplication dans la factorielle.

4. Comptage. Les appels sont Rep("ab",3), Rep("ab",2), Rep("ab",1), Rep("ab",0) : 4 appels, soit n + 1. La chaîne retournée contient 3 × 2 = 6 caractères.

Idée : un cas d'arrêt n'arrête rien tout seul. Il n'arrête la récursivité que si chaque appel rapproche l'argument de ce cas — c'est-à-dire s'il existe une grandeur entière positive qui diminue strictement d'un appel au suivant.

1. F s'arrête, G non. Dans F, le seul appel récursif se fait sur une chaîne de longueur long(ch) - 1 : la longueur est un entier positif qui perd 1 à chaque appel, elle atteint donc 0 en long(ch) appels, où le cas d'arrêt est rencontré. Dans G, la branche ch[0] = "a" réduit bien la longueur de 1, mais la branche Sinon relance G(ch) sur la même chaîne : rien n'a changé, le même test échoue de nouveau, et la fonction se rappelle indéfiniment. Le cas d'arrêt ch = "" est pourtant écrit et correct : il est simplement inatteignable dès que la chaîne commence par une lettre autre que a.

2. Exécutions. F("bac") = 1 + F("ac") = 1 + 1 + F("c") = 1 + 1 + 1 + F("") = 3 : F compte les caractères. G("bac") teste ch[0] = "b", entre dans la branche Sinon et rappelle G("bac") : boucle infinie, qui se termine en pratique par un débordement de pile. Sur la chaîne vide, les deux retournent 0 par leur cas d'arrêt.

3. Réparation. Une seule ligne change — la branche Sinon doit, elle aussi, raccourcir la chaîne, sans compter la lettre :

  Sinon Retourner G(sous(ch, 1, long(ch) - 1))

Sur "banana" : b non comptée → "anana" ; a comptée (1) → "nana" ; n non comptée → "ana" ; a comptée (2) → "na" ; n non comptée → "a" ; a comptée (3) → "" → 0. Le total retourné est 3, ce qui est bien le nombre de a de "banana", et les 7 appels successifs voient la longueur passer de 6 à 0.

4. Condition d'arrêt. Il ne suffit pas qu'un cas d'arrêt existe : il faut qu'une grandeur entière positive attachée à l'argument décroisse strictement à chaque appel, dans toutes les branches récursives, de sorte que le cas d'arrêt soit atteint après un nombre fini d'appels.