In theory,
recursive functions
prove useful in generating a list of numbers based on a formula in which the
final result is based on the result of the previous step. In other words, a
problem is solved by calculating the previous iteration of the same problem.
In practice, they are limited by the number of iterations allowed, and there
is a hard limit in SQL Server, the available resources (usually memory), and
probably a few other factors. Of course, some algorithms can be implemented to
overcome the limitations, while other times there are quite simple linear
implementations based on a loop, like in the below examples. Therefore,
recursive functions are more of a theoretical concept.
Disclaimer: The below code was generated by Copilot via prompts and is used
for demonstration purposes!
This post evaluates whether Microsoft 365 and Edge Copilot can be used to
generate the code for some recursive functions.
Case 1: Factorials
Let's start with the factorial that calculates the product of the n
consecutive numbers.
Prompt:
Generate a recursive function in SQL Server to calculate the factorial
of a number.
Output (M365 Copilot):
-- factorial function in Microsoft 365 Copilot
CREATE FUNCTION dbo.Factorial (@n INT)
RETURNS BIGINT
AS
BEGIN
IF @n <= 1
RETURN 1
ELSE
RETURN @n * dbo.Factorial(@n - 1)
END
Output (Edge Copilot):
-- factorial function in Edge Copilot
CREATE FUNCTION dbo.Factorial (@n INT)
RETURNS BIGINT
AS
BEGIN
IF @n = 0 OR @n = 1
RETURN 1
ELSE
RETURN @n * dbo.Factorial(@n - 1)
END;
The structure seems correct, and the returning value was identified correctly
as bigint, which allows the maximum value in working with integer values.
Unfortunately, both functions lead to the same error in a SQL database:
"Msg 455, Level 16, State 2, Line 9, The last statement included within a
function must be a return statement."
The formulas ca be consolidated in a single statement as follows:
-- factorial function adapted (minimal)
CREATE FUNCTION dbo.Factorial (@n INT)
RETURNS BIGINT
AS
BEGIN
RETURN
CASE
WHEN @n = 0 OR @n = 1 THEN 1
ELSE
@n * dbo.Factorial(@n - 1) END
END;
Especially when formulas become complex, it might be a good idea to store the
result into a variable and use it in the RETURN statement.
-- factorial function adapted
CREATE FUNCTION dbo.Factorial (@n INT)
RETURNS BIGINT
AS
BEGIN
DECLARE @retval as bigint;
IF @n = 0 OR @n = 1
SET @retval = 1
ELSE
SET @retval = @n * dbo.Factorial(@n - 1)
RETURN @retval
END;
And, here are some tests for the function:
-- testing the functions for multiple values
SELECT dbo.Factorial (0) -- returns 1
SELECT dbo.Factorial (1) -- returns 1
SELECT dbo.Factorial (2) -- returns 2
SELECT dbo.Factorial (3) -- returns 6
SELECT dbo.Factorial (4) -- returns 24
SELECT dbo.Factorial (5) -- returns 120
SELECT dbo.Factorial (20) -- returns 2432902008176640000
SELECT dbo.Factorial (21) -- returns an error for all bigger values
As can be seen, the function will return an error for values bigger than 20,
output limited by the data type used. One can build further constraints to
test for the maximum value.
Use the following code to drop the function as needed:
-- dropping the function
DROP FUNCTION IF EXISTS dbo.Factorial
Function's implementation has however another important caveat. If negative
numbers are provided as parameters, the following error message is thrown:
"Msg 217, Level 16, State 1, Line 1, Maximum stored procedure, function,
trigger, or view nesting level exceeded (limit 32)."
The final function can be defined as:
-- factorial function adapted (final)
CREATE FUNCTION dbo.Factorial (@n INT)
RETURNS BIGINT
AS
BEGIN
DECLARE @retval as bigint;
IF @n BETWEEN 0 AND 20
IF @n = 0 OR @n = 1
SET @retval = 1
ELSE
SET @retval = @n * dbo.Factorial(@n - 1)
RETURN @retval
END;
One can linearize the function as a loop, though the limitation with the
maximum value still exists:
Prompt:
Rewrite the factorial function using a loop.
Output (M365 Copilot):
-- non-recursive function to calculate the factorial of a number using a loop:
CREATE FUNCTION dbo.Factorial (@n INT)
RETURNS BIGINT
AS
BEGIN
DECLARE @result BIGINT = 1;
DECLARE @i INT = 1;
WHILE @i <= @n
BEGIN
SET @result = @result * @i;
SET @i = @i + 1;
END
RETURN @result;
END
-- test the code
SELECT dbo.Factorial(5) AS FactorialResult; -- result 120
One can obtain some improvement by changing the return type and @retsult from
bigint to float, though the results are always approximations. Here are the
approximated results:
-- test code
SELECT dbo.Factorial(20) AS FactorialResult; -- result 2432902008176640000
SELECT dbo.Factorial(21) AS FactorialResult; -- result 5.109094217170944E+19
SELECT dbo.Factorial(22) AS FactorialResult; -- result 1.1240007277776077E+21
SELECT dbo.Factorial(23) AS FactorialResult; -- result 2.585201673888498E+22
SELECT dbo.Factorial(24) AS FactorialResult; -- result 6.204484017332394E+23
SELECT dbo.Factorial(25) AS FactorialResult; -- result 1.5511210043330986E+25
SELECT dbo.Factorial(26) AS FactorialResult; -- result 4.0329146112660565E+26
SELECT dbo.Factorial(27) AS FactorialResult; -- result 1.0888869450418352E+28
SELECT dbo.Factorial(28) AS FactorialResult; -- result 3.0488834461171384E+29
SELECT dbo.Factorial(29) AS FactorialResult; -- result 8.841761993739701E+30
SELECT dbo.Factorial(30) AS FactorialResult; -- result 2.6525285981219103E+32
SELECT dbo.Factorial(31) AS FactorialResult; -- result 8.222838654177922E+33
SELECT dbo.Factorial(32) AS FactorialResult; -- result 2.631308369336935E+35
SELECT dbo.Factorial(170) AS FactorialResult; -- result 7.257415615307994E+306
SELECT dbo.Factorial(171) AS FactorialResult; -- results in arithmetic overflow
Another structure that allows creating recursive functions are the common
table expressions (CTEs).
Prompt:
Create a recursive CTE in SQL Server for calculating n factorial.
Output (M365 Copilot):
-- n factorial as CTE
WITH FactorialCTE AS (
-- Anchor member: factorial of 0 is 1
SELECT 0 AS n, 1 AS factorial
UNION ALL
-- Recursive member: factorial of n is n * factorial of (n-1)
SELECT n + 1, (n + 1) * factorial
FROM FactorialCTE
WHERE n < 10 -- Change this value to calculate factorial for larger numbers
)
SELECT n, factorial
FROM FactorialCTE;
One can cast the value in the anchor member as bigint or float as above with
all the constraints resulting from this:
-- n factorial as CTE
WITH FactorialCTE AS (
-- Anchor member: factorial of 0 is 1
SELECT 0 AS n, Cast(1 as bigint) AS factorial
UNION ALL
-- Recursive member: factorial of n is n * factorial of (n-1)
SELECT n + 1, (n + 1) * factorial
FROM FactorialCTE
WHERE n < 20 -- Change this value to calculate factorial for larger numbers
)
SELECT n, factorial
FROM FactorialCTE;
Case 2: Approximation of π
Power laws can be used to
approximate the value of π and other irrational constants. Writing such a function via recursive
functions has the same constraint as above, though there are alternatives
(including storing the actual value as a constant).
Prompt:
Generate a recursive function in SQL Server to approximate the value of
π using power laws.
Output (M365 Copilot):
-- approximate the value of π using this series:
CREATE FUNCTION dbo.ApproximatePi (@n INT)
RETURNS FLOAT
AS
BEGIN
IF @n = 0
RETURN 4.0
ELSE
RETURN 4.0 * POWER(-1, @n) / (2 * @n + 1) + dbo.ApproximatePi(@n - 1)
END
-- test the function
SELECT dbo.ApproximatePi(1000) AS PiApproximation;
Function's definition has the same issue as the previous example. It's
needed to rewrite the function as a single return:
-- approximate the value of π using this series (rewritten)
CREATE FUNCTION dbo.ApproximatePi (@n INT)
RETURNS FLOAT
AS
BEGIN
RETURN
CASE
WHEN @n = 0 THEN 4.0
ELSE
4.0 * POWER(-1, @n) / (2 * @n + 1) + dbo.ApproximatePi(@n - 1)
END
END
-- testing the function
SELECT dbo.ApproximatePi (0) -- output: 4
SELECT dbo.ApproximatePi (1) -- output: 2.666666666667
SELECT dbo.ApproximatePi (2) -- output: 3.466666666667
SELECT dbo.ApproximatePi (3) -- output: 2.8952380952389998
SELECT dbo.ApproximatePi (10) -- output: 3.232315809407
SELECT dbo.ApproximatePi (20) -- output: 3.189184782279
SELECT dbo.ApproximatePi (30) -- output: 3.1738423371919993
SELECT dbo.ApproximatePi (31) -- output: 3.110350273699999
SELECT dbo.ApproximatePi (32) -- output: 3.171888735237999
SELECT dbo.ApproximatePi (33) -- throws error
After 32 iterations the call throws the same error as above. Fortunately, such
functions can be (re)written using non-recursive implementations, which is the
proper way to implementation such functions:
Prompt:
Implement the function without using recursive functions.
Output (M365 Copilot):
-- approximation within loop
CREATE FUNCTION dbo.ApproximatePi (@terms INT)
RETURNS FLOAT
AS
BEGIN
DECLARE @pi FLOAT = 0.0;
DECLARE @i INT = 0;
WHILE @i < @terms
BEGIN
SET @pi = @pi + 4.0 * POWER(-1, @i) / (2 * @i + 1);
SET @i = @i + 1;
END
RETURN @pi;
END
This implementation is more flexible and a similar approach can be used for
similar series. And, here are the results for various parameters:
-- testing the function
SELECT dbo.ApproximatePi(1000) AS PiApproximation; -- result: 3.140592653840002
SELECT dbo.ApproximatePi(10000) AS PiApproximation; -- result: 3.141492653571029
SELECT dbo.ApproximatePi(100000) AS PiApproximation; -- result: 3.141582653466945
SELECT dbo.ApproximatePi(1000000) AS PiApproximation; -- result: 3.1415916535590713
The last call is close, but probably not close enough, especially when one
needs to use the function in multiple places. There are more complex power
series which provide better performance faster. The direct use of the pi()
function is usually recommended:
-- using the pi function
SELECT pi(); -- 3.141592653589793
Moreover, some series can be reduced to formulas based on constants
like π, e or Φ.
And, a final piece of code:
-- drop the function
DROP FUNCTION IF EXISTS dbo.ApproximatePi
One can use a CTE also in this case:
Prompt:
Generate a recursive function in SQL Server to approximate the value of
π using power laws.
Output (M365 Copilot):
-- series via recursive CTE
WITH PiApproximationCTE AS (
-- Anchor member: start with k = 0
SELECT 0 AS k, CAST(4.0 AS FLOAT) AS term, CAST(4.0 AS FLOAT) AS pi_approx
UNION ALL
-- Recursive member: calculate the next term and add it to the approximation
SELECT
k + 1,
CAST(4.0 * POWER(-1, k + 1) / (2 * (k + 1) + 1) AS FLOAT),
pi_approx + CAST(4.0 * POWER(-1, k + 1) / (2 * (k + 1) + 1) AS FLOAT)
FROM PiApproximationCTE
WHERE k < 1000 -- Change this value to increase the number of terms
)
SELECT k, pi_approx
FROM PiApproximationCTE
OPTION (MAXRECURSION 0); -- Allow for more recursion levels if needed
This time Copilot generated a different faction for calculating the same. (The
output is too long to be added in here as one record is generated for
each iteration.)
Happy coding!
Previous Post
<<||>>
Next Post
