Recursive function and pass by VALUE optimizations

[pat97269]

Hi all,

I have some questions about the recursive functions performance in the compiler.

The code is below, the performance table obtains with the compiler 14.  First column is normal, second column is pass by value.

Ifort is slower than gfortran(4.8.2), and is passing by reference creating more copies in the recursive case ?

I don't know if performance is better with old compiler version.

Thanks.

ifort         3.51  1.151

gfortran  2.027  0.452

program ackermann
         implicit none
   write(*,*) ack(3, 12)
   contains
 recursive function ack(m, n) result(a)
   integer, intent(in) :: m,n
   integer :: a

   if (m == 0) then
     a=n+1
   else if (n == 0) then
     a=ack(m-1,1)
   else
     a=ack(m-1, ack(m, n-1))
   end if
 end function ack
 end program ackermann

[mecej4]

jimdempseyatthecove wrote:

>>...however, I would also argue that the above code is iterative

I see your point of view. It occurred to me that, given a CPU with, say, 128 registers of which 120 are available for use as a stack, a larger number of Ackermann function evaluations may be possible without needing access to RAM. The distinction between recursive and iterative becomes more fuzzy in that situation.

The article http://en.wikipedia.org/wiki/Primitive_recursive_function makes a sharper statement, and in a computer context: "No control structures of greater generality, such as while loops or IF-THEN plus GOTO, are admitted in a primitive recursive language. Douglas Hofstadter's Bloop in Gödel, Escher, Bach is one such. Adding unbounded loops (WHILE, GOTO) makes the language partially recursive, or Turing-complete; Floop is such, as are almost all real-world computer languages."

[TimP]

Languages which depend on recursion as a primary method in place of iteration also depend on a compiler optimizing tail recursion, if they are to produce good performance.  Fortran isn't one of those; if it optimizes recursion at all, it may be a gift from a companion C compiler, and I wouldn't expect it to go as far as looking for auto-vectorization opportunities which aren't obvious inside a single function invocation.  But this gets quickly into computer science, where I'm not qualified and must refer to those wikipedia articles.

If you wanted limited support of recursion and also parallel support, you may need to look to the major general purpose programming languages rather than those which specialize in one or the other.  Interesting that Fortran RECURSIVE capability is probably used more in the context of parallelism than in plain recursion.