¿Quieres aprender todo sobre la recursividad en programación? Este tutorial sobre recursividad en Python le ayudará a empezar.
La recursividad es una técnica de resolución de problemas muy útil para agregar a la caja de herramientas de su programador. Si bien al principio suele resultar difícil entenderlo, la recursividad puede ayudarle a encontrar soluciones más elegantes a problemas complejos.
En este tutorial, adoptaremos un enfoque basado en el código para aprender la recursividad usando Python. En particular, cubriremos:
- Los fundamentos de la recursividad
- Funciones recursivas y cómo funcionan.
- Implementación de funciones recursivas en Python
- Diferencias entre enfoques iterativos y recursivos para la resolución de problemas
¡Empecemos!
Tabla de contenido
¿Qué es la recursividad?
La recursividad es una técnica de programación en la que una función se llama a sí misma repetidamente para resolver un problema.
En esencia, la recursividad es un enfoque de resolución de problemas que implica dividir un problema complejo en subproblemas más pequeños e idénticos. Básicamente, le permite resolver un problema en términos de versiones más simples de sí mismo.
Entonces, ¿cómo implementamos la recursividad en el código? Para ello, comprendamos cómo funcionan las funciones recursivas.
Comprender las funciones recursivas
Definimos una función recursiva que se llama a sí misma dentro de su definición. Cada llamada recursiva representa una versión más pequeña o más simple del problema original.
Para garantizar que la recursividad finalmente termine, las funciones recursivas deben incluir uno o más casos base: condiciones bajo las cuales la función deja de llamarse a sí misma y devuelve un resultado.
Analicemos esto más. Una función recursiva consta de:
- Caso base: El caso base es una condición (o condiciones) que determinan cuándo debe detenerse la recursividad. Cuando se cumple el caso base, la función devuelve un resultado sin realizar más llamadas recursivas. Un caso base es esencial para evitar la recursividad infinita.
- Caso recursivo: el caso recursivo define cómo dividir el problema en subproblemas más pequeños. En esta parte de la función, la función se llama a sí misma con entradas modificadas. Cada llamada recursiva es, por tanto, un paso hacia llegar al caso base.
A continuación, analicemos lo que sucede cuando llamas a una función recursiva.
Cómo funciona la recursividad bajo el capó
Cuando se llama a una función, se coloca un registro de su contexto de ejecución en la pila de llamadas. Este registro incluye información sobre los argumentos de la función, las variables locales y la ubicación a regresar una vez que la función finaliza su ejecución.
En el caso de funciones recursivas, cuando una función se llama a sí misma, se inserta un nuevo registro en la pila de llamadas, suspendiendo efectivamente la ejecución de la función actual. La pila permite a Python realizar un seguimiento de todas las llamadas a funciones pendientes, incluidas las de llamadas recursivas.
Hasta que se alcanza el caso base, la recursividad continúa. Cuando el caso base devuelve un resultado, las llamadas a la función se resuelven una por una, y cada función devuelve su resultado al nivel anterior de la pila de llamadas. Este proceso continúa hasta que se completa la llamada a la función inicial.
Implementando la recursividad en Python
En esta sección, exploraremos tres ejemplos simples de recursividad:
Para cada ejemplo, plantearemos el problema, proporcionaremos la implementación recursiva de Python y luego explicaremos cómo funciona la implementación recursiva.
#1. Cálculo factorial mediante recursividad
Problema: Calcule el factorial de un número entero no negativo n, denotado como n!. Matemáticamente, el factorial de un número n es el producto de todos los números enteros positivos del 1 al n.
El cálculo factorial se presta bien a la recursividad, como se muestra:
Aquí está la función recursiva para calcular el factorial de un número n dado:
def factorial(n):
# Base case
if n == 0 or n == 1:
return 1
# Recursive case: n! = n * (n-1)!
else:
return n * factorial(n - 1)
¡Calculemos 5! usando la función factorial():
factorial_5 = factorial(5) print(factorial(5)) # Output: 120
Ahora veamos cómo funciona la función:
- Tenemos un caso base que verifica si n es igual a 0 o 1. Si se cumple la condición, las funciones devuelven 1. ¡Recuerde que 0! es 1, ¡y también lo es 1!.
- Si n es mayor que 1, calculamos n! multiplicando n por el factorial de n-1. Esto se expresa como n * factorial(n – 1).
- La función sigue realizando llamadas recursivas con valores decrecientes de n hasta que llega al caso base.
#2. Números de Fibonacci con recursividad
Problema: Encuentre el término en el índice n-ésimo del secuencia Fibonacci. La secuencia de Fibonacci se define de la siguiente manera: F(0) = 0, F(1) = 1 y F(n) = F(n-1) + F(n-2) para n >= 2.
def fibonacciSeq(n):
# Base cases
if n == 0:
return 0
elif n == 1:
return 1
# Recursion: F(n) = F(n-1) + F(n-2)
else:
return fibonacciSeq(n - 1) + fibonacciSeq(n - 2)
Ejecutemos la función:
fib_5 = fibonacciSeq(5) print(fib_5) # Output: 5
Así es como funciona la función:
- Comencemos discutiendo los casos base. Si n es 0, devuelve 0. Y si n es 1, devuelve 1. Recuerde F(0) = 0 y F(1) = 1.
- En el caso recursivo, si n es mayor que 1, la función calcula F(n) sumando los términos F(n-1) y F(n-2). Esto se expresa como fibonacciSeq(n – 1) + fibonacciSeq(n – 2).
- La función sigue realizando llamadas recursivas con valores decrecientes de n hasta que llega a los casos base.
#3. Implementación recursiva de búsqueda binaria
Problema: implemente un algoritmo de búsqueda binaria utilizando recursividad para encontrar la posición de un elemento de destino en una lista ordenada.
Aquí está la implementación recursiva de la búsqueda binaria:
def binarySearch(arr, target, low, high):
# Base case: target not found
if low > high:
return -1
mid = (low + high) // 2
# Base case: target found
if arr[mid] == target:
return mid
# Recursive case: search left or right half of the array
elif arr[mid] > target:
return binarySearch(arr, target, low, mid - 1)
else:
return binarySearch(arr, target, mid + 1, high)
La función binarioSearch sigue dividiendo el intervalo de búsqueda a la mitad con cada llamada recursiva hasta que encuentra el objetivo o determina que el objetivo no está en la lista.
A continuación se muestra una ejecución de muestra de la función:
arr = [5, 8, 13, 24, 37, 49, 51, 64, 72, 88, 96] target = 37 idx = binarySearch(arr, target, 0, len(arr)-1) print(idx) # Output: 4
Analicemos qué hace la función:
- En la implementación recursiva de búsqueda binaria, tenemos dos casos base. Primero, si el nivel bajo es mayor que el nivel alto, significa que el elemento objetivo no está en la lista. Entonces, devolvemos -1 para indicar que no se encontró el objetivo.
- El otro caso base comprueba si el elemento en el índice medio del intervalo de búsqueda actual es igual al objetivo. Si coinciden, devolvemos el índice mid, indicando que hemos encontrado el objetivo.
- En el caso recursivo, si el elemento del medio es mayor que el objetivo, buscamos recursivamente en la mitad izquierda de la matriz llamando a binarioSearch(arr, target, low, mid – 1). Si el elemento del medio es menor que el objetivo, buscamos la mitad derecha llamando a binarioSearch(arr, target, mid + 1, high).
Enfoque recursivo versus iterativo
El enfoque iterativo (utilizar bucles) es otro enfoque común para la resolución de problemas. Entonces, ¿en qué se diferencia de la recursividad? Vamos a averiguar.
Primero, comparamos soluciones recursivas e iterativas a un problema común: calcular el factorial de un número.
Aquí está la implementación recursiva del cálculo factorial:
def factorialRec(n):
# Base case
if n == 0 or n == 1:
return 1
# Recursive case: n! = n * (n-1)!
else:
return n * factorial(n - 1)
Como sabemos que el factorial de un número no negativo es el producto de todos los números desde 1 hasta n, también podemos escribir una implementación iterativa usando bucles.
def factorialIter(n):
result = 1
for i in range(1, n + 1):
result *= i
return result
Ambas implementaciones dan resultados idénticos.
factorial_5 = factorialRec(5) print(factorial_5) # Output: 120 factorial_5 = factorialIter(5) print(factorial_0) # Output: 120
Pero, ¿se prefiere un enfoque iterativo a la recursividad? Cuando hay una recursividad profunda (con demasiadas llamadas a funciones), es posible que se produzcan errores debido a que se excede la profundidad de la recursividad. El bucle es una mejor opción para problemas cuya implementación recursiva requiere demasiadas llamadas a funciones para llegar al caso base.
Resumamos las diferencias entre implementaciones iterativas y recursivas:
CaracterísticaEnfoque recursivoEnfoque iterativoEstructuraUtiliza llamadas a funciones recursivas y se basa en la pila de llamadas.Utiliza bucles para la iteración sin llamadas a funciones adicionales.Casos baseRequiere casos base explícitos para detener la recursión.Normalmente utiliza condiciones de bucle para la terminación.RendimientoPuede ser menos eficiente en memoria debido a la pila de llamadas . La recursividad profunda a veces puede provocar errores de desbordamiento de la pila. Generalmente, es más eficiente en cuanto a memoria y menos propenso a errores de desbordamiento de la pila. Depuración Puede ser difícil depurar debido a múltiples llamadas a funciones y contextos de ejecución anidados. Normalmente, es más fácil de depurar debido a un flujo lineal directo de ejecución. .Enfoque iterativo versus recursivo
Conclusión
En este artículo, comenzamos aprendiendo qué es la recursividad y cómo definir funciones recursivas con casos base y relaciones de recurrencia.
Luego escribimos algo de código Python: implementaciones recursivas de problemas de programación comunes. Finalmente, aprendimos las diferencias entre los enfoques iterativos y recursivos y los pros y los contras de cada uno de estos enfoques.
A continuación, consulte esta lista de preguntas de la entrevista de Python.