And Recursion(…)

In my last post I discussed the topic of modularity of code in the context of generating prime numbers. In this post I am going to discuss the topic of recursion in SQL server in the context of modular code subsequently in the context of generating prime numbers.

In the prior post we showed how modularizing would allow us more opportunity to improve and correct past work without redoing everything from scratch. We created a function for testing primality called intIsPrime. We call it intIsPrime because if we really want a lot of primes (as many as we can get from SQL Server without inventing a new data type or doing some column and constraint tricks or both) we would need a bigintIsPrime function for all of those primes bigger than the integer data type which ends with the 2,147,483,647 which is prime. 2,147,483,647 is in fact the 3rd double Mersenne prime.

We then went on to query for the primes in the next 100 or so numbers using a technique called a recursive common table expression (CTE). In the spirit of modularity and reaching beyond a mere hundred tests through modular design consider this function:

CREATE FUNCTION dbo.hundredMorePrimeTests(@n int)
RETURNS TABLE
AS RETURN
(

WITH recurseMore AS (
SELECT @n AS p, 1 AS n 
UNION ALL 
SELECT p + 1 , n + 1 FROM recurseMore
	WHERE n < 101
					)
SELECT p, n FROM recurseMore
WHERE dbo.intIsPrime(p) = 1
)

By putting our recursive CTE into a function. We can pass it the parameter we want to test the next hundred integers for primality. This allows us to call it in a stored procedure that bases the call on the last prime in our prime table. We can also have that stored procedure call its self (another type of recursive technique) which enables us to run the stored procedure once and have it execute 32 times (an error occurs is a stored procedure nests more than 32 levels).

CREATE PROCEDURE thirtyTwoHundredPrimalityTests 
	@c INT = 1
AS
BEGIN
	SET NOCOUNT ON;
DECLARE @n INT; 
SELECT @n = MAX(p) FROM dbo.primes;
INSERT INTO dbo.primes 
	SELECT p FROM dbo.hundredMorePrimeTests(@n);
SET @n = @c + 1;
IF @n < 32 
EXEC thirtyTwoHundredPrimalityTests @n ;    
	
END

There you have it, modular and recursive. If we wanted to we could call thirtyTwoHundredPrimalityTests from another stored procedure that could serve to limit the run based on how long we want to run, or how many integers we want to test. We can pass @c as any integer and the result would be that many 100s of integers tested.

Advertisements

One thought on “And Recursion(…)

  1. Pingback: OPTION (MAXRECURSION 32767) | Thomas [W] Marshall

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s