Écrire dichotomie sous forme récursive

def dichotomie_recursive(t, v, gauche=0, droite=None):
    """Meme specification, ecrite recursivement.

    Le variant devient la taille de la tranche passee a l'appel suivant :
    chaque appel travaille sur une tranche STRICTEMENT plus petite.
    """
    if droite is None:
        droite = len(t) - 1
    if gauche > droite:
        return -1
    milieu = (gauche + droite) // 2
    if t[milieu] == v:
        return milieu
    elif t[milieu] < v:
        return dichotomie_recursive(t, v, milieu + 1, droite)
    else:
        return dichotomie_recursive(t, v, gauche, milieu - 1)

Le variant de boucle devient un variant d'appel. Il n'y a plus de boucle, donc plus de variant au sens du chapitre 7 ; ce qui garantit la terminaison est que chaque appel récursif reçoit une tranche strictement plus petite, et qu'une taille entière positive ne peut décroître indéfiniment. C'est le même argument, déplacé.

Le droite=None est le motif déjà rencontré pour la mémoïsation : on ne peut pas écrire droite=len(t)-1 comme valeur par défaut, puisque t n'existe pas encore au moment où Python évalue les défauts.

Vérification.

for _ in range(3000):
    t = sorted(random.randint(0, 30) for _ in range(random.randint(0, 15)))
    v = random.randint(-1, 31)
    r1, r2 = dichotomie(t, v), dichotomie_recursive(t, v)
    assert (r1 == -1) == (r2 == -1)
    if r1 != -1:
        assert t[r1] == t[r2] == v

assert dichotomie_recursive([], 3) == -1

Le test ne compare pas r1 == r2 : sur un tableau à doublons, les deux versions peuvent tomber sur des occurrences différentes. Ce qu'on vérifie, c'est la spécification — même verdict de présence, et un indice qui porte bien la valeur cherchée. Comparer les indices serait tester l'implémentation, pas le contrat.