Intel® Fortran Compiler
Build applications that can scale for the future with optimized code designed for Intel® Xeon® and compatible processors.

recursive subroutines and stack size

Roman1
New Contributor I
946 Views

I am experimenting with recursive subroutines.  If I compile and run a simple program, where a recursive subroutine calls itself many times, it crashes with a stack overflow.  I have figured out that to fix this, I have to set the Stack Reserve Size to a large value.  Is there a way to disable the stack usage?  I have tried using /heap-arrays0 option, but it did not help.

If I can't disable the stack and I want to use recursive subroutines, do you think I should just set the Stack Reserve Size to a maximum of 1 GB to prevent any stack overflows?

 

0 Kudos
6 Replies
Nick2
New Contributor I
946 Views

At least in my field, there's still a good number of people running 32-bit Windows; using up 1 GB of RAM might make them nervous ...

If you are calling the subroutine recursively that many times, maybe it would work better with some kind of a DO loop?  Every time you step into a recursive subroutine, you are allocating (whatever stack size the subroutine needs) on the stack again.

I have only used recursive subroutines/functions when there's a chain of 16 subroutines calling each other, and every once in a while you end up with subroutine #16 calling back into subroutine #1.

0 Kudos
NotThatItMatters
Beginner
946 Views

I HAVE used many instances of recursive subroutines on 32-bit Windows without running out of stack.  The method I use is to make tthe routine PRIVATE within a MODULE and make certain the routine has very few arguments.  Typically I am using one or two scalar arguments to the routine where the arrays necessary to employ in the recursion are MODULE-level PRIVATE arrays.  Hence when the CALL is made to the routine, only two "words" of stack are eaten and the PRIVATE array maintains the data between calls.

Also, I try to leave the number of local variables within the RECURSIVE routine small.  This is just a few pointers in making recursion work in stack-limited applications.

0 Kudos
GVautier
New Contributor II
946 Views
Hello Recursivity may look elegant but it hides the memory and CPU resources it consumes. The stack usage for each level of recursivity is equal to the sum of all local variables and arguments of the procedure and stack requirement for the call (and it's more than 2 words). Each call also consumes CPU time to jump. For deep recursive problems, I think it's more efficient to use classical programming with loops and allocated memory.
0 Kudos
mecej4
Honored Contributor III
946 Views

Two points to consider in managing stack consumption by recursive procedures: 

1. Tail recursion may be replaced by loops. As the article https://en.wikipedia.org/wiki/Tail_call explains, tail recursion implemented this way can be thought of as "jumps with parameters".

2. Convert local variables (those that do not have to be local, i.e., variables that do not change with recursion depth) to static variables or global variables, thereby reducing the stack burden incurred with each recursion.

-----------

Recursion: See Recursion

    -- from an early Macintosh Pascal manual

 

0 Kudos
Roman1
New Contributor I
946 Views

Thanks for the helpful comments.  My original question was if it was possible to NOT use the stack with recursive subroutines.  But it looks like it is not possible, and I have to be more careful with recursion.

 

0 Kudos
jimdempseyatthecove
Honored Contributor III
946 Views

Many, but not necessarily all, recursive routines can be written iteratively. Barring that...

Some recursive routines require some scratch variables that are used only prior to, or following, the recursion, and do not carry information across the recursion. When this situation exists, then each recursion level that is not active is unnecessarily consuming stack space. In this situation you might be able to take advantage of the following technique:

Add to the routine to be recursively called, an additional optional argument that is a user defined type containing the "scratch" variables. You also add an allocatable object of this type.

On initial call this argument is missing. Upon call with missing argument, you allocate the scratch type, then immediately recurse with the original arguments plus the reference to the allocatable scratch space.

On subsequent calls with present scratch object reference, you use the content of that for temporary use.

*** Note ***

While you can accomplish the same thing using SAVE without the user defined type optional argument, the use of SAVE will also make it impractical for the routine to be called in a multi-threaded application. Whereas the optional argument will work in a multi-threaded situation.

Jim Dempsey

0 Kudos
Reply