Houston, we have a problem

Well, okay, the situation here is not as serious as it was for Apollo 13 when the main oxygen tank exploded while the spacecraft was en route to the moon. Your problem is that the spiral-drawing program keeps calling itself and drawing longer and longer lines. It will continue to do that until the computer executing it runs out of resources and (if you’re lucky) puts an obnoxious error message on the screen. If you’re unlucky, the computer just crashes.

Failure is not an option

The scenario described in the previous section shows one of the dangers of using recursion. A program written to call itself invokes a new instance of itself — which in turn calls yet another instance, ad infinitum. This is generally not what you want. (Think of a certain cartoon mouse in a wizard’s hat trying to stop all those marching broomsticks… .)

To address this problem, programmers include a termination condition within the recursive function — a limit on how deep the recursion can go — so the program performs the desired action and then terminates gracefully. You can include a termination condition in your spiral-drawing program to save computer resources and prevent dizziness in programmers:

void spiral2(int segment)

{

if (segment <= 10)

{

line(segment)

left_turn(90)

spiral2(segment + 1)

}

} ;

When you call spiral2(1), it executes and then (recursively) calls itself until the value of segment exceeds 10. At the point where segment equals 11, the if (segment <=10) construct returns a False value, and the code within the interior braces is skipped. Control returns to the previous invocation of spiral2 and, from there, returns all the way up to the first invocation, after which the program terminates. Figure 13-2 shows the sequence of calls and returns that occur.

Every time a function calls itself, it takes you one level farther away from the main program that was the starting point of the operation. For the main program to continue, the deepest iteration must return control to the iteration that called it. That iteration will have to do likewise, returning all the way back to the main program that made the first call to the recursive function.

 Recursion is a powerful tool for repeatedly executing code when you don’t know at the outset how many times the code should be repeated. It’s ideal for searching through tree-shaped structures such as family trees, complex electronic circuits, or multilevel distribution networks.

Querying the hard way

To find out what you want to know — provided you have the time and patience — you can make a series of queries, first using Portland as the starting city:

SELECT Destination FROM FLIGHT WHERE Source = 'Portland';

The first query returns Orange County, Charlotte, and Daytona Beach. Your second query uses the first of these results as a starting point:

SELECT Destination FROM FLIGHT WHERE Source = 'Orange County';

The second query returns Montgomery. Your third query returns to the results of the first query and uses the second result as a starting point:

SELECT Destination FROM FLIGHT WHERE Source = 'Charlotte';

The third query returns Memphis. Your fourth query goes back to the results of the first query and uses the remaining result as a starting point:

SELECT Destination FROM FLIGHT WHERE Source = 'Daytona Beach';

Sorry, the fourth query returns a null result because Vannevar offers no outgoing flights from Daytona Beach. But the second query returned another city (Montgomery) as a possible starting point, so your fifth query uses that result:

SELECT Destination FROM FLIGHT WHERE Source = 'Montgomery';

This query returns Memphis, but you already know it’s among the cities you can get to (in this case, via Charlotte). But you go ahead and try this latest result as a starting point for another query:

SELECT Destination FROM FLIGHT WHERE Source = 'Memphis';

The query returns Champaign — which you can add to the list of reachable cities (even if you have to get there in two hops). As long as you’re considering multiple hops, you plug in Champaign as a starting point:

SELECT Destination FROM FLIGHT WHERE Source = 'Champaign';

Oops. This query returns a null value; Vannevar offers no outgoing flights from Champaign. (Seven queries so far. Are you fidgeting yet?)

Vannevar doesn’t offer a flight out of Daytona Beach, either, so if you go there, you’re stuck — which might not be a hardship if it’s Spring Break week. (Of course, if you use up a week running individual queries to find out where to go next, you might get a worse headache than you’d get from a week of partying.) Or you might get stuck in Champaign — in which case, you could enroll in the University of Illinois and take a few database courses.

Granted, this method will (eventually) answer the question, “What cities are reachable from Portland?” But running one query after another, making each one dependent on the results of a previous query, is complicated, time-consuming, and fidgety.

Saving time with a recursive query

A simpler way to get the info you need is to craft a single recursive query that does the entire job in one operation. Here’s the syntax for such a query:

WITH RECURSIVE

REACHABLEFROM (Source, Destination)

AS (SELECT Source, Destination

FROM FLIGHT

UNION

SELECT in.Source, out.Destination

FROM REACHABLEFROM in, FLIGHT out

WHERE in.Destination = out.Source

)

SELECT * FROM REACHABLEFROM

WHERE Source = 'Portland';

The first time through the recursion, FLIGHT has seven rows and REACHABLEFROM has none. The UNION takes the seven rows from FLIGHT and copies them into REACHABLEFROM. At this point, REACHABLEFROM has the data shown in Table 13-2.

 As I mention earlier, recursion is not a part of core SQL, and thus some implementations may not include it.

The second time through the recursion, things start to get interesting. The WHERE clause (WHERE in.Destination = out.Source) means that you’re looking only at rows where the Destination field of the REACHABLEFROM table equals the Source field of the FLIGHT table. For those rows, you’re taking two fields — the Source field from REACHABLEFROM and the Destination field from FLIGHT — and adding them to REACHABLEFROM as a new row. Table 13-3 shows the result of this iteration of the recursion.

The results are looking more useful. REACHABLEFROM now contains all the Destination cities that are reachable from any Source city in two hops or less. Next, the recursion processes three-hop trips, and so on, until all possible destination cities have been reached.

After the recursion is complete, the third and final SELECT statement (which is outside the recursion) extracts from REACHABLEFROM only those cities you can reach from Portland by flying Vannevar. In this example, all six other cities are reachable from Portland — in few enough hops that you won’t feel like you’re traveling by pogo stick.

 If you scrutinize the code in the recursive query, it doesn’t look any simpler than the seven individual queries it replaces. It does, however, have two advantages:

• When you set it in motion, it completes the entire operation without any further intervention.
• It can do the job fast.

Imagine a real-world airline with many more cities on its route map. The more possible destinations that are available, the greater the advantage of using the recursive method.

What makes this query recursive? The fact that you’re defining REACHABLEFROM in terms of itself. The recursive part of the definition is the second SELECT statement, the one just after the UNION. REACHABLEFROM is a temporary table that fills with data progressively as the recursion proceeds. Processing continues until all possible destinations have been added to REACHABLEFROM. Any duplicates are eliminated, because the UNION operator doesn’t add duplicates to the result table. After the recursion has finished running, REACHABLEFROM contains all the cities that are reachable from any starting city. The third and final SELECT statement returns only those destination cities that you can reach from Portland. Bon voyage.