program recursion

!===================================================================================
! El "Tiempo de ejecucion" de un algoritmo es la cantidad de pasos basicos que     |
! que se ejecutan, en funcion del tamano de la entrada N. Hablamos de el           |
! "orden del tiempo de ejecucion" a la clasificacion que le damos al tiempo de     |
! ejecucion para N muy grande (en la terminologia de limites), decimos que es O(N) |
!   - Las sentencias basicas son de O(1)                                           |
!   - Un bucle de N iteraciones es O(n)                                            |
!   - Un orden de tipo O(n^k) es "Polinomial"                                      |
!   - Un orden de tipo O(k^f(n)) es "Exponencial"                                  |
!===================================================================================


integer(kind=8) :: n
integer(kind=8) :: fact
integer(kind=8) :: fibo

!/////////////////////////////////////////////////////////////////////////////////////////////
!    observar como varia el tiempo de ejecucion de fibonacci iterativo/recursivo al llamar   / 
!    al procedimiento con varios n's. Esto muestra que se debe tener cuidado al implementar  / 
!    una funcion recursiva ya que el tiempo de ejecucion puede ser de mayor orden que su     / 
!    version iterativa de tenerla. Se muestra fibonacci con n de 0 a 60 de a 5, iterativo    /
!    primero y recursivo luego. La version recursiva se debe detener mucho antes de 60 por   /
!    su demora.                                                                              /
!/////////////////////////////////////////////////////////////////////////////////////////////


print *, "---- TIEMPO DE EJECUCION -----"
print *,
print *, "  Fibonacci iterativo  "

do i = 2,50,5
  print*, "-----------------------------------"
  print*, "i=",i
  print *,"fibonacci=  ",fibonacci_it(i)
  print *,
end do

print *,
print *, "  Fibonacci recursivo   "

do i = 2,50,5
  call fibonacci_rec(i,fibo) 
  print*, "-----------------------------------"
  print*, "i=",i
  print *,"fibonacci=  ",fibo
  print *,
end do

!-----------------------------------------------------------------
CONTAINS

integer(kind=8) function fibonacci_it(n)

integer(kind=4),intent(in) :: n
integer(kind=8) :: fib1 , fib2
integer :: i

if ( n == 0) then
   fibonacci_it = 0
else
   if ( n ==1 ) then
      fibonacci_it = 1
   else 
      fib1 = 1
      fib2 = 0
      do i =2,n
         fibonacci_it = fib1 + fib2
         fib2 = fib1
         fib1 = fibonacci_it
      end do
   end if
end if

end function fibonacci_it

!-----------------------------------------------------------------

recursive subroutine fibonacci_rec(n,fib)

integer(kind=4) ,intent(in) :: n
integer(kind=8) :: fib,fib1,fib2

if ( n==0 ) then
   fib = 0
else 
  if( n==1 ) then
     fib = 1
  else
     call fibonacci_rec(n-1,fib1)
     call fibonacci_rec(n-2,fib2)
     fib = fib1+fib2
  endif
endif 

end subroutine fibonacci_rec

!-------------------------------------------------------------------
end program recursion