Une structure séquentielle comme une liste est une bonne application pour la récursivité.

Je vous propose de reprendre l'implémentation rencontré dans ce cours mais de modifier certaines fonctions au profit d'une approche récursive.

"""
liste.py
Module définissant l'interface des listes
"""

def CREER_LIST_VIDE():
    """
    renvoie une liste vide
    """
    return { "head": None }

def LONGUEUR(L):
    """
    renvoie le nombre d'éléments de la liste L
    """
    # à faire de façon récursive

def RECHERCHER(L, e):
    """
    renvoie l'indice de la première occurrence de e dans L.
    renvoie -1 si e n'est pas dans L
    """
    # à faire de façon récursive
    
def LIRE(L, i:int):
    """
    renvoie la valeur de l'élément d'indice i dans L
    précondition : 0 <= i < LONGUEUR(L)
    """
    # à faire de façon récursive
    
def INSERER(L, e, i:int):
    """
    insère l'élément e à l'indice i dans L
    précondition : 0 <= i <= LONGUEUR(L)
    ne renvoie rien, le contenu de L est modifié
    """
    assert i >= 0
    nouveau_maillon = { "data":e, "next":None }
    if i == 0:
        nouveau_maillon["next"] = L["head"]
        L["head"] = nouveau_maillon
        return
    maillon = L["head"]
    while maillon != None and i > 1:
        i -= 1
        maillon = maillon["next"]
    assert maillon != None, "indice trop grand"
    nouveau_maillon = m["next"]
    m["next"] = nouveau_maillon

def SUPPRIMER(L, i:int):
    """
    supprime l'élément de rang i dans L
    précondition : 0 <= i < LONGUEUR(L)
    ne renvoie rien, le contenu de L est modifié
    """
    assert i >= 0
    if i == 0:
        assert L["head"] != None, "La liste est vide"
        L["head"] = L["head"]["suivant"]
        return
    maillon = L["head"]
    while maillon != None and i > 1:
        i -= 1
        maillon = maillon["next"]
    assert maillon != None and maillon["next"] != None, "indice trop grand"
    maillon["next"] = maillon["next"]["next"]

def MODIFIER(L, e, i:int):
    """
    dans la liste L, écrit dans la case de rang i la valeur e
    précondition : 0 <= i < LONGUEUR(L)
    ne renvoie rien, le contenu de la liste est modifié
    """
    assert i >= 0
    maillon = L["head"]
    while maillon != None and i > 0:
        i -= 1
        maillon = maillon["next"]
    assert maillon != None, "indice trop grand"
    maillon["data"] = e
    
def TEXTE(L):
    """
    Renvoi une représentation texte du contenu de la liste
    On utilise la notation, par ex, 4:9:17:12
    """
    if L["head"] == None:
        return ":"
    strOut = str(L["head"]["data"])
    maillon = L["head"]["next"]
    while maillon != None:
        strOut = "{}:{}".format(strOut, maillon["data"])
        maillon = maillon["next"]
    return strOut
    
# zone de test
if __name__ == '__main__':    
    # création de L = 4:9:17:12
    L = CREER_LIST_VIDE()
    INSERER(L,0,4)
    INSERER(L,1,9)
    INSERER(L,2,17)
    INSERER(L,3,12)
    
    # tests
    assert LONGUEUR(L) == 4
    assert RECHERCHER(L, 9) == 1
    assert RECHERCHER(L, 25) == -1
    assert LIRE(L, 2) == 17
    assert TEXTE(L) == "4:9:17:12"
    
    MODIFIER(L, 48, 1)
    assert TEXTE(L) == "4:48:17:12"
    assert LIRE(L, 1) == 48
    assert RECHERCHER(L, 9) == -1
    
    SUPPRIMER(L,2)
    assert TEXTE(L) == "4:48:12"
    assert LONGUEUR(L) == 3
    
    # si on arrive là, c'est que tous les test ont été passés avec succès
    print("Succès !")