4.4. Las tres leyes de la recursividad¶
Al igual que los robots de Asimov, todos los algoritmos recursivos deben obedecer tres leyes importantes:
Un algoritmo recursivo debe tener un caso base.
Un algoritmo recursivo debe cambiar su estado y moverse hacia el caso base.
Un algoritmo recursivo debe llamarse a sí mismo, recursivamente.
Echemos un vistazo a cada una de estas leyes con más detalle y veamos cómo se usó en el algoritmo sumalista. En primer lugar, un caso base es la condición que permite que el algoritmo detenga la recursividad. Un caso base es típicamente un problema que es lo suficientemente pequeño como para resolverlo directamente. En el algoritmo sumalista el caso base es una lista de longitud 1.
Para obedecer la segunda ley, debemos organizar un cambio de estado que mueva el algoritmo hacia el caso base. Un cambio de estado significa que se modifican algunos datos que el algoritmo está usando. Por lo general, los datos que representan nuestro problema se hacen más pequeños de alguna manera. En el algoritmo sumalista nuestra estructura de datos primaria es una lista, así que debemos centrar nuestros esfuerzos de cambio de estado en la lista. Dado que el caso base es una lista de longitud 1, una progresión natural hacia el caso base es acortar la lista. Esto es exactamente lo que ocurre en la línea 5 del ActiveCode 2 cuando llamamos a sumalista con una lista más corta.
La última ley es que el algoritmo debe llamarse a sí mismo. Esta es la definición misma de la recursividad. La recursividad es un concepto confuso para muchos programadores principiantes. Como programador principiante, usted ha aprendido que las funciones son buenas porque usted puede tomar un problema grande y descomponerlo en problemas más pequeños. Los problemas más pequeños pueden resolverse escribiendo una función para resolver cada problema. Cuando hablamos de recursividad, puede parecer que estamos hablando en círculos. Tenemos un problema que resolver con una función, ¡pero esa función resuelve el problema llamándose a sí misma! Pero la lógica no es circular en absoluto; la lógica de la recursividad es una expresión elegante de resolver un problema al descomponerlo en problemas más pequeños y más fáciles.
En lo restante de este capítulo veremos más ejemplos de recursividad. En cada caso nos centraremos en diseñar una solución a un problema usando las tres leyes de la recursividad.
Autoevaluación
- 6
- Sólo hay cinco números en la lista, el número de llamadas recursivas no será mayor que el tamaño de la lista.
- 5
- La llamada inicial a sumalista no es una llamada recursiva.
- 4
- La primera llamada recursiva pasa la lista [4,6,8,10], la segunda [6,8,10] y así sucesivamente hasta [10].
- 3
- Esta no sería una cantidad suficiente de llamadas para cubrir todos los números de la lista
Q-1: ¿Cuántas llamadas recursivas se realizan al calcular la sumatoria de la lista [2,4,6,8,10]?
- n == 0
- Aunque esto funcionaría hay opciones mejores y un poco más eficientes. Dado que fact(1) y fact(0) valen lo mismo.
- n == 1
- Una buena opción, pero ¿qué pasa si usted llama a fact(0)?
- n >= 0
- Este caso base sería verdadero para todos los números mayores que cero, así que el factorial de cualquier número positivo sería 1.
- n <= 1
- Bien, éste es el más eficiente, e incluso previene que su programa colapse si se intenta calcular el factorial de un número negativo.
Q-2: Suponga que usted va a escribir una función recusiva para calcular el factorial de un número. fact(n) devuelve n * n-1 * n-2 * … , donde el factorial de cero está definido como 1. ¿Cuál sería el caso base más apropiado?