Kbase P27594: The disadvantages of recursive functions.
| Autor |
Progress Software Corporation - Progress |
| Acesso |
Público |
| Publicação |
15/06/2009 |
|
Status: Verified
GOAL:
The disadvantages of recursive functions.
GOAL:
Why not to use recursive function/procedure calls ?
GOAL:
Why recursion should be avoided if possible.
FACT(s) (Environment):
All Supported Operating Systems
Progress 9.x
OpenEdge 10.x
OpenEdge Category: Language (4GL/ABL)
FIX:
Recursive function/procedure calls occur when a function or procedure calls itself. Care must be taken when using such functions, as there are certain risks involved.
The thing to keep in mind is that each iteration consumes space on the call stack and will consume memory for variables and such until it completes, which will not happen until the final iteration has completed and the recursion starts to unwind.
If left unchecked, this is very likely to lead to stack or memory segment overflows which will crash an application.
For example, the following program will cause a stack overflow due to the recursion (assuming the stack is the default size of 40K):
DEFINE VARIABLE q AS CHARACTER NO-UNDO.
FUNCTION recur RETURNS CHARACTER
(INPUT a AS CHARACTER):
a = a + "A".
IF LENGTH(a) = 30000 THEN RETURN a.
ELSE RETURN recur(a).
END.
MESSAGE recur(q).
If such a function accesses a database, there will also be record pointers and such that will not be released until the final iteration, so the recursion may cause issues on the database side as well, manifesting as unexpected disconnections of clients or possibly worse.
For these reasons it's usually better to avoid straight recursion if possible.
One technique which can be used instead is using a loop in which calls the function as often as required instead, and which stores the values being processed in variables. This way there will never be more than one iteration of the function call active at a time, and no matter how many iterations are needed, the amount of stack space and other resources used will be just the amount required for that one iteration plus what's needed for the loop.
The next program has the same functionality as the example listed above, but avoids the recursion. It will run without causing a stack overflow:
DEFINE VARIABLE q AS CHARACTER NO-UNDO.
FUNCTION recuronce RETURNS CHARACTER
(INPUT a AS CHARACTER):
RETURN a + "A".
END.
FUNCTION recur RETURNS CHARACTER
(INPUT b AS CHARACTER):
DO WHILE LENGTH(b) < 30000:
b = recuronce(b).
END.
RETURN b.
END.
MESSAGE recur(q).If for whatever reason using recursion cannot be avoided, and the maximum number of iterations is unknown, it is advised to manually limit the maximum number of iterations by adding a "depth count" to the function. For example, the following recursive function accepts a parameter for the maximum number of iterations:
DEFINE VARIABLE q AS CHARACTER NO-UNDO.
FUNCTION recur RETURNS CHARACTER
( INPUT a AS CHARACTER,
INPUT b AS INTEGER,
INPUT c AS INTEGER
) :
IF c = 0 THEN RETURN ERROR. /* max. number of iterations passed */
a = a + "A".
IF LENGTH(a) = b THEN RETURN a.
ELSE RETURN recur(a,b,c - 1).
END.
MESSAGE recur(q, 10, 20). /* Maximum is 20 iterations, will perform 10. */
MESSAGE recur(q, 25, 20). /* Maximum is 20 iterations, attempt 25 and fail */