Recursive Subprograms

A recursive subprogram invokes itself. Recursion is a powerful technique for simplifying an algorithm.

A recursive subprogram must have at least two execution paths—one leading to the recursive invocation and one leading to a terminating condition. Without the latter, recursion continues until PL/SQL runs out of memory and raises the predefined exception STORAGE_ERROR.

In Example 9-37, the function implements the following recursive definition of n factorial (n!), the product of all integers from 1 to n:

n! = n * (n - 1)!

In Example 9-38, the function returns the nth Fibonacci number, which is the sum of the n-1st and n-2nd Fibonacci numbers. The first and second Fibonacci numbers are zero and one, respectively.

Note:

The function in Example 9-38 is a good candidate for result caching. For more information, see "Result-Cached Recursive Function".

Each recursive invocation of a subprogram creates an instance of each item that the subprogram declares and each SQL statement that it runs.

A recursive invocation inside a cursor FOR LOOP statement, or between an OPEN or OPEN FOR statement and a CLOSE statement, opens another cursor at each invocation, which might cause the number of open cursors to exceed the limit set by the database initialization parameter OPEN_CURSORS.

Example 9-37 Recursive Function Returns n Factorial (n!)

CREATE OR REPLACE FUNCTION factorial (
  n POSITIVE
) RETURN POSITIVE
  AUTHID DEFINER
IS
BEGIN
  IF n = 1 THEN                 -- terminating condition
    RETURN n;
  ELSE
    RETURN n * factorial(n-1);  -- recursive invocation
  END IF;
END;
/
BEGIN
  FOR i IN 1..5 LOOP
    DBMS_OUTPUT.PUT_LINE(i || '! = ' || factorial(i));
  END LOOP;
END;
/

Result:

1! = 1
2! = 2
3! = 6
4! = 24
5! = 120

Example 9-38 Recursive Function Returns nth Fibonacci Number

CREATE OR REPLACE FUNCTION fibonacci (
  n PLS_INTEGER
) RETURN PLS_INTEGER
  AUTHID DEFINER
IS
  fib_1 PLS_INTEGER := 0;
  fib_2 PLS_INTEGER := 1;
BEGIN
  IF n = 1 THEN                              -- terminating condition
    RETURN fib_1;
  ELSIF n = 2 THEN
    RETURN fib_2;                           -- terminating condition
  ELSE
    RETURN fibonacci(n-2) + fibonacci(n-1);  -- recursive invocations
  END IF;
END;
/
BEGIN
  FOR i IN 1..10 LOOP
    DBMS_OUTPUT.PUT(fibonacci(i));
    IF i < 10 THEN
      DBMS_OUTPUT.PUT(', ');
    END IF;
  END LOOP;
 
  DBMS_OUTPUT.PUT_LINE(' ...');
END;
/

Result:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...