Introducción

1

Grafos y Árboles: Estructuras de Datos Avanzadas

2

Estructuras de Datos: Introducción a Árboles y Sus Propiedades

3

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

4

Aplicaciones Prácticas de Grafos en Tecnología e Industria

5

Representación de Grafos: Matriz y Lista de Adyacencia

DFS

6

Búsqueda en Profundidad (DFS) en Árboles y Grafos

7

Implementación de DFS recursivo para búsqueda en árboles

8

Búsqueda en Profundidad (DFS) para Grafos: Enfoque Iterativo y Recursivo

9

Recorridos y Profundidad en Árboles Binarios y Enearios

10

Suma de Caminos en Árboles Binarios

11

Suma de Números de Raíz a Hoja en Árboles

12

Playground: Sum Root to Leaf Numbers

13

Implementación de Algoritmo DFS en Árboles Binarios con Golang

14

Resolución del Problema de Número de Islas con DFS

15

Conteo de Islas en Matrices con DFS

16

Playground: Number of Islands

17

Implementación de "Número de Islas" con Recursión en Python

18

Ejercicios Prácticos de Búsqueda en Profundidad (DFS)

19

Algoritmos de Búsqueda en Profundidad (DFS) en Problemas Comunes

BFS

20

Algoritmo BFS: Recorrido en Anchura de Grafos y Árboles

21

Implementación de BFS en Árboles usando Python

22

Movimiento mínimo de caballo en ajedrez infinito

23

Resolviendo el Problema Mínimo de Movimiento del Caballo en Ajedrez

24

Playground: Minimum Knights Moves

25

Resolución de Problemas de Caballos de Ajedrez con BFS en Python

26

Propagación de Plagas en Cultivos: Cálculo de Días para Contagio Total

27

Resolución de Rotting Oranges usando BFS

28

Playground: Rotting Oranges

29

Propagación de Plagas en Matrices usando BFS en Java

30

Construcción de Puentes Cortos entre Islas en Matrices Binarias

31

Resolución del Problema Shortest Bridge con DFS y BFS

32

Playground: Shortest Bridge Between Islands

33

Búsqueda del camino más corto entre islas usando BFS en Python

34

Búsqueda en anchura: Ejercicios prácticos y aplicaciones

35

Ejercicios avanzados de búsqueda en anchura (BFS) en programación

Backtrack

36

Algoritmo Backtracking: Solución de Problemas Complejos

37

Combinaciones de Letras en Números Telefónicos

38

Combinaciones de Letras a partir de un Número de Teléfono

39

Generación de combinaciones de letras con teclados numéricos en C++

40

Playground: Letter Combinations of a Phone Number

41

Generación de Direcciones IP Válidas a partir de Cadenas Numéricas

42

Generación de IPs válidas con backtracking en C++

43

Playground: Restore IP Addresses

44

Búsqueda de Palabras en Matrices: Solución y Complejidad

45

Búsqueda de Palabras en Matrices usando Backtracking y DFS

46

Playgrund: Word Search

47

Implementación de búsqueda de palabras en matrices con DFS en JavaScript

48

Resolución del problema de las n reinas en ajedrez

49

Ejercicios de Backtracking: Combinaciones y Permutaciones

50

Combinaciones y Permutaciones con Backtracking

Próximos pasos

51

Algoritmos de Grafos: MIN/MAX-HIP, TRI, Topological Sort y Dijkstra

52

Algoritmos y Estructuras de Datos en la Ingeniería

No tienes acceso a esta clase

¡Continúa aprendiendo! Únete y comienza a potenciar tu carrera

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

3/52
Recursos

¿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.

Aportes 20

Preguntas 0

Ordenar por:

¿Quieres ver más aportes, preguntas y respuestas de la comunidad?

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

Aquí una implementación en Go: ```js 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 } ```
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`
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))`
\#2024 ```js 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] ```
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
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.
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é. ```java 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 { 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 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);
        }
    }
     }> 
Buena analogía. De la caja dentro de la caja

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