Introduction à la récursivité

Requêtes hiérarchiques et récursives dans SQL Server

Jasmin Ludolf

Content Developer

Qu'est‑ce que la récursivité ?

La récursivité consiste à utiliser une procédure, une sous‑routine, une fonction ou un algorithme qui s'appelle lui‑même une ou plusieurs fois jusqu'à ce qu'une condition soit atteinte

Une image illustrant la propriété de récursivité où l'on s'appelle plusieurs fois.

Exemple concret de récursivité

Arbre généalogique – Trouver tous les pères sur 5 générations

Réduire le problème à un plus petit du même type
1. Problème complet : trouver les cinq générations
2. Petit problème : trouver le père, puis le père du père, …
Limiter le nombre d'étapes

La propriété de récursivité de la tour de Hanoï.

À savoir sur la récursivité

Avantages :

Résoudre les problèmes de façon récursive
Facile à lire et à suivre
Peut être bornée par la condition d'arrêt

Inconvénient :

Exécution lente

Exemple de récursivité – Somme de nombres

Définition mathématique

La somme des nombres consécutifs se définit récursivement comme suit :

number = 1 
    for iteration = 1
number = number + (iteration - 1) 
    for iteration > 1

La somme des nombres jusqu'à 5 est :

1+2+3+4+5 = 15

Exemple de récursivité – Somme de nombres

Récursivité en SQL : Common Table Expression - CTE

WITH calculate_SumOfNumber AS
     ( -- Initial Query
    SELECT 1 AS iteration, 1 AS SumOfNumber

     UNION ALL
     -- Recursive Part 
     SELECT iteration + 1, SumOfNumber + (iteration + 1)
         FROM calculate_SumOfNumber

         WHERE iteration < 6
     )

SELECT SumOfNumber 
    FROM calculate_SumOfNumber

Passons à la pratique !

Requêtes hiérarchiques et récursives dans SQL Server