| Recursion in SQR | KEVIN RESCHENBERG
07-12-2004 |
Programming classes teach recursion, but how often do we actually use it? Last week I had
an assignment that was solved easily with recursion—and I was a little surprised to find that
SQR handled it with no problems.
"Recursion" simply refers to a programming technique in which a procedure calls itself.
That may sound like an infinite loop—and it can be—but we just need to
include some sort of IF logic so that the procedure calls itself only under certain conditions.
That avoids the loop.
The assignment was to create a process to build a table. This table is a cross-reference which
contains each employee's ID and the ID of his or her first supervisor who is at least a vice
president. In other words, we start with each employee and then move up through the
hierarchy until a VP is found. If the original employee is already a VP, we take that
person's supervisor. Therefore, we might move up one level or several.
Couldn't we just put a BEGIN-SELECT into some sort of loop? Possibly, but then what would the
main SELECT be? The problem seemed to be a natural for recursion.
The solution includes a main SELECT and a LOCAL procedure. The main
SELECT simply goes through the JOB table, finding each active employee. The JOB row contains
both an employee's EMPLID and the person's SUPERVISOR_ID. The main loop retrieves these fields
for each employee and calls a procedure, passing a $variable containing the SUPERVISOR_ID
to the procedure as a parameter within parentheses (which automatically makes the procedure LOCAL). This
procedure returns the ID of the employee's VP. The loop then writes this information to a
table and goes on to the next employee.
How does the called procedure find the VP? This is where the recursion comes in. The procedure
receives the parameter, which is also an employee ID. It looks up that person's current JOB
row and, based on JOBCODE.MANAGER_LEVEL, determines whether the person is a VP. If so, the
procedure returns that ID back to the caller. If not, it takes the person's SUPERVISOR_ID
(up one level in the hierarchy), calls itself, and then returns whatever it receives
back to the caller.
Suppose that Ann reports to Bob and Bob reports to VP Carol. The main SELECT finds employee = Ann,
supervisor = Bob. It calls the procedure, passing Bob's ID. The procedure receives this ID and
finds Bob's JOB row. It determines that Bob is not a VP, so it calls itself with Bob's supervisor's
(Carol's) ID. The procedure receives this ID and finds Carol's JOB row. Carol is a VP,
so it returns Carol's ID and exits. The first invocation of the procedure then continues and
returns Carol's ID back to its caller—the main SELECT loop. The main loop originally called
the procedure with Bob's ID but now it receives Carol's ID back. That is written to the table.
There is a danger here. What if there is some bad data in our database, and we have Ann reporting
to Bob and Bob reporting to Ann? I solved that with a little kludge by keeping a counter. Each
time the procedure calls itself, it increments the counter. If that ever reaches 20 (an arbitrary
number that is much higher than the number of levels in the organization), the program reports
a circular reference, writes blanks as the VP's ID, and goes on to the next employee.
The whole project took probably an hour, but it was an interesting little problem.
|
