La recursión es una técnica de abstracción que se basa en dividir un problema en situaciones o problemas más pequeños que tienen la misma forma
Diseño Top-Down: Una estrategia de diseño para programas de gran tamaño. Usa el proceso denominado como "Descomposicion de problemas" en el cual se asigna una funcion para cada subproblema (mas manejables)
Diseño de funciones recursivo: Un problema es partido en subproblemas de la misma forma, en este caso se asigna cada problema a la misma función que resuelve el problema en un nivel superior.
EJEMPLO 1: Sumnatoria de una secuencia de enteros a partir de una cota inferior hasta un límite superior.
Si tenemos 1 + 2 + 3 + 4 entonces la funcion sumatoria(1,4) nos debería retornar la suma de todos los elementos de la secuencia, osea 10.
La solucion empieza reconociendo que esta secuencia de sumas contiene las siguientes sumas anidadas: sumatoria(1, 4) = 1 + sumatoria(2, 4) sumatoria(2, 4) = 2 + sumatoria(3, 4) sumatoria(3, 4) = 3 + sumatoria(4, 4) sumatoria(4, 4) = 4
Cada llamada de la funcion sumatoria a exception de la ultima llama otra vez a la misma funcion sumatoria. Esta llamada is conocida como una llamada recursiva de la funcion.
La ultima llamada no retorna una llamada recursiva de la funcion sino que retorna uno de sus argumentos directamente, esto es conocido como el caso base de la funcion.
En cada llamada a la funcion el primer argumento incrementa en uno lo cual eventualmente hará que se alcance el límite que detedría el proceso recursivo, osea esto permite que le funcion detecte cuando la recursion debe finalizar y retornar el valor del caso base.
Entonces ahora podemos pensar en plantearnos una fórmula general para la versión recursiva de la función sumatoria con sus argumentos que podemos denominar bajo y alto por ejemplo, la misma que plantea dos ecuaciones, la primera se refiere a cuando los dos argumentos son iguales y la segunda en el caso contrario:
sumatoria(bajo, alto) = alto si bajo == alto
sumatoria(bajo, alto) = bajo + sumatoria(bajo + 1, alto)
"""
Archivo: sumatoria.py
Define y prueba una función recursiva para sumatoria.
"""
def sumatoria(bajo, alto):
"""
Retorna la sumatoria de los enteros desde 'bajo' hasta 'alto'.
Precondición: bajo <= alto.
"""
if bajo == alto:
return alto
else:
return bajo + sumatoria(bajo + 1, alto)
if __name__ == '__main__':
print('La sumatoria de ', 1, ' hasta ', 4, ' es ', sumatoria(1,4))
EJEMPLO 2: Serie de Fibonacci
"""
Archivo: fibonacci.py
Calcula recursivamente los n primeros términos de la serie de fibonacci.
"""
def fibonacci(n):
if n < 3:
return 1
else:
print (n)
return fibonacci(n - 1) + fibonacci(n - 2)
if __name__ == "__main__":
print('Los 5 primeros términos de la serie de fibonacci son:', fibonacci(5))
Lambert, Kenneth A.. Python Programming for Teens. Boston, MA, USA: Cengage Learning PTR, 2014. ProQuest ebrary. Web. 16 July 2015.