Introducción
Cuando empecé los
artículos previos sobre
Recursividad Terminal, pensé en demostrarlos en
Fortran 77
por ser el lenguaje por excelencia que no soporta recursividad. Sin
embargo, encontré algunos problemas y opté por otros lenguajes. En este
artículo he retomado ese reto.
¿Conseguí finalmente ejecutar una subrutina recursiva en Fortran 77?
Objetivo: implementar la función Factorial recursivamente en Fortran 77
Un ejemplo típico de función recursiva cuyo valor depende de invocarse a sí misma es la función matemática
Factorial:
| Factorial(N) | si N es 0 entonces 1 | //Caso base. |
| en otro caso, N * Factorial(N-1) | //Llamada recursiva. |
Utilicé dicha función como ejemplo por ser
muy sencilla de implementar, muy ilustrativa y también porque yo no soy
ningún experto en
Fortran 77.
Problema 1: Fortran 77 no soporta recursividad
Al intentar crear un pequeño programa en
Fortran 77
con una función (usaré el termino subrutina en general) recursiva me
topé con el primer problema: no está permitida la recursividad ni
directa (invocarse a sí mismo) ni indirecta (una subrutina no puede
invocar a otra que ya esté en la pila de ejecución, es decir, que una
misma subrutina sólo puede estar una única vez en memoria).
El
compilador (supongo que el lenguaje en sí) que utilicé resuelve la
imposibilidad de que una subrutina se invoque a sí misma o a otra que
indirectamente pueda invocarla a ella permitiendo invocar únicamente
subrutinas ya definidas (no se permiten declaraciones por adelantado
como en otros lenguajes).
Así, al estar definiendo una subrutina, su cuerpo no puede
tener invocaciones a sí misma porque aún no está completamente definida
y obtendremos un error de subrutina (símbolo) desconocida. De igual
modo, cada subrutina sólo puede invocar subrutinas que hayan sido
previamente definidas, por lo que ninguna de ellas podrá contener
invocaciones a ella.
Solución al problema 1
Siguiendo las indicaciones dadas por Andrew J. Miller en su página
Example 1: Recursive Routines in FORTRAN 77 (and Fortran 90), utilicé las directivas
EXTERNAL y
CALL para conseguir que una subrutina se invoque a sí misma. Sólo sirve para
subroutine, no sirve para
function.
De
este modo, la subrutina recursiva recibirá como argumento el nombre de
una subrutina a la que invocar, que en este caso, será ella misma.
Problema 2: en Fortran 77 se pasan los argumentos por referencia
En
Fortran 77
los argumentos siempre se pasan por referencia, por lo que hay que
tener cuidado de no alterar el valor de aquellos argumentos que
semánticamente sean de entrada, sobre todo si hicieran falta después de
la invocación recursiva.
Solución al problema 2
En el caso de la función
Factorial(N)
es necesario realizar llamadas recursivas con el valor (N-1). Hay que
tener en cuenta que si se altera el argumento con una asignación
N= N-1
se está alterando el valor de la variable original, porque se pasa por
referencia. Por lo tanto, hay que tener cuidado con el sitio donde se
almacena el resultado de ese cálculo, ya que su ubicación será
traspasada a la invocación recurisva.
Problema 3: subrutinas sin almacenar variables en la pila
En
Fortran 77
el valor una una variable local se considera indefinido una vez que se
sale de su ámbito. Sin embargo, es opcional, mediante la directiva
SAVE,
que se salvaguarde el valor de las variables locales de una subrutina
entre una invocación y otra. En otras palabras, se solicita al
compilador que almacene la variable local de la subrutina de forma
estática.
Suena
bastante chocante, pero después de todo, no es una idea tan disparatada
dado que el lenguaje no permite que una misma subrutina esté dos veces
en memoria, y por tanto, es irrelevante que sus variables locales
estuviesen almacenadas estáticamente, ahorrando el coste computacional
que conlleva mantener la pila de ejecución. Más discutible es que se
programase usando esa característica como truco para reaprovechar el
valor entre invocaciones.
Al parecer, ese comportamiento se hizo tan común que algunos compiladores antiguos (especialmente conocido el de
DEC) se saltaban el estándar y siempre almacenaban las variables locales de forma estática sin que se pusiese explícitamente
SAVE, y muchos programadores se acostumbraron a programar así.
El compilador que utilicé, el
g77, tiene una opción para compilar en ese modo:
-fno-automatic.
Al utilizar la directiva SAVE, la variable local V de la subrutina S ocupa siempre la misma posición de memoria M. En caso de que S
se invocase recursivamente, se estaría sobreescribiendo constantemente
la misma posición de memoria M, por lo que es muy probable que al
acceder a V después de una invocación recursiva su
valor difiera del valor que tenía antes de la invocación.
Solución al problema 3
Yo he forzado que aparezca este problema utilizando la directiva SAVE, demostrando que se puede eludir mediante una implementación basada en Recursividad Terminal,
puesto que tras la invocación ya se tiene el resultado y no hay que
realizar ninguna operación más (siendo por tanto irrelevante el valor de
las variables locales en ese punto).
Demostración
Es
muy importante tener en cuenta utilizar un compilador estricto para
Fortran 77, ya que a partir de
Fortran 90 ya no existen tantas restricciones (soporta
recursión). Para las pruebas he utilizado:
Hoy día me costó encontrar compiladores de
Fortran 77, así que realicé las pruebas sólo con ese compilador.
A continuación se puede ver el programa en
Fortran 77 que escribí para este artículo, con una implementación recursiva de la función matemática
Factorial. Se compone de la función
factorial(num) que es un simple envoltorio (wrapper) para la subrutina recursiva
factorial_inner(self, input, output), donde:
- self es el nombre de la subrutina a invocar con CALL (ella misma en este caso).
- input es el número cuyo Factorial se desea calcular (argumento de entrada).
- output es la variable acumulador del resultado (argumento de entrada/salida).
Hay que prestar especial atención a las líneas 3, 10, 11 y 12.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| subroutine factorial_inner(self, input, output)
integer :: input, output, tmp
save tmp
external self
if (input .GT. 0) then
c Con cualquier otro orden de estas 3 sentencias el programa
c fallará si se usa la directiva SAVE sobre la variable tmp.
output= input * output
tmp= input - 1
call self(self, tmp, output)
endif
return
end
integer function factorial(num)
integer :: num, output
external factorial_inner
output= 1
call factorial_inner(factorial_inner, num, output)
factorial= output
return
end
program demo_factorial
integer :: input, output
integer :: factorial
write (*,*) 'Input number:'
read (*,*) input
output= factorial(input)
write (*,*) 'Factorial= ', output
stop
end
|
He puesto la variable tmp
para evitar que el compilador cree variables temporales debidas a
cálculos intermedios (expresiones) y para demostrar el funcionamiento de
la directiva SAVE.
Si se elimina la directiva SAVE
de la línea 3, el programa funcionará perfectamente aunque se reordenen
las sentencias 10, 11 y 12 (con sentido claro), porque la variable tmp estará almacenada en la pila. Sin embargo, con dicha directiva activada, sólo fucionará correctamente en ese orden.
Obsérvese que, con la directiva SAVE activada, desde factorial_inner sólo se accede a la verdadera variable input (el argumento input de factorial_inner apunta al argumento num de factorial que a su vez apunta a la variable input del programa principal) en la primera invocación, de ahí en adelante se está trabajando con una referencia a la variable tmp (a la que se le ha asignado una posición fija en memoria), y por tanto, en el resto de invocaciones el argumento input y la variable local tmp apuntan a la misma posición de memoria. Si se intercambian las instrucciones 10 y 11, output estará mal calculado puesto que en la primera iteración input
ya habrá sido decrementado. De hecho, ese intercambio de instrucciones
provoca que el resultado siempre sea 0 porque al llegar a la invocación
correspondiente al Factorial de 1 se realizaría la multiplicación output*input = output*0 = 0.
Conclusión
En respuesta a la pregunta que planteé al comienzo del artículo,
sí ha sido posible implementar una subrutina recursiva en Fortran 77,
con ciertas restricciones impuestas por el propio lenguaje, aunque lo
más interesante ha sido aprender sobre lo útil que es la pila de
ejecución y cómo la
Recursividad Terminal puede ser de ayuda en ciertas condiciones.
Enlaces
Enlaces de interés relacionados con este artículo:
(Actualizado 03/03/2016)
