Introduction to recursion

Hierarchical and Recursive Queries in SQL Server

Jasmin Ludolf

Content Developer

What is recursion?

Recursion is the use of a procedure, subroutine, function, or algorithm that calls itself one or more times until a specified condition is met

An image of the recursion property to call itself many times.

Real-world example for recursion

Family Tree - Find all fathers for the last 5 generations

Reduce the problem to a smaller problem of the same type
1. Whole problem: Find all five generations
2. Small problem: Find the father, find the father of the father, ...
Limit the number of steps

The recursion property of the Tower of Hanoi.

Facts about recursion

Advantage:

Solve problems in a recursive way
Easy to read and follow
Recursion could be limited by the termination condition

Disadvantage:

Slow execution time

Recursion example - Sum of numbers

Mathematical definition

The sum of consecutive numbers is defined recursively as follows:

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

The sum of numbers to 5 is:

1+2+3+4+5 = 15

Recursion example - Sum of numbers

Recursion with 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

Let's practice!

Hierarchical and Recursive Queries in SQL Server