recursion

[Ralf]

Another question about recursion:

I have a recursive subroutine which may have large recursion-depths, I increased the stack to 10MB for this.

1) is it possible to use the heap instead of the stack, something akin to automatic arrays and option /heap_arrays?

2) for very large recursion depths I have to increase the stack to about 100MB - at some point I plan to parallelize the program - will such a large stack be problematic for multiple threads?

Cheers

-Ralf

[mecej4]

1. If you are exclusively using tail-recursion, you may eliminate recursion altogether and write a loop instead. If tail recursion is a part, it may still be of advantage to replace the tail-recursion by a loop.

2. If your recursive subroutine has local variables that are not distinct for each activation, making them static instead of automatic will help reduce stack consumption.

3. You may need to assess whether the simplicity and elegance of recursion needs to be sacrificed because of the inefficiency of executing millions of function calls, returns and stack clean-ups.

[Ralf]

Thanks mecej4!

I would hate to get rid of the recursion - that's why I (still) hang on to it ...

>2. If your recursive subroutine has local variables that are not distinct for each activation, making them static >instead of automatic will help reduce stack consumption.

What do you mean with 'static'? Declaring the SAVE attribute?

I got rid of the SAVE alltogether thinking that an "intent(inout)" will save memory, but I didn't see any effect ...

I think making the recursive subroutine an host-associated routine could get rid of some variables as they indeed are just copies of some variables in the caller (?).

Cheers

-Ralf

[Jugoslav_Dujic]

Quoting Ralf

I think making the recursive subroutine an host-associated routine could get rid of some variables as they indeed are just copies of some variables in the caller (?).Thanks mecej4!

Have in mind that this (recursive host-associated routines) is non-standard, at least according to F95 (not sure about F2003). It works in Intel Fortran as an extension, although they went through a lot of hoops (and bugs) to make this work. The difficulty in implementation on the compiler side is exactly in maintaining references to correct stack frames from the contained routine to its host.

[jimdempseyatthecove]

You have to weigh the costs of recursive programming (if any), usually expressed in run-time or memory consumption, against the costs of getting your code "dirty" by writing loops. In some situations recursive programming is more suitable but in other situations loop programming is more suitable. Time is money (or inconvenience when waiting for results). Below are two ways to produce the Fibonacci series

// Serial recursive method to calculate Fibonacci series

long SerialFib( long n )

{

if( n<2 )

return n;

else

return SerialFib(n-1)+SerialFib(n-2);

}

// Serial non-recursive method to calculate Fibonacci series

// *** Note, several orders of magnitude faster than all

// *** recursive techniques.

long SerialFib2( long n )

{

if( n<2 )

return n;

long fib0 = 1; // most recent

long fib1 = 1; // 1 prior to most recent

long fib2 = 0; // 2 prior to most recent

long i;

for(i=2; i

{

fib2 = fib1;

fib1 = fib0;

fib0 = fib1 + fib2;

}

return fib0;

}

For small numbers the recursive routine is more than suitable, for larger numbers, the loop method is far superior.

Although the above is in C++, it is easy enough to rewrite into FORTRAN.

When your recursive argument list contains a significant number of invariant variables/constants then think of using SAVE or an outer most layer context container and then pass the reference to the context as opposed to the list of invariant arguments. This saves stack space and the computation time to push the references (or values). A second area for concern with recursive programming is when the recursive function requires a substantial portion of working storage for the duration between the entry of the function/subroutine and the next recursion call. IOW the working storage for that section of code is no longer required at the point of recursion. In situations like this, the "temporary" working storage can be placed in the above mentioned context for re-use on by the next recursion level.

Jim Dempsey

[jimdempseyatthecove]

Excuse the above paste (double spaced lines)
This @!%$ editor pastes as C++ the code as one long frigg'n line.
The @!%$ editor pastes single line spaces Word text (the C++ code) as double spaced text

It would be interesting to add up the time spent by forum users screwing around with this against the time (to be) spent fixing this problem.

Jim Dempsey

[Steven_L_Intel1]

Jim, use the code pasting tool (yellow pencil).

[Ralf]

Hi Jugoslav,

are you sure that recursive internal subroutines are not allowed even in F90/95?

from the Intel Fortran doc ("Internal Procedures"):

In Fortran 95/90, the name of an internal procedure must not be passed as an argument to another procedure.

and

An internal procedure can reference itself (directly or indirectly); it can be referenced in the execution part of its host and in the execution part of any internal procedure contained in the same host (including itself).

so, you cannot have the routine in the argument list of the recursive internal procedure.

by the way, no compiler complaints when using/stand:f03.

Cheers

-Ralf

[Steven_L_Intel1]

Recursive internal routines are fine in F90. What is non-standard until F2008 is passing an internal routine as an actual argument. Intel/Compaq/DEC fortran has supported this for a long time.