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.
Introducción
Grafos y Árboles: Estructuras de Datos Avanzadas
Estructuras de Datos: Introducción a Árboles y Sus Propiedades
Recursión: Concepto y Aplicaciones Prácticas con Ejemplos
Aplicaciones Prácticas de Grafos en Tecnología e Industria
Representación de Grafos: Matriz y Lista de Adyacencia
DFS
Búsqueda en Profundidad (DFS) en Árboles y Grafos
Implementación de DFS recursivo para búsqueda en árboles
Búsqueda en Profundidad (DFS) para Grafos: Enfoque Iterativo y Recursivo
Recorridos y Profundidad en Árboles Binarios y Enearios
Suma de Caminos en Árboles Binarios
Suma de Números de Raíz a Hoja en Árboles
Playground: Sum Root to Leaf Numbers
Implementación de Algoritmo DFS en Árboles Binarios con Golang
Resolución del Problema de Número de Islas con DFS
Conteo de Islas en Matrices con DFS
Playground: Number of Islands
Implementación de "Número de Islas" con Recursión en Python
Ejercicios Prácticos de Búsqueda en Profundidad (DFS)
Algoritmos de Búsqueda en Profundidad (DFS) en Problemas Comunes
BFS
Algoritmo BFS: Recorrido en Anchura de Grafos y Árboles
Implementación de BFS en Árboles usando Python
Movimiento mínimo de caballo en ajedrez infinito
Resolviendo el Problema Mínimo de Movimiento del Caballo en Ajedrez
Playground: Minimum Knights Moves
Resolución de Problemas de Caballos de Ajedrez con BFS en Python
Propagación de Plagas en Cultivos: Cálculo de Días para Contagio Total
Resolución de Rotting Oranges usando BFS
Playground: Rotting Oranges
Propagación de Plagas en Matrices usando BFS en Java
Construcción de Puentes Cortos entre Islas en Matrices Binarias
Resolución del Problema Shortest Bridge con DFS y BFS
Playground: Shortest Bridge Between Islands
Búsqueda del camino más corto entre islas usando BFS en Python
Búsqueda en anchura: Ejercicios prácticos y aplicaciones
Ejercicios avanzados de búsqueda en anchura (BFS) en programación
Backtrack
Algoritmo Backtracking: Solución de Problemas Complejos
Combinaciones de Letras en Números Telefónicos
Combinaciones de Letras a partir de un Número de Teléfono
Generación de combinaciones de letras con teclados numéricos en C++
Playground: Letter Combinations of a Phone Number
Generación de Direcciones IP Válidas a partir de Cadenas Numéricas
Generación de IPs válidas con backtracking en C++
Playground: Restore IP Addresses
Búsqueda de Palabras en Matrices: Solución y Complejidad
Búsqueda de Palabras en Matrices usando Backtracking y DFS
Playgrund: Word Search
Implementación de búsqueda de palabras en matrices con DFS en JavaScript
Resolución del problema de las n reinas en ajedrez
Ejercicios de Backtracking: Combinaciones y Permutaciones
Combinaciones y Permutaciones con Backtracking
Próximos pasos
Algoritmos de Grafos: MIN/MAX-HIP, TRI, Topological Sort y Dijkstra
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
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.
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.
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.
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.
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).
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
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))
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));
¿Quieres ver más aportes, preguntas y respuestas de la comunidad?