Contenido principal

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 $n$ ‍ = 0, regresa 1
De lo contrario, si $n$ ‍ está en el memo, regresa el valor del memo para $n$ ‍
De lo contrario,
- Calcula $(n - 1)! \times n$ ‍
- Almacena el resultado en el memo
- Regresa el resultado

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

O (1)

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

0

1

. Después de eso, el siguiente número es

1

(a partir de

0 + 1

) y el siguiente número después de eso es

2

(a partir de

1 + 1

), y así sucesivamente.

Los primeros 10 números de Fibonacci:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34

Una función recursiva simple para generar el

n

-ésimo número de Fibonacci se ve así:

Si $n$ ‍ es 0 o 1, regresa $n$ ‍
De lo contrario, regresa $fibonacci (n - 1) + fibonacci (n - 2)$ ‍

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

n = 5

, la computadora hace 15 llamadas:

Contenedor video de Khan Academy

Recursive Fibonacci Calls (Diagrammed)Ver la transcripción del video

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 $n$ ‍ es 0 o 1, regresa $n$ ‍
De lo contrario, si $n$ ‍ está en el memo, regresa el valor del memo para $n$ ‍
De lo contrario,
- Calcula $fibonacci (n - 1) + fibonacci (n - 2)$ ‍
- Almacena el resultado en el memo
- Regresa el resultado

Si quieres visualizar la ejecución del algoritmo memoizado implementado en JavaScript, mira este video o ejecuta la visualización tú mismo.

Para

n = 5

, la computadora hace 9 llamadas:

Contenedor video de Khan Academy

Memoized Recursive Fibonacci Calls (Diagrammed)Ver la transcripción del video

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

n = 5

hasta

n = 10

$n$ ‍	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

n

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 $n$ ‍ es 0 o 1, regresa $n$ ‍
De lo contrario,
- Crea la variable $twoBehind$ ‍ para recordar el resultado de $(n - 2)$ ‍ e inicializa su valor a 0
- Crea la variable $oneBehind$ ‍ para recordar el resultado de $(n - 1)$ ‍ e inicializa su valor a 1
- Crea la variable $result$ ‍ para almacenar el resultado final e inicializa su valor a 0
- Repite $(n - 1)$ ‍ veces:
  - Actualiza $result$ ‍ a que sea la suma de $twoBehind$ ‍ más $oneBehind$ ‍
  - Actualiza $twoBehind$ ‍ para almacenar el valor actual de $oneBehind$ ‍
  - Actualiza $oneBehind$ ‍ para almacenar el valor actual de $result$ ‍
  - Regresa $result$ ‍

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

O (n)

que el algoritmo memoizado, pero solo requiere

O (1)

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.

[Créditos]

¿Quieres unirte a la conversación?

Inicia sesión

Ordenar por:

joseotniel2010
Publicado hace hace 3 años. Enlace directo a la publicación “¿Que ejecicios o libros r...” de joseotniel2010
¿Que ejecicios o libros recomendarian para entender mejor este tema?
Botón que navega a la página de registroBotón que navega a la página de registro
(3 votos)
Respuesta

¿Sabes inglés? Haz clic aquí para ver más discusiones en el sitio en inglés de Khan Academy.