0

I am relatively new to Fortran (using 90), and haven't been able to find any literature answering this question, so I thought I would ask here on SO: I am trying to write a recursive function that will return an array.

My end goal was to write my own FFT in Fortran without going through the C fftw and using the "C to Fortran" package; I understand there are ways of doing this without using a recursive function, but I would still like to know if a recursive function is able to return an array.

As an exercise, I tried to write a program that takes in a natural number, recursively computes the Fibonacci sequence and returns a list of the Fibonacci numbers indexed up to the argument integer. Using the same algorithm, I wrote this function in Matlab and it works, but there is a semantic error when writing in Fortran 90:

recursive function Fibbo(l)
    integer, INTENT(IN) :: l
    integer, dimension(l)  :: x

    integer, dimension(l) :: Fibbo

    if ( l == 1 ) then
        x = 1
    else if ( l == 2 ) then
        x(1) = 1
        x(2) = 1
    else
        x(1:l-1) = Fibbo(l-1)
        x(n) = x(l-1) + x(l-2)
    end if

Fibbo = x  
end function

It will compile just fine, and no problems except for the output: (when trying to call ell = 3)

Enter an integer:
3
 -1610612736
  1342177280
           0

There is a different output each time, and with an out like that I am guessing there is an issue with memory allocation, or something like that, but like I said I cannot find any literature online addressing recursive functions returning arrays. Perhaps it cannot be done?

P.S. It will output the correct list--i.e., 1, [1 1]--when calling Fibbo(1), Fibbo(2), rest.

EDIT: P.P.S. If it matters, I am compiling with gfortran, in Yosemite

EDIT: Thank you for pointing out the mistake, however trying to recast the output didn't fix it: 

recursive function Fibbo(l) result(x)
    integer, INTENT(IN) :: l
    integer, dimension(l)  :: x

    if ( l == 1 ) then
        x = 1
    else if ( l == 2 ) then
        x(1) = 1
        x(2) = 1
    else
        x(1:l-1) = Fibbo(l-1)
        x(n) = x(l-1) + x(l-2)
    end if

end function

This still gives errors for ell > 2.

charlestoncrabb
  • 103
  • 1
  • 8
  • 1
    Inside the function `Fibbo(l-1)` isn't a reference to the function, but the (undefined) result array. See, perhaps, http://stackoverflow.com/q/31061507 – francescalus Aug 01 '15 at 00:31
  • 1
    Does the function have an explicit interface in the scope from which it is called? If not, it needs one. – IanH Aug 01 '15 at 04:54
  • 2
    Fortran rule 1: ALWAYS use `implicit none` in every scoping unit. That way you avoid, *inter alia*, inadvertent dynamic declaration of unwanted variables, such as `n` in the statement `x(n) = x(l-1) + x(l-2)`. Voting to close, this is a typo-generated error. – High Performance Mark Aug 01 '15 at 07:24
  • 1
    The n is indeed the problem, place the function in a module which begins with `implicit none `. I also suggest to rething your FFT plan, if you need the transforms for serious work and not just for fun. There are Fortran libraries available and it will be very difficult to reach their quality and performance. – Vladimir F Героям слава Aug 01 '15 at 07:35
  • @HighPerformanceMark "every" scoping unit? That's a bit excessive... – IanH Aug 01 '15 at 08:08
  • 1
    @IanH: yes, should have referred to your own answer at http://stackoverflow.com/questions/24337413/where-to-put-implicit-none-in-fortran on that point. On the other hand, overuse of `implicit none` is a lesser sin than underuse. – High Performance Mark Aug 01 '15 at 08:30

1 Answers1

3

The problem is this line:

x(n) = x(l-1) + x(l-2)

Where you assign to element n of array x. The problem is that n is an uninitialized implicit variable of type integer (because you did not declare any variable called n). You have not assigned a value to n, and are accessing it making this a non-conforming program.

As noted in the comments, using 'implicit none' is considered best practices and will result in a compiler error when you inadvertently use a variable you have not declared. e.g. gfortran 5.2 will complain:

        x(n) = x(l-1) + x(l-2)
          1
Error: Symbol ‘n’ at (1) has no IMPLICIT type

If you fix n to l and make sure you function has an explicit interface (e.g. by putting it in a module) your code works.

For demonstration purposes, here is what I did to your code:

module fib
  implicit none
contains
  recursive function Fibbo(l) result(x)
    implicit none
    integer, INTENT(IN) :: l
    integer, dimension(l)  :: x
    if ( l == 1 ) then
       x = 1
    else if ( l == 2 ) then
       x(1) = 1
       x(2) = 1
    else
       x(1:l-1) = Fibbo(l-1)
       x(l) = x(l-1) + x(l-2)
    end if
  end function Fibbo
end module fib

program test
  use fib
  implicit none
  print *, Fibbo(10)
end program test

which will output

1       1       2       3       5       8      13      21      34      55
casey
  • 6,855
  • 1
  • 24
  • 37