La notion de récursion

1.1 Définition de la récursion et ses concepts de base.

La récursion, c’est quand quelque chose se répète encore et encore. Imagine que tu as une instruction, et qu’une partie de cette instruction dit de suivre l’instruction elle-même. C'est comme si tu donnais l'ordre de répéter l'ordre lui-même.

Exemples de la vie réelle :

Mirroirs en face l'un de l'autre :

Imagine que tu te tiens entre deux miroirs. Tu vois ton reflet, et dans le reflet, tu vois aussi ton reflet, et ainsi de suite. C'est un exemple de récursion, car chaque miroir montre le reflet de l'autre miroir.

Matriochkas :

Une matriochka est une poupée qui contient une autre poupée, et ainsi de suite. Quand tu arrives à la plus petite poupée, il n'y a plus rien à découvrir. C'est comme le cas de base dans la récursion – le moment où s'arrêter.

Partage de pizza :

Imagine que tu partages une pizza en deux. Ensuite, tu prends une moitié et la partages à nouveau, et tu continues jusqu'à ce que les morceaux soient trop petits pour être partagés. Le partage est un processus récursif, et le moment où tu ne peux plus diviser est le cas de base.

Important ! La récursion n'est pas une répétition interminable d'une commande. Il s'agit plutôt de diviser une tâche complexe en parties où l'approche pour résoudre les sous-tâches est similaire à celle de la tâche entière.

Comment ça fonctionne ?

Pour comprendre la récursion, il faut connaître deux concepts de base :

• Cas de base : c'est la condition qui arrête la récursion. Par exemple, dans l'exemple des matriochkas, le cas de base est lorsque tu ouvres la plus petite poupée et qu’il n'y a plus rien dedans.
• Cas récursif : c'est lorsque la tâche se répète avec des parties plus petites. Dans l'exemple de la pizza, tu divises le morceau, puis tu divises la moitié, et ainsi de suite.

Pourquoi est-ce utile ?

La récursion aide à résoudre des tâches complexes en les décomposant en parties plus simples. Au lieu de résoudre toute la tâche d'un coup, tu la résous petit à petit.

Autres exemples de la vie :

Conte dans un conte :

Imagine qu'un héros de conte raconte un autre conte, et que le héros de ce conte commence à raconter un autre conte. Quand l'un des contes se termine, tu reviens au conte précédent. Le cas de base est lorsque le dernier conte se termine.

Dessin récursif :

Tu dessines un grand triangle, puis dans chaque coin de ce triangle tu dessines un petit triangle, et tu continues jusqu'à ce que les triangles deviennent trop petits. Le cas de base est lorsque le triangle devient si petit qu'il ne peut plus être dessiné.

1.2 Cas de base : définition et exemples.

Cas de base : c'est la condition qui met fin aux appels récursifs et permet à la fonction de retourner une valeur spécifique. C'est généralement la solution la plus simple et la plus évidente à un problème, qui ne nécessite pas de récursion supplémentaire.

Exemples de cas de base :

Factorielle d'un nombre :

La factorielle d'un nombre n est notée comme F(n) == 1*2*3*…*n. De même, il est évident que F(n) == n* F(n-1).

Cas de base : la factorielle de 0 ou 1 est 1. F(0) == F(1)==1

def factorial(n):
    if n == 0 or n == 1:
        return 1  # Cas de base
    else:
        return n * factorial(n - 1)
        

Nombres de Fibonacci :

Les nombres de Fibonacci sont une séquence : 1, 1, 2, 3, 5, 8, 13, … Où chaque nombre suivant est la somme des deux précédents. Pour F(n) == F(n-1) + F(n-2)

Cas de base : les deux premiers nombres de Fibonacci sont 1, donc le «zéroième» nombre de Fibonacci est 0. Ou F(0) = 0 et F(1) = 1.

def fibonacci(n):
    if n == 0:
        return 0  # Cas de base
    elif n == 1:
        return 1  # Cas de base
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)
        

1.3 Cas récursif : définition et exemples

Cas récursif : c'est la partie d'une fonction qui résout le problème en s'appelant elle-même avec de nouveaux paramètres qui rapprochent la solution du cas de base. Chaque appel récursif réduit ou modifie le problème pour finalement atteindre le cas de base.

Exemples de cas récursif :

Factorielle d'un nombre :

Cas récursif : la factorielle d'un nombre n est n multiplié par la factorielle du nombre n-1.

def factorial(n):
    if n == 0 or n == 1:
        return 1  # Cas de base
    else:
        return n * factorial(n - 1)  # Cas récursif
        

Nombres de Fibonacci :

Cas récursif : F(n) est la somme de F(n-1) et F(n-2).

def fibonacci(n):
    if n == 0:
        return 0  # Cas de base
    elif n == 1:
        return 1  # Cas de base
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)  # Cas récursif
        

1.4 Exemples d'algorithmes récursifs

1. Parcours d'un arbre binaire :

Exemple de parcours en ordre "in-order".

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        
def inorder_traversal(node):
    if node:
        inorder_traversal(node.left)
        print(node.value)
        inorder_traversal(node.right)
        
# Exemple d'utilisation :
root = Node(1)
root.left = Node(2)
root.right = Node(3)
inorder_traversal(root)
        

2. Recherche de l'élément maximal dans une liste :

def find_max(lst):
    if len(lst) == 1:
        return lst[0]  # Cas de base
    else:
        max_of_rest = find_max(lst[1:])  # Cas récursif
        return max(lst[0], max_of_rest)
        
# Exemple d'utilisation :
print(find_max([1, 5, 3, 9, 2]))  # Sortie : 9
        
        

3. Recherche binaire récursive :

def binary_search(arr, target, left, right):
    if left > right:
        return -1  # Cas de base : élément non trouvé
    mid = (left + right) // 2
    if arr[mid] == target:
        return mid  # Cas de base : élément trouvé
    elif arr[mid] < target:
        return binary_search(arr, target, mid + 1, right)  # Cas récursif
    else:
        return binary_search(arr, target, left, mid - 1)  # Cas récursif
        
# Exemple d'utilisation :
arr = [1, 2, 3, 4, 5, 6, 7]
print(binary_search(arr, 5, 0, len(arr) - 1))  # Sortie : 4