Fibonacci
En muchas asignaturas de algoritmia utilizan la sucesión de Fibonacci como ejemplo de algoritmo recursivo.
La peor forma de darnos la sucesión de Fibonacci es así: 1,1,2,3,5,8…
Otra forma con la que queda totalmente definida es a través de su término general:
fib(n) = n si n < = 1 fib(n) = fib(n-1) + fib(n-2) si n > 1
A la vista de la segunda definición de la sucesión de Fibonacci es muy fácil darse cuenta del algoritmo recursivo múltiple que hay que hacer para resolver el problema de hallar el n-ésimo término de la sucesión.
func fib (n:entero) dev (res:entero)
alg
si (n< =1):
res := n
otras:
res := fib(n-1) + fib(n-2)
fsi
fin
Según la posición de la llamada a la misma función en un algoritmo recursivo podemos distinguir entre recursividad no final y final, a ésta última nos referimos cuando no hay que realizar más procesamiento después de la llamada recursiva.
Ahora veremos como conseguir un algoritmo recursivo final que nos devuelva el valor de la n-ésimo termino de la sucesión de Fibonacci mediante el uso de acumuladores.
func fibFinal (n:entero) dev (res:entero)
alg
res := 0
si (n < 2):
res := 1
otras:
res := fibFinalAux(n,1,0,1)
fsi
fin
func fibFinalAux (n,i,f0,f1:entero) dev (res:entero)
alg
res := 0
si (i = n):
res := f1
otras:
res := fibFinalAux(n,i+1,f1,f0+f1)
fsi
fin
Lo que hemos hecho ha sido utilizar 2 acumuladores, f0 que almacena en todo momento el valor de fib(n-2) y f1 que almacena el valor de fib(n-1).
Por último, debemos saber que cualquier algoritmo recursivo final puede transformarse en un algoritmo iterativo con un bucle. Si el algoritmo fuese no final tendríamos que usar 2 bucles.
Vamos a ver como pasamos de un algoritmo recursivo final (anterior) a uno iterativo.
func fibIter (n:entero) dev (res:entero)
var
i,f0,f1,faux: entero
alg
i := 1
f0 := 0
f1 := 1
faux := 0
res := 0
si (n < 2):
res := 1
otras:
mientras (i < n)
i := i+1
faux := f0
f0 := f1
f1 := faux + f1
fmientras
res := f1
fsi
fin
He hecho la traza de los algoritmos y todos cumplen con su labor. He estado buscando un poco en internet para ver si mi solución era la más eficiente y no he encontrado ninguna para los 2 últimos algoritmos asi que si veis alguna mejora debeis comentadmela
Si os han mandado estos pequeños ejercicios para una práctica pensadlos un poquito y no los copieis porque sino no sirve de nada y yo no me fiaría de un algoritmo de alguien que no conozco.
:wq








