Repositorio de Antonio Sanchez

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