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

Clase 3 de 52 • Curso de Algoritmos Avanzados: Grafos y Árboles

Resumen

¿Qué es la recursión?

La recursión es una técnica de programación que permite a una función llamarse a sí misma. Aunque puede sonar abstracto, es una herramienta poderosa para resolver problemas que pueden dividirse en subproblemas más pequeños. Al igual que buscar un objeto en una serie de cajas cada vez más pequeñas hasta encontrarlo, la recursión es útil cuando repetimos la misma operación, pero cada vez con conjuntos de datos más pequeños.

¿Cómo funciona la recursión en la vida diaria?

Imagina que estás buscando una pulsera en un cajón, dentro del cual hay varias cajas anidadas hasta llegar a la más pequeña donde finalmente encuentras el objeto. En este caso, cada nivel de búsqueda dentro de una caja más pequeña representa una llamada recursiva a la función, donde el objetivo es encontrar el objeto. Este proceso imita el funcionamiento de la recursión sea en programación o en situaciones reales.

¿Qué papel juegan los casos base en la recursión?

Para que la recursión no se prolongue indefinidamente, es esencial establecer un caso base. El caso base es el punto en el cual la función deja de llamarse a sí misma porque ya ha encontrado la solución o alcanzado la condición de parada. En nuestro ejemplo de la pulsera, el caso base sería encontrar la caja que contiene el objeto buscado.

¿Qué es la secuencia de Fibonacci?

La secuencia de Fibonacci es una serie infinita de números presentes en la naturaleza, el arte y varias áreas más. Se inicia con dos números, cero y uno, y los dos valores se suman para obtener el siguiente número en la secuencia.

¿Cómo se relaciona Fibonacci con la recursión?

La relación entre la secuencia de Fibonacci y la recursión radica en cómo se puede calcular cada número de la secuencia basándose en los dos anteriores. Al usar recursión, una función puede calcular Fibonacci para un número dado n, descomponiéndose repetidamente en los cálculos de Fibonacci(n-1) y Fibonacci(n-2).

¿Cómo evitar cálculos repetidos en Fibonacci?

Al implementar una función recursiva para la secuencia de Fibonacci, surge el problema de recalcular los mismos valores múltiples veces, lo que resulta ineficiente. La solución a este problema de optimización puede lograrse mediante técnicas como la memorización o el almacenamiento en caché de resultados intermedios ya calculados, reduciendo así el número de operaciones necesarias y mejorando la eficiencia del código.

Pro Code

student•

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/

Camila Púa

student•

lo probé con 6 y me da 13 :/ debería dar 8, no?

Camila Púa

student•

ya, es que en las líneas del if

if n == 0 or n == 1: return 1

está devolviendo 1 incluso cuando es 0, en realidad debería retornar n, así:

if n == 0 or n == 1: return n

Así retornará 0 o 1 cuando sea necesario c;

Usuario anónimo

user•

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.

Santiago García Rincón

student•

Exactamente, memorización es una tecnica de DP

Fernando Famanía

student•

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

Santiago García Rincón

student•

Excelente, es la tecnica de memorización y es utilizada en DP.

Mauricio Combariza

student•

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)))

Mauricio Combariza

student•

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))

Oscar Uriel Cortés Zanabria

student•

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]

Pro Code

student•

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));
}

Pro Code

student•

Representación de la recursividad con la muñeca tradicional rusa, Matrioska:

Santiago García Rincón

student•

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

Fernando Sánchez Mejía

student•

Para la función fiboacci.

Gabriel Calvo Vargas

student•

Aquí una implementación en Go:

func fib(num int, cache map[int]int) int {
	if num <= 1 {
		return num
	}
	if res, ok := cache[num]; ok {
		return res
	}
	result := fib(num-1, cache) + fib(num-2, cache)
	cache[num] = result
	return result
}

Miguel Angel Reyes Moreno

student•

Ejemplo de fibonacci con memoización en Python:

def fibonacci_memo(n, memo={}):

"""Calculates the nth Fibonacci number using memoization."""

if n in memo:

return memo[n]

if n <= 1:

result = n

else:

result = fibonacci_memo(n-1, memo) + fibonacci_memo(n-2, memo)

memo[n] = result

return result

# Example usage:

result = fibonacci_memo(7)

print(result) # Output: 13

Reinaldo Mendoza

student•

Excelente idea usar memoizacion

Israel Villa Olvera

student•

asi me quedo a mi:

def fibo(n, memo={}): if n == 0 or n == 1: return n if n not in memo: memo[n] = fibo(n - 1) + fibo(n - 2) return memo[n]

print(fibo(6))

José Angél Rodríguez Estrada

student•

#2024

def fibSencilla(n, dp):
    if n == 1 or n == 2:
        dp[n] = 1
        return 1
    if dp[n] != -1:
        return dp[n]
    dp[n] = fibSencilla(n-1, dp) + fibSencilla(n-2, dp)
    return dp[n]

Elias Guillermo Ruiz Gonzalez

student•

para acelerar la ejecucion usando valores ya calculados se pueden adicionar mas ifs segun los valores que conozcamos if n=8 return 13 if n=16 return 610 ... y asi

Kevin Vega

student•

La recursión es un concepto fundamental en informática y matemáticas que se refiere a la técnica de resolver problemas mediante la división en casos más pequeños y la auto-referencia.

Yojan Antonio Pardo Zabala

student•

Esta es mi solución en java, utilicé un HashMap para la caché y en lugar de crear los casos para cuando n = 1 || 0 inserto esas llaves para que las encuentre en la validación de la caché.

public class Fibonacci {

    static Map<Integer, Long> cache = new HashMap<>();

    static {
        cache.put(0, 0L);
        cache.put(1, 1L);

    }

    public static void main(String[] args) {
        final Scanner sc = new Scanner(System.in);

        System.out.println("ingrese el valor a calcular");

        final int fibonacciSeries = sc.nextInt();

        System.out.println("resultado final: " + calcularFibonacci(fibonacciSeries));
    }

    private static long calcularFibonacci(int n) {
        System.out.println(n);

        if(cache.get(n) != null){
            System.out.println("valor en cache: [" + n + "] : [" + cache.get(n) + "]");
            return cache.get(n);
        }

        long result = calcularFibonacci(n-1) + calcularFibonacci(n-2);
        System.out.println("añadiendo valor: [" + result + "] a la cache en la posicion: [" + n + "]");
        cache.put(n, result);
        return result;
    }
}
```public class Fibonacci {

&#x20;   static Map\<Integer, Long> *cache* = new HashMap<>();
&#x20;   static {
&#x20;       *cache*.put(0, 0L);
&#x20;       *cache*.put(1, 1L);
&#x20;   }

&#x20;   public static void main(String\[] args) {
&#x20;       final Scanner sc = new Scanner(System.*in*);
&#x20;       System.*out*.println("ingrese el valor a calcular");
&#x20;       final int fibonacciSeries = sc.nextInt();
&#x20;       System.*out*.println("resultado final: " + *calcularFibonacci*(fibonacciSeries));
&#x20;   }

&#x20;   private static long calcularFibonacci(int n) {
&#x20;       System.*out*.println(n);
&#x20;       if(*cache*.get(n) != null){
&#x20;           System.*out*.println("valor en cache: \[" + n + "] : \[" + *cache*.get(n) + "]");
&#x20;           return *cache*.get(n);
&#x20;       }

&#x20;       long result = *calcularFibonacci*(n-1) + *calcularFibonacci*(n-2);
&#x20;       System.*out*.println("añadiendo valor: \[" + result + "] a la cache en la posicion: \[" + n + "]");
&#x20;       *cache*.put(n, result);
&#x20;       return result;
&#x20;   }
}

Camilo Forero

student•

<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);
        }
    }
     }>

Fernando Sánchez Mejía

student•

Buena analogía. De la caja dentro de la caja

Fernando Sánchez Mejía

student•

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

Mauricio Combariza

student•

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

Jeisson Felipe Rodriguez Prieto

student•

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));