Appels récursifs croisés

regardons cet exemple :

🐍 Script Python

def f(n):
    if n == 0:
        return 0
    else:
        return 3 * g(n // 3)

def g(n):
    if n == 0:
        return 0
    else:
        return 2 + f(n * 2)

f et g sont des fonctions récursives mutuelles, en effet la définition de l'une contient un appel à l'autre, donc (indirectement) à elle-même.

Ici, il est possible de prouver la terminaison, mais ce genre d'exercices ne fait pas partie du programme de NSI.

En revanche, on peut demander d'appliquer à la main un algorithme avec deux fonctions mutuellement récursives.