Recursion is a concept used to solve a large problem by breaking it down into smaller, similar problems. It works by having a function call itself repeatedly until a specific condition is met.
Let’s look at an example: the factorial.
A factorial (written with !) means that a number is multiplied by the factorial of the number one less than it:
n!=n×(n−1)!
For example:
3! = 3 × 2!
= 3 × 2 × 1!
= 3 × 2 × 1 × 0!
You might notice this pattern could continue forever, which is why factorials stop calculating after it reaches 0! (0! is defined as 1 and factorials are not defined for negative numbers). This is the condition that stops the recursion, also know as a base case.
So when you calculate something like 3!, it keeps breaking down into smaller parts (3! = 3 × 2!, then 2! = 2 × 1!, and so on) until it reaches the base case of 0! At that point, it stops and multiplies everything back together to get the final answer.
The same idea applies to larger numbers like 10!:
10! = 10 × 9!
9! = 9 × 8!
…and this continues until it reaches the base case.
Although calculating something like 10! may seem like a huge task, a short recursive function can actually handle it quite easily.
So, let’s try to recreate the logic to solving 10! using recursion in SQL.
First, lets start by getting the logic to generate 10 rows.
Here, A Common Table Expression (CTE) named 'numbers' is defined to generate a sequence of values (rows 1 - 10). A CTE can be thought of as a temporary table that you can reference in context of a larger query. The CTE 'numbers' is a recursive CTE because it references itself in line 8, and in the end we view the entire CTE (line 12).
'numbers' begins with a base case that assigns the value 1 to the column n. This serves as the starting point for the recursion.
The recursive part of the CTE then selects n + 1 from the CTE itself, effectively incrementing the value of n by 1 on each iteration. This process continues repeatedly, with the CTE calling itself, until the condition n < 10 is no longer satisfied.
The UNION ALL operator combines the base case and each recursive result, adding a new row at every step. As a result, the query generates 10 rows in total.
You can see in the end that there's 10 rows, and the n value goes up to 10 as well.
Great, now let's modify the query to make it generate factorials!
Here, other than the renaming of the CTE to 'factorials', the only new logic that was added was on line 3, 4, and 9.
On line 3 and 4 the base case now initiates two values.
There is a new variable called factorial_result, which is the running total of the factorial values at each step.
n is set to 0, and factorial_result is set to 1, which initializes the base case of 0! = 1.
Then, on line 9, each iteration multiplies the current n (row number) with the running factorial values of the previous row.
You can see from the result that factorial_result is equal to n multiplied by the factorial_result of the previous row.
You can also see that there is 11 rows now, because the base case of n = 0, which is 0! = 1 is set up as the base case.
You can see that this concept of using recursion in SQL can be helpful for applying methods like scaffolding (which I also have a blog on). The idea behind the practice with factorials is that you can build on the values of the previous rows to generate new rows, which can be useful in situations such as running totals, cumulative calculations, or solving problems where each step depends on the result of the previous one.