How does recursive common table expression work?

Question

The requirement is to write a table-valued function that takes 2 parameters.

@start_number  (a integer value)
@end_number (a integer value)

The function will return a table containing the numbers between @start_number and @end_number, including both the parameter numbers.

Here is the code:

Declare @start_number int
Declare @end_number int
Declare @max_recursion int

Set @start_number = 10
Set @end_number = 100
Set @max_recursion = (@end_number - @start_number)

Declare @numbers table(number int)   --start
;with numbers(number) as
(
 select @start_number as number
 union all
 select number + 1 from numbers where number between @start_number and @end_number - 1
)

insert into @numbers(number)
select number from numbers option(maxrecursion 10000)
select number from @numbers       --end

The query gives desired output.But,I need an explanation from start to end,how these lines are working?What is the purpose of max recursion here?

Answer 1

-- table variable declaration
Declare @numbers table(number int)   --start

-- CTE declaration
;with numbers(number) as
( -- CTE body
 -- anchor 
 select @start_number as number -- [a]
 union all

 -- recursive call to itself
 select number + 1 from numbers -- [r]

 -- recursion limit
 where number between @start_number and @end_number - 1
)

insert into @numbers(number)

-- insert into @numbers table all values from CTE
select number from numbers option(maxrecursion 10000)

-- pretty obvious select
select number from @numbers       --end

Table variable would be operated almost as usual table. About difference between temporary table and table variable refer this question or msdn.

CTE is like nested query, temporary result set. Primary difference is that it can be self-referenced (like in your case). You declare CTE with only one column number. Specifying columns manually is not required if they can be resolved. This is a recursive CTE - select a number and join itself appending +1 to number. So each subsequent row will have +1 to previous row. When you select from CTE anchor select @start_number as number is executed. Than it concatenated with everything, returned form itself (with +1 added).

Let's go step by step inside CTE:

on [a] return 1
on [r] add +1 to everything from self ([a] and [r]):
    on [a] return 1
    on [r] add +1 to everything from self ([a] and [r]):
        on [a] return 1
        on [r] add +1 to everything from self ([a] and [r]):
            on [a] return 1
            on [r] add +1 to everything from self ([a] and [r]):
                ...

So your result set is (each nest level is inside { and }):

{1, {1, {1, {1, ...} +1 } +1 } +1 }

where {1} +1 => {2}, {1, {1} +1 } +1 => {1, 2} +1 => {2, 3} and so on

So if you will not limit this query, nesting will be infinite. That is why recursion limit appear. Engine will simply filter your infinite query and stop nesting as on any subsequent selection it will get value that will not match you filter and that selection will return empty result set. For example, you filter values less then 10:

....
on [a] return 1 -- will result 8, match
on [r] add +1 to everything from self ([a] and [r]):
    on [a] return 1 -- will result in 9, match
    on [r] add +1 to everything from self ([a] and [r]): -- (STOP)
        on [a] return 1 -- will result in 10, not match
                        -- nothing else will be queried as on (STOP) empty result returned
                        -- so, recursion stopped

Note, that if you filter incorrectly in recursive call, e.g.

where number between @start_number + 1 and @end_number - 1

that very first recursive call will return to you @start_number, which is not match to you filter, and no recursion will occur.

Actually, filter

where number between @start_number and @end_number - 1

is excessive. It can be simplified to

where number < @end_number

Note, in both cases filter will not match @end_number as adds +1 to previous value. So as you start with @start_number (anchor) and concatenating with with recursion, that returns

  { @start_number, ..., @end_number -1 } +1

result will be

  { @start_number, @start_number +1, ..., @end_number -1 +1 }
--  ^^^^^^^^^^^^^ - anchor
--     recursion - ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Hint in select statement option(maxrecursion 10000) overrides default maximum recursion level (by default it is 100, valid values are [0..32767]). So your particular function is limited to 10000 values and if you will try to generate more then 10000 values, you will get this error:

The statement terminated. The maximum recursion 10000 has been exhausted before statement completion.

Note, filter that limits recursion must be placed inside your CTE, not where you use that CTE as in that case engine will continue to iterate through CTE looking for next matching value, but your CTE would be literally infinite and error will occur.

Rest of code is pretty simple - result form CTE inserted into @numbers table variable and then simply selected.

Variable @max_recursion can be removed as it not used (and cannot be used inside OPTION clause).