Introduktion till rekursion

Hierarkiska och rekursiva frågor i SQL Server

Jasmin Ludolf

Content Developer

Vad är rekursion?

Rekursion innebär att en procedur, subrutin, funktion eller algoritm anropar sig själv en eller flera gånger tills ett angivet villkor är uppfyllt

En bild som illustrerar rekursionens egenskap att anropa sig själv upprepade gånger.

Verkligt exempel på rekursion

Stamträd – Hitta alla fäder under de senaste 5 generationerna

Bryt ned problemet till ett mindre problem av samma typ
1. Hela problemet: Hitta alla fem generationer
2. Delproblem: Hitta fadern, hitta farfadern, ...
Begränsa antalet steg

Rekursionsegenskapen hos Tornet i Hanoi.

Fakta om rekursion

Fördelar:

Löser problem på ett rekursivt sätt
Lätt att läsa och följa
Rekursion kan begränsas av ett avslutningsvillkor

Nackdelar:

Långsammare körtid

Rekursionsexempel – Summa av tal

Matematisk definition

Summan av på varandra följande tal definieras rekursivt enligt följande:

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

Summan av talen upp till 5 är:

1+2+3+4+5 = 15

Rekursionsexempel – Summa av tal

Rekursion i SQL: Gemensamt tabelluttryck – 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

Nu kör vi en övning!

Hierarkiska och rekursiva frågor i SQL Server