Contenido principal
Ciencias de la computación
Curso: Ciencias de la computación > Unidad 1
Lección 6: Algoritmos recursivos- Recursividad
- La función factorial
- Desafío: factorial iterativo
- Factorial recursivo
- Desafío: factorial recursivo
- Propiedades de los algoritmos recursivos
- Usar recursividad para determinar si una palabra es un palíndromo o no
- Desafío: ¿una cadena de caracteres es un palíndromo?
- Calcular potencias de un número
- Desafío: potencias recursivas
- Recursividad múltiple con el triángulo de Sierpinski
- Mejorar la eficiencia de las funciones recursivas
- Proyecto: arte recursivo
© 2023 Khan AcademyTérminos de usoPolítica de privacidadAviso de cookies
Mejorar la eficiencia de las funciones recursivas
La recursividad puede ser una manera elegante para resolver un problema y muchos algoritmos se prestan para soluciones recursivas. Sin embargo, los algoritmos recursivos pueden ser ineficientes en términos tanto de tiempo como de espacio. Aquí vamos a exponer varias técnicas para mejorar su eficiencia.
En el desafío de codificación para calcular recursivamente el factorial de un número, te pedimos llamar la función varias veces con diferentes valores.
Por ejemplo, este código de JavaScript llama
factorial()
4 veces:factorial(0);
factorial(2);
factorial(5);
factorial(10);
Consideremos todas las llamadas que hace la computadora al ejecutar esas 4 líneas de código:
Línea de código | Llamadas recursivas | Total de llamadas |
---|---|---|
factorial(0) | 1 llamada | |
factorial(2) | factorial(1) → factorial(0) | 3 llamadas |
factorial(5) | factorial(4) → factorial(3) → factorial(2) → factorial(1) → factorial(0) | 6 llamadas |
factorial(10) | factorial(9) → factorial(8) → factorial(7) → factorial(6) → factorial(5) → factorial(4) → factorial(3) → factorial(2) → factorial(1) → factorial(0) | 11 llamadas |
Observa que
factorial(10)
tiene que hacer 11 llamadas de la función, y 6 de ellas tienen exactamente los mismos argumentos y valores de resultado que las llamadas anteriores de la función realizadas durante factorial(5)
.Memoización del factorial
Podemos usar una técnica llamada memoización para ahorrar tiempo a la computadora al hacer llamadas idénticas a la función. La memoización (una forma de caché) recuerda el resultado de una llamada a la función con entradas particulares en una tabla de búsqueda (el "memo") y devuelve ese resultado cuando se llama la función de nuevo con las mismas entradas.
Una memoización de la función factorial podría verse así:
- Si
= 0, regresa 1 - De lo contrario, si
está en el memo, regresa el valor del memo para - De lo contrario,
- Calcula
- Almacena el resultado en el memo
- Regresa el resultado
- Calcula
Este algoritmo revisa el valor de entrada en el memo antes de hacer una llamada recursiva potencialmente costosa. El memo debe ser una estructura de datos con tiempos de búsqueda eficientes, tales como una tabla hash con un tiempo de búsqueda de .
Si quieres visualizar la ejecución del algoritmo memoizado implementado en JavaScript, mira este video o ejecuta la visualización tú mismo. Antes de verlo, tal vez quieras desafiarte a implementar el algoritmo en el lenguaje de programción de tu elección.
Con la memoización implementada, la computadora puede hacer menos llamadas totales sobre llamadas repetidas a
factorial()
:Línea de código | Llamadas recursivas | Total de llamadas |
---|---|---|
factorial(0) | 1 llamada | |
factorial(2) | factorial(1) → factorial(0) | 3 llamadas |
factorial(5) | factorial(4) → factorial(3) → factorial(2) | 3 llamadas |
factorial(10) | factorial(9) → factorial(8) → factorial(7) → factorial(6) → factorial(5) | 6 llamadas |
La memoización hace un intercambio entre el tiempo y el espacio. Mientras la búsqueda sea eficiente y la función sea llamada repetidamente, la computadora puede ahorrar tiempo a costa de usar memoria para almacenar el memo.
Memoización de Fibonacci
En el caso de la función factorial, un algoritmo solo se beneficia de la optimización de la memoización cuando un programa hace llamadas repetidas a la función durante su ejecución. Sin embargo, en algunos casos, la memoización puede ahorrar tiempo incluso para una única llamada a una función recursiva.
Veamos un ejemplo simple: el algoritmo para generar números de Fibonacci.
La sucesión de Fibonacci es una serie famosa de números donde el siguiente número en la sucesión es la suma de los 2 números anteriores. Los dos primeros números de la sucesión están definidos como y . Después de eso, el siguiente número es (a partir de ) y el siguiente número después de eso es (a partir de ), y así sucesivamente.
Los primeros 10 números de Fibonacci:
Una función recursiva simple para generar el -ésimo número de Fibonacci se ve así:
- Si
es 0 o 1, regresa - De lo contrario, regresa
Este algoritmo es un ejemplo de recursividad múltiple ya que se llama a sí mismo varias veces. Para entender las múltiples llamadas que realiza la computadora, es útil visualizar las llamadas como un árbol.
Cuando , la computadora hace 15 llamadas:
Observa las múltiples llamadas a la función fibonacci para los valores de entrada de 3, 2, 1 y 0. A medida que las entradas se hacen más grandes, esto se vuelve cada vez más ineficiente. Una llamada a
fibonacci(30)
da como resultado que la computadora llame fibonacci(2)
más de medio millón de veces.Aquí podemos usar la memoización para evitar que la computadora recalcule un número de Fibonacci que ya está calculado.
La versión memoizada del algoritmo recursivo de Fibonacci se ve así:
- Si
es 0 o 1, regresa - De lo contrario, si
está en el memo, regresa el valor del memo para - De lo contrario,
- Calcula
- Almacena el resultado en el memo
- Regresa el resultado
- Calcula
Si quieres visualizar la ejecución del algoritmo memoizado implementado en JavaScript, mira este video o ejecuta la visualización tú mismo.
Para , la computadora hace 9 llamadas:
La versión original del algoritmo requirió 15 llamadas de la función, por lo que la memoización eliminó 6 llamadas.
Esta tabla muestra el número de llamadas requeridas desde hasta :
Original | Memoizado | |
---|---|---|
5 | 15 | 9 |
6 | 25 | 11 |
7 | 41 | 13 |
8 | 67 | 15 |
9 | 109 | 17 |
10 | 177 | 19 |
El número total de llamadas a la función aumenta a una tasa exponencial para el algoritmo original, pero a una tasa lineal mucho más lenta para el algoritmo memoizado.
Sin embargo, el algoritmo memoizado requiere más espacio, suficiente para que el memo almacene cada valor de respuesta de .
De abajo arriba
A veces, la mejor manera de mejorar la eficiencia de un algoritmo recursivo es no usar la recursividad en absoluto.
En el caso de estar generando números de Fibonacci, una técnica iterativa llamada el enfoque de abajo arriba nos puede ahorrar tanto tiempo como espacio. Cuando se utiliza un enfoque de abajo arriba, la computadora primero resuelve los subproblemas y utiliza los resultados parciales para llegar al resultado final.
Un enfoque de abajo arriba para la generación de números de Fibonacci se ve así:
- Si
es 0 o 1, regresa - De lo contrario,
- Crea la variable
para recordar el resultado de e inicializa su valor a 0 - Crea la variable
para recordar el resultado de e inicializa su valor a 1 - Crea la variable
para almacenar el resultado final e inicializa su valor a 0 - Repite
veces:- Actualiza
a que sea la suma de más - Actualiza
para almacenar el valor actual de - Actualiza
para almacenar el valor actual de - Regresa
- Actualiza
- Crea la variable
Este enfoque nunca hace una llamada recursiva; en su lugar, utiliza la iteración para sumar los resultados parciales y calcular el número.
Si quieres visualizar la ejecución del algoritmo de abajo arriba implementado en JavaScript, mira este video o ejecuta la visualización tú mismo.
El algoritmo de abajo arriba tiene la misma complejidad de tiempo que el algoritmo memoizado, pero solo requiere de espacio, ya que solo recuerda tres números a la vez.
Programación dinámica
La memoización y de abajo arriba son técnicas de programación dinámica, una estrategia de resolución de problemas que se utiliza en matemáticas y ciencias de la computación.
La programación dinámica se puede utilizar cuando un problema tiene una subestructura óptima y superposición de subproblemas. La subestructura óptima significa que la solución óptima al problema se puede crear a partir de soluciones óptimas de sus subproblemas. En otras palabras,
fib(5)
puede resolverse con fib(4)
y fib(3)
. La superposición de subproblemas ocurre siempre que un subproblema se resuelve varias veces, lo cual vimos cuando fib(5)
hizo varias llamadas a las típicamente recursivas fib(3)
y fib(2)
.La programación dinámica se puede utilizar para una serie de problemas e involucra otras técnicas además de las que aprendimos aquí. Si estás trabajando en un problema con una subestructura óptima y superposición de subproblemas, considera si un enfoque de programación dinámica podría funcionar.
¿Quieres unirte a la conversación?
- ¿Que ejecicios o libros recomendarian para entender mejor este tema?(3 votos)