Recursividad aplicada a listas versus árboles en Python

Mi principal preocupación con la recursividad es el límite de recursividad en Python, que creo que es 1000. Teniendo esto en cuenta, quiero analizar dos escenarios:

Escenario 1: aplicación de recursividad para un árbol equilibrado (binario)

Por ejemplo, para buscar el valor máximo en un árbol:

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def max(root):
    max_left = max(root.left)
    max_right = max(root.right)
    if max_left > root.value and max_left > max_right:
        return max_left
    if max_right > root.value and max_right > max_left:
        return max_right
    else:
        return root.value

Aquí, el número máximo de llamadas en la pila en un momento dado será la altura del árbol, que es log_2(n) donde n es el número de elementos en la lista. Dado que el límite en Python es de 1000 llamadas, el árbol podría almacenar hasta 2^1000 (o 2^999) elementos sin alcanzar el límite de llamadas. Para mí, eso no es una limitación real, así que supongo que podemos usar la recursividad aquí.

Escenario 2: aplicar recursividad a una lista

Un ejemplo ficticio sería calcular el máximo de una lista, de modo que devolvamosel máximo entre el encabezado de la lista y el resultado de la misma función sobre el resto de la lista:

def max(l):
    if len(l) == 1:
        return l[0]
    max_tail = max(l[1:])
    if l[0] > max_tail:
        return l[0]
    else:
        return max_tail

Salida:

>>> max(list(range(998)))
997
>>> max(list(range(999)))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 4, in max
  File "<stdin>", line 4, in max
  File "<stdin>", line 4, in max
  [Previous line repeated 995 more times]
  File "<stdin>", line 2, in max
RecursionError: maximum recursion depth exceeded while calling a Python object

Así que tengo entendido que para las listas la recursividad no es una opción razonable, ya que generalmente no puede procesar listas mayores que 999 (o incluso menos, dependiendo del seguimiento de la pila).

Ahora, mis preguntas:

¿Es razonable utilizar la recursividad para procesar árboles equilibrados? ¿Es cierto que para la mayoría de los problemas simplemente no es una opción (listas, árboles no equilibrados, etc.)? ¿Algo más que deba tener en cuenta aquí? Solo estoy tratando de aprender más sobre cuándo la recursividad es la buena opción en general cuando se usa Python.

Si calcula cuántas recursiones se requieren para un árbol equilibrado de cierto tamaño y lo compara con el límite de recursividad, tendrá la respuesta para 1.

Carcigénico

28/03/2021 a las 13:50

@Carcigenicate estamos bien en términos del límite de llamadas a funciones de Python. ¿Pero no sería más eficiente en cuanto a espacio utilizar la versión iterativa? ¿Usáis habitualmente la recursividad para este tipo de cosas?tareas?

- Selnay

28/03/2021 a las 13:54

1

Para el primer caso con el árbol, si hubiera determinado que no había forma de exceder el límite, sí, usaría la recursividad allí. Sería mucho mejor que mantener una pila yo mismo para hacer el mismo trabajo. Si encuentro que el espacio es un problema, lo convertiría a una versión iterativa para manejarlo. Para la lista, no, definitivamente no usaría la recursividad. Una iteración simple sería mucho mejor.

Carcigénico

28/03/2021 a las 13:56

1

chrispenner.ca/posts/python-tail-recursion

-David Brabante

28/03/2021 a las 14:15

------------------------------------

En primer lugar, ten en cuenta que no es lo mismo un lenguaje que la implementación de un lenguaje. El tamaño de la pila de llamadas en Python varía según la implementación. El límite de 1000 se aplica a CPython pero no necesariamente a todas las implementaciones.

Es¿Es razonable utilizar la recursividad para procesar árboles equilibrados?

La recursividad es razonable para árboles equilibrados. Como ha descrito con bastante claridad, la profundidad máxima de la pila de llamadas es un factor logarítmico del tamaño de la estructura. Necesitarías una gran aportación para hacer explotar la pila.

Con una lista o un árbol degenerado desequilibrado, la recursividad es inapropiada porque la profundidad máxima de la pila de llamadas es lineal en la longitud de la estructura.

Dicho esto, no creo que sea necesario utilizar árboles autoequilibrados con frecuencia en Python. La mayor parte del trabajo se realiza en listas y dictados, ocasionalmente anidados y definidos de forma recursiva. El hecho de que la recursividad sea una buena opción para estructuras como árboles no implica que sea ampliamente aplicable en general en Python.

¿Es cierto que para la mayoría de los problemas simplemente no es una opción (listas, árboles no balanceados, etc)?

Sí, pero la recursividad está inhibida por diseño en CPython. Python no es un lenguaje funcional. CPython no admite la optimización de llamadas finales y "nunca" voluntad.

Guido tiene una excelente publicación en el blog que defiende el diseño anti-recursivo de CPython. Independientemente de si está de acuerdo con este diseño o no, las herramientas generalmente deben usarse según lo previsto, no como uno desea que sean.

En caso de necesidad, Python (como lenguaje multiparadigma) puede admitir código escrito en un estilo funcional y existen soluciones para hacer que la recursividad larga funcione, pero eso no cambia el hecho de que son soluciones alternativas.

¿Algo más que deba tener en cuenta aquí? Sólo estoy tratando de aprender más sobre cuándo la recursividad es la buena opción en general cuando se usa Python.

Las llamadas a funciones en CPython tienen más sobrecarga (tiempo y espacio) que la iteración, por lo que hay problemas de rendimiento a considerar incluso cuando el tamaño de la estructura cabe en la pila de llamadas o se utiliza un truco para admitir una recursividad profunda.

Usar setrecursionlimit no es seguro y casi nunca es necesario. Esta opción no está disponible en la mayoría de los idiomas. Aumentarlo significa que corre el riesgo de que el sistema operativo elimine el intérprete CPython. Claro, jugar con el límite puede resultar útil para secuencias de comandos y depuración rápidas, pero no es una solución general.

La etiqueta de recursividad está inundada de preguntas de estudiantes de informática bien intencionados encargados de resolver problemas con recursividad similar a su ejemplo que explota la pila usando Python y otros lenguajes no funcionales. La cantidad delEstas publicaciones y la confusión por parte de los estudiantes sugieren que el sistema educativo de informática tiene un papel en impulsar la recursividad como la opción predeterminada para la iteración. La recursividad es tan elegante como el grado en que el lenguaje fue diseñado para ella. El hecho de que la recursividad tienda a confundir a los estudiantes es más un síntoma de su mala aplicación en lenguajes imperativos donde la recursividad es un ciudadano de segunda clase después de los bucles que algo inherente a la recursividad en sí.

Probablemente nunca necesitarás recursividad en Python, aparte de las tareas escolares, los desafíos de codificación de algoritmos y el poco común uso práctico de aplicaciones empresariales. Pero si tienes un martillo, todo parece un clavo, así que esto no quiere decir que no puedas aplicar la recursividad a todos y cada uno de los problemas que veas, sino que probablemente deberías hacerlo.No podría.

El pensamiento recursivo es muy valioso, y esto no es un ataque a la recursividad como herramienta en general, simplemente reconoce que Python es particularmente inadecuado para usarlo (como lo son la mayoría de los otros lenguajes imperativos).

No está relacionado con la recursividad y entiendo que su código es solo una demostración, pero max es una función incorporada, por lo que elegiría un nombre diferente. Tomado solo, parece que max(list(range(999))) debería funcionar.

------------------------------------

Puedes hacer trampolines en Python si realmente deseas escribir tu código de manera recursiva. Pero escribir tu código de forma iterativa es mucho más real.tic.

Puedes crear una función de trampolín basada en generadores como se ilustra en esta publicación de blog:

http://www.usrsb.in/blog/blog/2012/08/12/bouncing-pythons-generators-with-a-trampoline/

def tramp(gen, *args, **kwargs):
    g = gen(*args, **kwargs)
    while isinstance(g, types.GeneratorType):
        g=g.next()
    return g

También puedes cambiar el límite de recursividad en Python, lo que no siempre se recomienda y rara vez se considera una solución adecuada; pero es posible.

from sys import setrecursionlimit
setrecursionlimit(10**8)