Recursión: Concepto y Aplicaciones Prácticas con Ejemplos

Podemos usar memoizacion para optimizarlo, antes de hacer la llamada a la función podemos revisar en una especie de cache si el valor ya lo hemos consultado previamente, en caso que no llamamos a la función.

Para mejorarlo aplicaría Programación Dinámica con la técnica de Memorización, para evitar repetir cálculos ya realizados, transformar la complejidad de un algoritmo de exponencial a lineal o polinomial, dependiendo del problema e intercambiar tiempo por espacio.
Y así poder obtener el resultado de fibonacci de números grandes en menor tiempo:

import sys

def fibonacci_dinamico(n, memo = {}):
    if n == 0 or n == 1:
        return 1

    try:
        return memo[n]
    except KeyError:
        resultado = fibonacci_dinamico(n - 1, memo) + fibonacci_dinamico(n - 2, memo)
        memo[n] = resultado

        return resultado

print(fibonacci_dinamico(250))        

https://platzi.com/clases/1835-programacion-estocastica/26429-introduccion-a-la-programacion-dinamica/

Se me ocurre crear un “cache”, de numeros ya calculados.

cache = {}
def fib(n):
    if n <= 1:
        return n
    if cache.get(n) != None:
        return cache[n]
    result = fib(n-1) + fib(n-2)
    cache[n] = result
    return result

Asi queda lo mas resumido posible, detectando también que el numero sea mayor a cero

def fibo(n):
    return (print('Error') if n<0 else( n if n<2 else fibo(n-1) + fibo (n-2)))

Tomando los datos solo para numeros positivos, e intentando reducir el código al máximo en python:

def fibo(n):
    return (n if n<2 else fibo(n-1) + fibo (n-2))

Para evitar cálculos pre-hechos, en ese código en particular se me ocurre mandar un arreglo con los valores fibonacci recién calculados y validar si ya está calculado algo como:

def fib(n, fib_values):
     if n == 0:
         return 0
     if n == 1:
         return 1
     if fib_values[n] >= 0:
         return fib_values[n]
     fib_values[n] = fib(n-1, fib_values) + fib(n-2, fib_values)
     return fib_values[n]

n = 100
fib_values = [-1] * (n+1)

print(fib(n, fib_values))

Esto mejora mucho el tiempo en valores mayores como 40 pasando de 51seg a 0.04seg:

oscar@pavilion:~/Dev/algo$ time python3 fibonacci.py
102334155

real	0m51.446s
user	0m51.286s
sys	0m0.032s
oscar@pavilion:~/Dev/algo$ time python3 fibonacci_optimizado.py 
102334155

real	0m0.040s
user	0m0.028s
sys	0m0.012s

O un poco más elegante para mi gusto, resolverlo con programación dinámica:

def fib(n):
    fib = [-1] * (n+1)
    fib[0] = 0
    fib[1] = 1

    for i in range(2, n+1):
        fib[i] = fib[i-1] + fib[i-2]

    return fib[n]

Recursividad: Proceso que se define en términos de sí mismo. Lo importante al definir una función de recursividad es saber cuando va a terminar de ejecutar la función (el caso base), caso contrario podríamos caer en un ciclo infinito.
En tiempo de ejecución en memoria funciona como un Pila (LIFO), en el cuál cada frame tiene sus variables independientes de cada llamada de la función. Ej.: con factorial.

Sucesión de Fibonacci: Sucesión infinita de números naturales, la cual empieza a partir del 0 y el 1, continuando con la suma de los 2 anteriores: 0, 1, 1 (1+0), 2(1+1), 3(2+1), 5(3+2)+, 8(5+3), 13(8+5) … Descubierta por el matemático italiano Leonardo de Pisa, más conocido como Fibonacci en el siglo trece.

Al código le añadiría un mensaje de retorno en caso que se pida el Fibonacci de un número negativo o retornaría el mismo número:

function fib(n) {
	if (n <= 1) 
		return n;
	return (fib(n-1) + fib(n-2));
}

def fibo(n):
if n == 1 or n==2:
return n
else:
num = fibo(n-1) + fibo(n-2)
return num
print(fibo(7))

<public class sucesionDeFibonacci{

    public static void main(String[] args) {
        Scanner leer = new Scanner(System.in);
        System.out.println("Numero de fibonacci a conocer: ");
        int numUsuario = leer.nextInt()-1;
        int [] fibonacci  = new int [numUsuario+1];
        int i = 0;
        sucesion(numUsuario, fibonacci, i);
    }
    
    public static void sucesion(int fibonacci, int [] num, int i){
        if (i <= 1) {
            num[i] = 1;
            System.out.println("Fibonacci " + (i + 1) + ": " + num[i]);
        } else {
            num[i] = num[i - 1] + num[i - 2];
            System.out.println("Fibonacci " + (i + 1) + ": " + num[i]);
        }
        if (i < fibonacci) {
            i++;
            sucesion(fibonacci, num, i);
        }
    }
     }> 

Jejeje si recuerso la pelicula del Origen o Inceptión.
Y su parodia de Rick y Morty.

Me gusto la forma sencilla de explicar recursión
Es una forma sencilla de repetir una misma acción varias veces.

function fib(n<2){
    if (n<=1){
        return n
    } 
    return fib(n-1) + fib(n-2);
}
console.log(fib(6))

const fib = n =>	(n< 2) ? n :	fib(n-1) + fib(n-2);
console.log(fib(6));