Python Language
Recursion

Observaciones

Suma de números del 1 al n

Si quisiera averiguar la suma de los números del 1 al n donde n es un número natural, puedo hacer 1 + 2 + 3 + 4 + ... + (several hours later) + n . Alternativamente, podría escribir un bucle for :

n = 0
for i in range (1, n+1):
    n += i

O podría usar una técnica conocida como recursión:

def recursion(n):
    if n == 1:
        return 1
    return n + recursion(n - 1)

La recursión tiene ventajas sobre los dos métodos anteriores. La recursión toma menos tiempo que escribir 1 + 2 + 3 para una suma de 1 a 3. Para la recursion(4) , la recursión se puede usar para trabajar hacia atrás:

Llamadas a funciones: (4 -> 4 + 3 -> 4 + 3 + 2 -> 4 + 3 + 2 + 1 -> 10)

Mientras que el bucle for está trabajando estrictamente hacia adelante: (1 -> 1 + 2 -> 1 + 2 + 3 -> 1 + 2 + 3 + 4 -> 10). A veces, la solución recursiva es más simple que la solución iterativa. Esto es evidente cuando se implementa una reversión de una lista vinculada.

El qué, cómo y cuándo de la recursión

La recursión se produce cuando una llamada de función hace que esa misma función se vuelva a llamar antes de que finalice la llamada de función original. Por ejemplo, considere la expresión matemática conocida x! (Es decir, la operación factorial). La operación factorial se define para todos los enteros no negativos de la siguiente manera:

• Si el número es 0, entonces la respuesta es 1.
• De lo contrario, la respuesta es que el número multiplicado por el factorial es uno menos que ese número.

En Python, una implementación ingenua de la operación factorial se puede definir como una función de la siguiente manera:

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

Las funciones de recursión pueden ser difíciles de comprender a veces, así que veamos esto paso a paso. Considera la expresión factorial(3) . Esta y todas las llamadas a funciones crean un nuevo entorno . Un entorno es básicamente una tabla que asigna identificadores (por ejemplo, n , factorial , print , etc.) a sus valores correspondientes. En cualquier momento, puede acceder al entorno actual utilizando locals() . En la primera llamada a la función, la única variable local que se define es n = 3 . Por lo tanto, la impresión de locals() mostraría {'n': 3} . Como n == 3 , el valor de retorno se convierte en n * factorial(n - 1) .

En este siguiente paso es donde las cosas pueden ser un poco confusas. Mirando nuestra nueva expresión, ya sabemos qué es n . Sin embargo, todavía no sabemos qué factorial(n - 1) es. Primero, n - 1 evalúa a 2 . Entonces, 2 se pasa a factorial como el valor para n . Dado que se trata de una nueva llamada de función, se crea un segundo entorno para almacenar esta nueva n . Sea A el primer entorno y B el segundo entorno. A todavía existe y es igual a {'n': 3} , sin embargo, B (que es igual a {'n': 2} ) es el entorno actual. Al observar el cuerpo de la función, el valor de retorno es, nuevamente, n * factorial(n - 1) . Sin evaluar esta expresión, vamos a sustituirla en la expresión de retorno original. Al hacer esto, estamos descartando mentalmente B , así que recuerde sustituir n consecuencia (es decir, las referencias a B 's n se reemplazan con n - 1 que usa A ' s n ). Ahora, la expresión de retorno original se convierte en n * ((n - 1) * factorial((n - 1) - 1)) . Tome un segundo para asegurarse de que entiende por qué esto es así.

Ahora, evaluemos la porción factorial((n - 1) - 1)) de eso. Como A 's n == 3 , estamos pasando 1 a factorial . Por lo tanto, estamos creando un nuevo entorno C que es igual a {'n': 1} . Una vez más, el valor de retorno es n * factorial(n - 1) . Entonces, reemplacemos factorial((n - 1) - 1)) de la expresión de retorno "original" de manera similar a como ajustamos la expresión de retorno original anteriormente. La expresión "original" ahora es n * ((n - 1) * ((n - 2) * factorial((n - 2) - 1))) .

Casi termino. Ahora, necesitamos evaluar factorial((n - 2) - 1) . Esta vez, estamos pasando en 0 . Por lo tanto, esto se evalúa a 1 . Ahora, vamos a realizar nuestra última sustitución. La expresión de retorno "original" ahora es n * ((n - 1) * ((n - 2) * 1)) . Recordando que la expresión de retorno original se evalúa en A , la expresión se convierte en 3 * ((3 - 1) * ((3 - 2) * 1)) . Esto, por supuesto, se evalúa a 6. Para confirmar que esta es la respuesta correcta, ¡recuerde que 3! == 3 * 2 * 1 == 6 . Antes de seguir leyendo, asegúrese de comprender completamente el concepto de entornos y cómo se aplican a la recursión.

La declaración if n == 0: return 1 se llama un caso base. Esto se debe a que no exhibe recursión. Un caso base es absolutamente necesario. Sin uno, te encontrarás con una recursión infinita. Dicho esto, siempre que tenga al menos un caso base, puede tener tantos casos como desee. Por ejemplo, podríamos haber escrito un factorial equivalente de la siguiente manera:

def factorial(n):
    if n == 0:
        return 1
    elif n == 1:
        return 1
    else:
        return n * factorial(n - 1)

También puede tener varios casos de recursión, pero no vamos a entrar en eso, ya que es relativamente poco frecuente y, a menudo, es difícil de procesar mentalmente.

También puede tener llamadas de función recursiva "paralelas". Por ejemplo, considere la secuencia de Fibonacci que se define de la siguiente manera:

• Si el número es 0, entonces la respuesta es 0.
• Si el número es 1, entonces la respuesta es 1.
• De lo contrario, la respuesta es la suma de los dos números anteriores de Fibonacci.

Podemos definir esto como sigue:

def fib(n):
    if n == 0 or n == 1:
        return n
    else:
        return fib(n - 2) + fib(n - 1)

No recorreré esta función tan a fondo como lo hice con factorial(3) , pero el valor de retorno final de fib(5) es equivalente a la siguiente expresión ( sintácticamente no válida):

(
  fib((n - 2) - 2)
  +
  (
    fib(((n - 2) - 1) - 2)
    +
    fib(((n - 2) - 1) - 1)
  )
)
+
(
  (
    fib(((n - 1) - 2) - 2)
    +
    fib(((n - 1) - 2) - 1)
  )
  +
  (
    fib(((n - 1) - 1) - 2)
    +
    (
      fib((((n - 1) - 1) - 1) - 2)
      +
      fib((((n - 1) - 1) - 1) - 1)
    )
  )
)

Esto se convierte en (1 + (0 + 1)) + ((0 + 1) + (1 + (0 + 1))) que, por supuesto, se evalúa en 5 .

Ahora, vamos a cubrir algunos términos más de vocabulario:

• Una llamada de cola es simplemente una llamada de función recursiva que es la última operación que se realiza antes de devolver un valor. Para ser claros, return foo(n - 1) es una llamada de cola, pero return foo(n - 1) + 1 no (ya que la adición es la última operación).
• La optimización de llamadas de cola (TCO) es una forma de reducir automáticamente la recursión en funciones recursivas.
• La eliminación de la llamada de cola (TCE) es la reducción de una llamada de la cola a una expresión que se puede evaluar sin recursión. TCE es un tipo de TCO.

La optimización de llamadas de cola es útil por varias razones:

• El intérprete puede minimizar la cantidad de memoria ocupada por los entornos. Como ninguna computadora tiene memoria ilimitada, las llamadas excesivas a funciones recursivas conducirían a un desbordamiento de pila .
• El intérprete puede reducir el número de interruptores de cuadros de pila .

Python no tiene una forma de TCO implementada por varias razones . Por lo tanto, se requieren otras técnicas para evitar esta limitación. El método de elección depende del caso de uso. Con algo de intuición, las definiciones de factorial y fib se pueden convertir de manera relativamente fácil a código iterativo de la siguiente manera:

def factorial(n):
    product = 1
    while n > 1:
        product *= n
        n -= 1
    return product

def fib(n):
    a, b = 0, 1
    while n > 0:
        a, b = b, a + b
        n -= 1
    return a

Esta suele ser la forma más eficiente de eliminar manualmente la recursión, pero puede ser bastante difícil para funciones más complejas.

Otra herramienta útil es el decorador lru_cache de Python, que se puede usar para reducir el número de cálculos redundantes.

Ahora tiene una idea de cómo evitar la recursión en Python, pero ¿cuándo debería usar la recursión? La respuesta es "no a menudo". Todas las funciones recursivas pueden ser implementadas iterativamente. Es simplemente una cuestión de averiguar cómo hacerlo. Sin embargo, hay casos raros en los que la recursión está bien. La recursión es común en Python cuando las entradas esperadas no causan un número significativo de llamadas a una función recursiva.

Si la recursión es un tema que le interesa, le imploro que estudie lenguajes funcionales como Scheme o Haskell. En tales idiomas, la recursión es mucho más útil.

Tenga en cuenta que el ejemplo anterior para la secuencia de Fibonacci, aunque es bueno para mostrar cómo aplicar la definición en python y el uso posterior de la caché lru, tiene un tiempo de ejecución ineficiente ya que realiza 2 llamadas recursivas para cada caso no básico. El número de llamadas a la función crece exponencialmente a n .
Más bien, de forma no intuitiva, una implementación más eficiente usaría la recursión lineal:

def fib(n):
    if n <= 1:
        return (n,0)
    else:
        (a, b) = fib(n - 1)
        return (a + b, a)

Pero ese tiene el problema de devolver un par de números. Esto enfatiza que algunas funciones realmente no ganan mucho con la recursión.

Exploración de árboles con recursión

Digamos que tenemos el siguiente árbol:

root
- A
  - AA
  - AB
- B
  - BA
  - BB
    - BBA

Ahora, si deseamos enumerar todos los nombres de los elementos, podríamos hacer esto con un simple bucle for. Suponemos que hay una función get_name() para devolver una cadena del nombre de un nodo, una función get_children() para devolver una lista de todos los get_children() de un nodo dado en el árbol, y una función get_root() para obtener el nodo raíz

root = get_root(tree)
for node in get_children(root):
    print(get_name(node))
    for child in get_children(node):
        print(get_name(child))
        for grand_child in get_children(child):
            print(get_name(grand_child))
# prints: A, AA, AB, B, BA, BB, BBA

Esto funciona bien y rápido, pero ¿qué pasa si los subnodos tienen subnodos propios? Y esos subnodos podrían tener más subnodos ... ¿Qué pasa si no sabe de antemano cuántos habrá? Un método para resolver esto es el uso de la recursión.

def list_tree_names(node):
    for child in get_children(node):
        print(get_name(child))
        list_tree_names(node=child)

list_tree_names(node=get_root(tree))
# prints: A, AA, AB, B, BA, BB, BBA

Quizás desee no imprimir, pero devuelva una lista plana de todos los nombres de nodo. Esto se puede hacer pasando una lista móvil como parámetro.

def list_tree_names(node, lst=[]):
    for child in get_children(node):
        lst.append(get_name(child))
        list_tree_names(node=child, lst=lst)
    return lst

list_tree_names(node=get_root(tree))
# returns ['A', 'AA', 'AB', 'B', 'BA', 'BB', 'BBA']

Incrementando la profundidad máxima de recursión

Hay un límite a la profundidad de la posible recursión, que depende de la implementación de Python. Cuando se alcanza el límite, se genera una excepción RuntimeError:

RuntimeError: Maximum Recursion Depth Exceeded

Aquí hay una muestra de un programa que causaría este error:

def cursing(depth):
  try:
    cursing(depth + 1) # actually, re-cursing
  except RuntimeError as RE:
    print('I recursed {} times!'.format(depth))
cursing(0)
# Out: I recursed 1083 times!

Es posible cambiar el límite de profundidad de recursión usando

sys.setrecursionlimit(limit) 

Puede verificar cuáles son los parámetros actuales del límite ejecutando:

sys.getrecursionlimit()

Ejecutando el mismo método anterior con nuestro nuevo límite obtenemos

sys.setrecursionlimit(2000)
cursing(0)
# Out: I recursed 1997 times!

Desde Python 3.5, la excepción es un RecursionError, que se deriva de RuntimeError.

Recursión de cola - Mala práctica

Cuando lo único que se devuelve de una función es una llamada recursiva, se la denomina recursión de cola.

Aquí hay un ejemplo de cuenta regresiva escrita usando la recursión de la cola:

def countdown(n):
    if n == 0:
        print "Blastoff!"
    else:
        print n
        countdown(n-1)

Cualquier cálculo que se pueda hacer usando la iteración también se puede hacer usando la recursión. Aquí hay una versión de find_max escrita usando la recursión de la cola:

def find_max(seq, max_so_far):
    if not seq:
        return max_so_far
    if max_so_far < seq[0]:
        return find_max(seq[1:], seq[0])
    else:
        return find_max(seq[1:], max_so_far)

La recursión de cola se considera una mala práctica en Python, ya que el compilador de Python no maneja la optimización para las llamadas recursivas de cola. La solución recursiva en casos como este utiliza más recursos del sistema que la solución iterativa equivalente.

Optimización de la recursión de cola a través de la introspección de la pila

Por defecto, la pila de recursión de Python no puede exceder los 1000 cuadros. Esto se puede cambiar configurando sys.setrecursionlimit(15000) que es más rápido, sin embargo, este método consume más memoria. En su lugar, también podemos resolver el problema de recursión de cola utilizando la introspección de pila.

#!/usr/bin/env python2.4
# This program shows off a python decorator which implements tail call optimization. It
# does this by throwing an exception if it is it's own grandparent, and catching such 
# exceptions to recall the stack.

import sys

class TailRecurseException:
    def __init__(self, args, kwargs):
        self.args = args
        self.kwargs = kwargs

def tail_call_optimized(g):
"""
This function decorates a function with tail call
optimization. It does this by throwing an exception
if it is it's own grandparent, and catching such
exceptions to fake the tail call optimization.
  
This function fails if the decorated
function recurses in a non-tail context.
"""
      
    def func(*args, **kwargs):
        f = sys._getframe()
        if f.f_back and f.f_back.f_back and f.f_back.f_back.f_code == f.f_code:
            raise TailRecurseException(args, kwargs)
        else:
            while 1:
                try:
                    return g(*args, **kwargs)
                except TailRecurseException, e:
                    args = e.args
                    kwargs = e.kwargs
    func.__doc__ = g.__doc__
    return func

Para optimizar las funciones recursivas, podemos usar el decorador @tail_call_optimized para llamar a nuestra función. Aquí hay algunos de los ejemplos comunes de recursión que utilizan el decorador descrito anteriormente:

Ejemplo factorial:

@tail_call_optimized
def factorial(n, acc=1):
  "calculate a factorial"
  if n == 0:
    return acc
  return factorial(n-1, n*acc)

print factorial(10000)
# prints a big, big number,
# but doesn't hit the recursion limit.

Ejemplo de Fibonacci:

@tail_call_optimized
def fib(i, current = 0, next = 1):
  if i == 0:
    return current
  else:
    return fib(i - 1, next, current + next)

print fib(10000)
# also prints a big number,
# but doesn't hit the recursion limit.