RECURSION

In programming, recursion is the act of using a function to call itself. Outputs from a previous iteration are used as inputs to the next iteration. For example, consider the task of generating a sequence of integer values from one to ten, inclusive. Given the starting value of one, the next value can be defined as the current value plus one. To determine the third value in the sequence, the output of the previous iteration (i.e., 2) is used, resulting in 3 (i.e., 2 + 1). Here, the challenge doesn’t concern our ability to perform basic addition, but to understand how something so simple as adding one to an integer value can be expounded upon.

Structured query language (SQL) offers recursion through the use of common table expressions (CTE). If you’re unfamiliar with common table expressions, then I highly recommend reading my page containing a high-level overview on the topic, with supporting examples before continuing further.

Let’s return to the task of generating a sequence of integer values from one to ten, inclusive. Using SQL, we’ll make use of a recursive common table expression. Please note, with Oracle database a column alias list is required when using recursive CTEs. See line one in the example code below where the column alias listing is provided in parentheses. A recursive CTE contains two parts: an anchor query and a recursive query.

WITH integer_sequence (integer_value) AS (
    SELECT
    	1 AS integer_value 
    FROM
    	dual
    UNION ALL
    SELECT
    	integer_value + 1
    FROM
    	integer_sequence
    WHERE
    	integer_sequence.integer_value < 10
)
SELECT
	integer_sequence.integer_value
FROM
	integer_sequence;

In the anchor query, the starting value is generated. In this case, the value is one. Don’t let the reference to “dual” in the anchor query distract you. This is simply a dummy table offered by Oracle database that can expand and retract as needed at the time of executing a query. Here the dummy table is used to maintain a column named integer_value containing a single value, one. In the recursive query, the common table expression (i.e., integer_sequence) is referenced. During the first iteration, a second row of data containing our second integer value, two, is generated by referencing the current integer value, one, and adding one to it. At this point, integer_sequence contains two values, one and two. Each iteration after results in the subsequent integer value, defined as the integer value generated in the previous iteration plus one, being generated. A vital aspect of the recursive query is the stopping condition. Typically, this stopping condition is defined in the WHERE clause of the recursive query. In the absence of logic stating when to stop generating integer values, this process would continue forever. Luckily, Oracle database will throw an error reminding you to incorporate a stopping condition in your query if you happen to forget. For the current task, we’d like our query to terminate or stop generating integer values when integer_value for the current iteration is greater than or equal to 10. During the last iteration, integer_value will equal nine, resulting in the final value of ten being generated. Pay close attention to the comparison operator and operands used in your stopping conditions. It’s the easiest part to get wrong.

At first, it can be easy to dismiss the usefulness of recursion. I find this to be particularly true in the absence of presenting real-world problems where recursion is incorporated into the solution, so let’s explore a few problems extending beyond generating a sequence of integers.

Before reading further, consider reviewing the Example Data section below to familiarize yourself with the data being used throughout the examples on this page. If you are already familiar with the data, then skip to the Identifying Gaps in Dates section.

Example Data
The schemas, corresponding tables, and data used in the example problems can be found at livesql.oracle.com. To more easily follow the examples covered on this page, consider first reading the table descriptions below and reviewing each table’s contents. To review the data maintained in each table, click on the icon next to the table name. To hide the data, click the icon again.

Identifying Gaps in Dates
Imagine there exists a popular 24/7 online cupcake delivery service, allowing users to purchase cupcakes online and have them delivered to their door. The service is so popular an order has been placed every day since opening day. Stacy, the owner of the service, developed and configured the front-end aspect of the ordering system users interact with and also the back-end database table (i.e., oe.orders) for which orders are written to as they are placed. Unfortunately, something has gone wrong with the database causing several days’ worth of orders to disappear. Although the data is recoverable, in an effort to assess impact and identify root cause, she wishes to determine the dates for which orders disappeared. She completes a quick check to verify order data corresponding to the first day her service was available, and the current day is present in the database table but is unsure on how to quickly and programmatically identify the missing dates in between the two dates. Unfortunately, she is also without a calendar table that would allow her to quickly generate a list of all date values between the two dates. How can Stacy identify the missing order date values?

Stacy’s problem ultimately requires her to identify gaps in order dates. Given that an order has been placed every day since the launch of her online service and she’s verified the existence of order data for launch day and the current day, any date value missing from the database table between those two dates is of interest. To identify those missing dates, she first needs to develop a means to generate a list of those date values between launch day and the current day. She can use a recursive CTE to generate this list. Let’s explore this option, starting with the means to capture the date values associated with launch day and the current day given the data and this specific scenario.

In the query below and subsequent output, the date_range CTE returns the date values associated with launch day and the most recent day by computing the minimum and maximum order date value. These two values are vital to the task because they will serve as the lower and upper bound for the date range in the search for missing dates.

WITH date_range (start_date, end_date) AS (
    SELECT
		TRUNC(MIN(oe.orders.order_date)) AS start_date,
		TRUNC(MAX(oe.orders.order_date)) AS end_date
    FROM
		oe.orders
)
SELECT
	date_range.start_date,
	date_range.end_date
FROM
	date_range;

Now that identifying the lower and upper bound for our date range has been solved for, the query needs to be augmented to use these two values as the start and end dates for the list of date values. A recursive CTE can be used to perform this task. See the augmented code below with an explanation following.

WITH date_range (start_date, end_date) AS (
    SELECT
		TRUNC(MIN(oe.orders.order_date)) AS start_date,
		TRUNC(MAX(oe.orders.order_date)) AS end_date
    FROM
		oe.orders
),
applicable_date (date_value, end_date) AS (
    SELECT
		date_range.start_date AS date_value,
		date_range.end_date
    FROM
		date_range
    UNION ALL
    SELECT
		applicable_date.date_value + 1,
		applicable_date.end_date
    FROM
		applicable_date
    WHERE
		applicable_date.date_value < applicable_date.end_date
)
SELECT
	applicable_date.date_value,
    applicable_date.end_date
FROM
	applicable_date;

In the recursive CTE, applicable_date, the anchor query returns the start_date and end_date values referenced in and returned by date_range. Again, these values correspond to the launch date of the online service and the most recent day given the data. The recursive query generates a new row of data during each iteration. In each of these new rows, the date_value reflected is equal to the current date or most recent iteration’s date_value plus one day while the end_date value remains constant. For clarity, observe the output generated by applicable_date’s anchor query, first two iterations of the recursive query, and the final iteration of the recursive query following the code below. The generation of new rows ceases because the stopping condition is met. Remember, the goal of the recursive query is to generate a list of date values starting with the date associated with the launch day of Stacy’s online service and ending with the current day.

Anchor Query Output

Recursive Query Iteration 1

Recursive Query Iteration 2

Recursive Query Iteration 1596

With the successful generation of the list of date values, the final task is to compare this list of date values to the date values remaining in Stacy’s database table. Any date value generated by applicable_date not also in the Stacy’s database table qualifies as a missing date or gap. To make this comparison, Oracle’s set operator, MINUS, is used. This set operator returns only those rows returned by the first query not also returned by the second query. While there are other ways to achieve the same thing, I do not believe there is another such method that aligns so closely to the pseudocode and high-level explanation of the task at hand.

See the updated code and corresponding output below. Notice applicable_date’s second attribute, end_date, is not used in the final output because it’s already served its purpose and is not needed for the comparison. Given the output, Stacy’s issue is significant. 1526 days’ worth of orders are missing from her database table.

WITH date_range (start_date, end_date) AS (
    SELECT
		TRUNC(MIN(oe.orders.order_date)) AS start_date,
		TRUNC(MAX(oe.orders.order_date)) AS end_date
    FROM
		oe.orders
),
applicable_date (date_value, end_date) AS (
    SELECT
		date_range.start_date AS date_value,
		date_range.end_date
    FROM
		date_range
    UNION ALL
    SELECT
		applicable_date.date_value + 1,
		applicable_date.end_date
    FROM
		applicable_date
    WHERE
		applicable_date.date_value < applicable_date.end_date
)
SELECT
	applicable_date.date_value
FROM
	applicable_date
MINUS
SELECT
	TRUNC(oe.orders.order_date)
FROM
	oe.orders;