Comprender las funciones recursivas con Python

Cuando pensamos en repetir una tarea, generalmente pensamos en los bucles for y while. Estas construcciones nos permiten realizar iteraciones sobre una lista, colección, e...

Introducción

Cuando pensamos en repetir una tarea, solemos pensar en los bucles for y while. Estas construcciones nos permiten realizar iteración sobre una lista, colección, etc.

Sin embargo, existe otra forma de repetir una tarea, de una manera ligeramente diferente. Al llamar a una función dentro de sí misma, para resolver una instancia más pequeña del mismo problema, estamos realizando recursión.

Estas funciones se llaman a sí mismas hasta que se resuelve el problema, dividiendo prácticamente el problema inicial en muchas instancias más pequeñas de sí mismo, como por ejemplo, tomar pequeños bocados de un trozo de comida más grande.

El objetivo final es comer todo el plato de bolsas calientes, lo haces mordiendo una y otra vez. Cada mordida es una acción recursiva, después de la cual realizas la misma acción la próxima vez. Haces esto por cada bocado, evaluando que debes tomar otro para llegar a la meta, hasta que no queden bolsas calientes en tu plato.

¿Qué es la recursividad? {#qué es la recursividad}

Como se indicó en la introducción, [recursion] (https://en.wikipedia.org/wiki/Recursion) implica un proceso que se llama a sí mismo en la definición. Una función recursiva generalmente tiene dos componentes:

  • El caso base que es una condición que determina cuándo debe detenerse la función recursiva
  • La llamada a sí mismo

Echemos un vistazo a un pequeño ejemplo para demostrar ambos componentes:

1
2
3
4
5
6
7
8
9
# Assume that remaining is a positive integer
def hi_recursive(remaining):
    # The base case
    if remaining == 0:
        return
    print('hi')

    # Call to function, with a reduced remaining count
    hi_recursive(remaining - 1)

El caso base para nosotros es si la variable restante es igual a 0, es decir, cuántas cadenas "hola" restantes debemos imprimir. La función simplemente regresa.

Después de la declaración de impresión, llamamos hi_recursive nuevamente pero con un valor restante reducido. ¡Esto es importante! Si no disminuimos el valor de remaining, la función se ejecutará indefinidamente. Generalmente, cuando una función recursiva se llama a sí misma, los parámetros se cambian para estar más cerca del caso base.

Vamos a visualizar cómo funciona cuando llamamos a hi_recursive(3):

hi_recursive example

Después de que la función imprima 'hola', se llama a sí misma con un valor más bajo para remaining hasta que llega a 0. En cero, la función regresa a donde fue llamada en hi_recursive(1), que regresa a donde fue llamada en hi_recursive(2) y finalmente regresa a donde fue llamada en hi_recursive(3).

¿Por qué no usar un bucle?

Todo el recorrido se puede manejar con bucles. Aun así, algunos problemas a menudo se resuelven más fácilmente con la recursividad que con la iteración. Un caso de uso común para la recursividad es el recorrido del árbol:

Atravesar los nodos y las hojas de un árbol suele ser más fácil de pensar cuando se utiliza la recursividad. Aunque los bucles y la recursión atraviesan el árbol, tienen diferentes propósitos: los bucles están destinados a repetir una tarea, mientras que la recursión está destinada a dividir una tarea grande en tareas más pequeñas.

La recursión con árboles, por ejemplo, se bifurca bien porque podemos procesar todo el árbol procesando partes más pequeñas del árbol individualmente.

Ejemplos

La mejor manera de familiarizarse con la recursividad, o cualquier concepto de programación, es practicarlo. La creación de funciones recursivas es sencilla: asegúrese de incluir su caso base y llame a la función de manera que se acerque más al caso base.

Suma de una lista

Python incluye una función sum para listas. La implementación predeterminada de Python, CPython, usa un ciclo for indefinido en C para crear esas funciones (código fuente aquí para los interesados). Veamos cómo hacerlo con recursividad:

1
2
3
4
5
6
def sum_recursive(nums):
    if len(nums) == 0:
        return 0

    last_num = nums.pop()
    return last_num + sum_recursive(nums)

El caso base es la lista vacía - la mejor suma para eso es 0. Una vez que manejamos nuestro caso base, eliminamos el último elemento de la lista. Finalmente llamamos a la función sum_recursive con la lista reducida, y sumamos el número que sacamos al total.

En un intérprete de Python sum([10, 5, 2]) y sum_recursive([10, 5, 2]) deberían darte 17.

Números factoriales

Puede recordar que un [factorial] (https://en.wikipedia.org/wiki/Factorial) de un entero positivo es el producto de todos los enteros que lo preceden. El siguiente ejemplo lo dejaría más claro:

1
5! = 5 x 4 x 3 x 2 x 1 = 120

El signo de exclamación denota un factorial, y vemos que multiplicamos ‘5’ por el producto de todos los números enteros desde ‘4’ hasta ‘1’. ¿Qué pasa si alguien ingresa 0? Es ampliamente entendido y probado que 0! = 1. Ahora vamos a crear una función como la siguiente:

1
2
3
4
def factorial(n):
    if n == 0 or n == 1:
        return 1
    return n * factorial(n - 1)

Atendemos los casos en los que se ingresa 1 o 0, y de lo contrario multiplicamos el número actual por el factorial del número disminuido en 1.

Una simple verificación en tu intérprete de Python mostraría que factorial(5) te da 120.

Secuencia de Fibonacci

Una secuencia Fibonacci es aquella en la que cada número es la suma de los dos números anteriores. Esta secuencia supone que los números de Fibonacci para 0 y 1 también son 0 y 1. Por lo tanto, el equivalente de Fibonacci para 2 sería 1.

Veamos la sucesión y sus correspondientes números naturales:

1
2
    Integers:   0, 1, 2, 3, 4, 5, 6, 7
    Fibonacci:  0, 1, 1, 2, 3, 5, 8, 13

Podemos codificar fácilmente una función en Python para determinar el equivalente de Fibonacci para cualquier número entero positivo usando la recursividad:

1
2
3
4
5
6
def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

Puede verificar que funciona como se esperaba comprobando que fibonacci(6) es igual a 8.

Ahora me gustaría que considerara otra implementación de esta función que usa un bucle for:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def fibonacci_iterative(n):
    if n <= 1:
        return n

    a = 0
    b = 1
    for i in range(n):
        temp = a
        a = b
        b = b + temp
    return a

Si el entero es menor o igual a 1, devuélvelo. Ahora que nuestro caso base está manejado. Agregamos continuamente el primer número con el segundo almacenando el primer número en una variable temp antes de actualizarlo.

La salida es la misma que la primera función fibonacci(). Esta versión es más rápida que la recursiva, ya que las implementaciones de Python no están optimizadas para la recursividad pero sobresalen con la programación imperativa. Sin embargo, la solución no es tan fácil de leer como nuestro primer intento. Ahí reside una de las mayores fortalezas de la recursión: elegancia. Algunas soluciones de programación se resuelven de forma más natural mediante la recursividad.

Conclusión

La recursividad nos permite dividir una tarea grande en tareas más pequeñas llamándose repetidamente a sí misma. Una función recursiva requiere un caso base para detener la ejecución, y la llamada a sí misma que lleva gradualmente a la función al caso base. Se usa comúnmente en árboles, pero se pueden escribir otras funciones con recursividad para proporcionar soluciones elegantes.

Licensed under CC BY-NC-SA 4.0