PL/SQL User's Guide and Reference

Recursion

Recursion is a powerful technique for simplifying the design of algorithms. Basically, recursion means self-reference. In a recursive mathematical sequence, each term is derived by applying a formula to preceding terms. The Fibonacci sequence (1, 1, 2, 3, 5, 8, 13, 21, ...), which was first used to model the growth of a rabbit colony, is an example. Each term in the sequence (after the second) is the sum of the two terms that immediately precede it.

In a recursive definition, something is defined in terms of simpler versions of itself. Consider the definition of n factorial (n!), the product of all integers from 1 to n:

n! = n * (n - 1)!

Recursive Subprograms

A recursive subprogram is one that calls itself. Think of a recursive call as a call to some other subprogram that does the same task as your subprogram. Each recursive call creates a new instance of any objects declared in the subprogram, including parameters, variables, cursors, and exceptions. Likewise, new instances of SQL statements are created at each level in the recursive descent.

There must be at least two paths through a recursive subprogram: one that leads to the recursive call and one that does not. That is, at least one path must lead to a terminating condition. Otherwise, the recursion would (theoretically) go on forever. In practice, if a recursive subprogram strays into infinite regress, PL/SQL eventually runs out of memory and raises the predefined exception STORAGE_ERROR.

An Example

To solve some programming problems, you must repeat a sequence of statements until a condition is met. You can use iteration or recursion to solve such problems. Recursion is appropriate when the problem can be broken down into simpler versions of itself. For example, you can evaluate 3! as follows:

0! = 1
1! = 1 * 0! = 1 * 1 = 1
2! = 2 * 1! = 2 * 1 = 2
3! = 3 * 2! = 3 * 2 = 6

To implement this algorithm, you might write the following recursive function, which returns the factorial of a positive integer:

FUNCTION fac (n POSITIVE) RETURN INTEGER IS  -- returns n!
BEGIN
   IF n = 1 THEN  -- terminating condition
      RETURN 1;
   ELSE
      RETURN n * fac(n - 1);  -- recursive call
   END IF;
END fac;

At each recursive call, n is decremented. Eventually, n becomes 1 and the recursion stops.

Another Example

Consider the procedure below, which finds the staff of a given manager. The procedure declares two formal parameters, mgr_no and tier, which represent the manager's employee number and a tier in his or her departmental organization. Staff members reporting directly to the manager occupy the first tier. When called, the procedure accepts a value for mgr_no but uses the default value of tier. For example, you might call the procedure as follows:

find_staff(7839);

The procedure passes mgr_no to a cursor in a cursor FOR loop, which finds staff members at successively lower tiers in the organization. At each recursive call, a new instance of the FOR loop is created and another cursor is opened, but prior cursors stay positioned on the next row in their result sets. When a fetch fails to return a row, the cursor is closed automatically and the FOR loop is exited. Since the recursive call is inside the FOR loop, the recursion stops.

PROCEDURE find_staff (mgr_no NUMBER, tier NUMBER := 1) IS
   boss_name  CHAR(10);
   CURSOR c1 (boss_no NUMBER) IS
      SELECT empno, ename FROM emp WHERE mgr = boss_no;
BEGIN
   /* Get manager's name. */
   SELECT ename INTO boss_name FROM emp WHERE empno = mgr_no;
   IF tier = 1 THEN
      INSERT INTO staff  -- single-column output table
         VALUES (boss_name || ' manages the staff');
   END IF;

   /* Find staff members who report directly to manager. */
   FOR ee IN c1 (mgr_no) LOOP
      INSERT INTO staff
         VALUES (boss_name || ' manages ' || ee.ename
            || ' on tier ' || to_char(tier));
      /* Drop to next tier in organization. */
      find_staff(ee.empno, tier + 1);  -- recursive call
   END LOOP;
   COMMIT;
END;

Unlike the initial call, each recursive call passes a second actual parameter (the next tier) to the procedure.

The last example illustrates recursion, not the efficient use of set-oriented SQL statements. You might want to compare the performance of the recursive procedure to that of the following SQL statement, which does the same task:

INSERT INTO staff
   SELECT PRIOR ename || ' manages ' || ename
      || ' on tier ' || to_char(LEVEL - 1)
   FROM emp
   START WITH empno = 7839
   CONNECT BY PRIOR empno = mgr;

The SQL statement is appreciably faster. However, the procedure is more flexible. For example, a multi-table query cannot contain the CONNECT BY clause. So, unlike the procedure, the SQL statement cannot be modified to do joins. (A join combines rows from two or more database tables.) In addition, a procedure can process data in ways that a single SQL statement cannot.

Caution

Be careful where you place a recursive call. If you place it inside a cursor FOR loop or between OPEN and CLOSE statements, another cursor is opened at each call. As a result, your program might exceed the limit set by the Oracle initialization parameter OPEN_CURSORS.

Mutual Recursion

Subprograms are mutually recursive if they directly or indirectly call each other. In the example below, the Boolean functions odd and even, which determine whether a number is odd or even, call each other directly. The forward declaration of odd is necessary because even calls odd, which is not yet declared when the call is made. (See "Forward Declarations"

FUNCTION odd (n NATURAL) RETURN BOOLEAN;  -- forward declaration

FUNCTION even (n NATURAL) RETURN BOOLEAN IS
BEGIN
   IF n = 0 THEN
      RETURN TRUE;
   ELSE
      RETURN odd(n - 1);  -- mutually recursive call
   END IF;
END even;

FUNCTION odd (n NATURAL) RETURN BOOLEAN IS
BEGIN
   IF n = 0 THEN
      RETURN FALSE;
   ELSE
      RETURN even(n - 1);  -- mutually recursive call
   END IF;
END odd;

When a positive integer n is passed to odd or even, the functions call each other by turns. At each call, n is decremented. Ultimately, n becomes zero and the final call returns TRUE or FALSE. For instance, passing the number 4 to odd results in this sequence of calls:

odd(4)
even(3)
odd(2)
even(1)
odd(0)  -- returns FALSE

On the other hand, passing the number 4 to even results in the following sequence of calls:

even(4)
odd(3)
even(2)
odd(1)
even(0)  -- returns TRUE

Recursion versus Iteration

Unlike iteration, recursion is not essential to PL/SQL programming. Any problem that can be solved using recursion can be solved using iteration. Also, the iterative version of a subprogram is usually easier to design than the recursive version. However, the recursive version is usually simpler, smaller, and therefore easier to debug. Compare the following functions, which compute the nth Fibonacci number:

-- recursive version
FUNCTION fib (n POSITIVE) RETURN INTEGER IS
BEGIN
   IF (n = 1) OR (n = 2) THEN
      RETURN 1;
   ELSE
      RETURN fib(n - 1) + fib(n - 2);
   END IF;
END fib;

-- iterative version
FUNCTION fib (n POSITIVE) RETURN INTEGER IS
   pos1 INTEGER := 1;
   pos2 INTEGER := 0;
   cum  INTEGER;
BEGIN
   IF (n = 1) OR (n = 2) THEN
      RETURN 1;
   ELSE
      cum := pos1 + pos2;
      FOR i IN 3..n LOOP
         pos2 := pos1;
         pos1 := cum;
         cum := pos1 + pos2;
      END LOOP;
      RETURN cum;
   END IF;
END fib;

The recursive version of fib is more elegant than the iterative version. However, the iterative version is more efficient; it runs faster and uses less storage. That is because each recursive call requires additional time and memory. As the number of recursive calls gets larger, so does the difference in efficiency. Still, if you expect the number of recursive calls to be small, you might choose the recursive version for its readability.