Recursividad

Menu

Recursividad

¿Qué es recursividad?

La recursividad es un método para resolver problemas que implica descomponer un problema en subproblemas más y más pequeños hasta llegar a un problema lo suficientemente pequeño que pueda resolverse trivialmente. Por lo general, la recursividad implica una función que se llama a sí misma. Si bien puede no parecer mucho superficialmente, la recursividad nos permite escribir soluciones elegantes a los problemas que de otro modo podrían ser muy difíciles de programar.

Cálculo de la suma de una lista de números

def sumalista(listaNumeros):
laSuma = 0
for i in listaNumeros:
laSuma = laSuma + i
return laSuma
print(sumalista([1,3,5,7,9]))

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.

Recursión con una lista

Comencemos con un ejemplo básico: sumar todos los números de una lista. Sin recursiones podría ser:

def suma(lista):
suma = 0
# Suma cada numero de la lista.
for i in range(0,len(lista)):
suma = suma + lista[i]
# Devuelve la suma
return suma
print(suma([6,3,4,2,10]))

En donde simplemente llamamos a la función “suma”, la cual suma cada elemento a la variable “suma” y luego la retorna. Para hacer esto recursivamente:

def suma(lista):
if len(lista) == 1: # Caso base
return lista[0]
else:
return lista[0] + suma(lista[1:]) # La función se llama a si misma (Recursión)
# lista[1:] devuelve la lista sin su primer elemento
print(suma([6,3,4,2,10]))

Factorial con recursión

La definición matemática del factorial es n! = n * (n-1)!, si n > 1 y f(1) = 1. Ejemplo: 3! = 3 * 2 * 1 = 6. Se puede implementar en Python usando una función recursiva:

def fact(n):
if n == 1: # Caso base
return 1
else:
return n * fact(n-1)
print(fact(5))

Se hace la llamada a la función fact con n = 3. Esto devuelve n * (n-1). El proceso continúa hasta que n = 1. Cuando n = 1 la función retorna el valor final.

Limitaciones de la Recursión en Python

Cada vez que una función se llama a si misma ocupa memoria. Por lo tanto, una función recursiva, puede ocupar mucha mas memoria que una función tradicional. Python detiene la ejecución de las funciones luego de que exceden las 1000 ejecuciones. Si se ejecuta el siguiente ejemplo:

def factorial(n):
if n == 1:
return 1
else:
return n * factorial(n-1)
print(factorial(42))

Se obtendría el siguiente error: 4200