2

Acabo de encontrarme con un problema. He hecho un algoritmo recursivo que va haciendo appends conforme recorre ciertos índices. Aquí pongo una versión modificada a modo de ejemplo:

def example(text, result):
    for i in range(5):
        if text.startswith(str(i)):
            result.append(example(text.replace(str(i), ""), result))
    return result

result = example("1234", [])

El resultado es una lista del tipo:

[[...], [...], [...], [...]]

Que es una lista infinita, da igual las veces que accedas sobre ella, siempre mantiene la misma forma. He probado con una forma recursiva de obtener la longitud de la lista y salta un error de maximum recursion depth exceeded while calling a Python object, como si la lista fuese recursiva en sí.

def depth(count, result):
    if isinstance(result, list):
        count = depth(count+1, result[0])
    return count
depth(0, result)

Mi duda es, ¿Es esto algún tipo de lista u objeto que desconozco? ¿Tiene fin el hecho de poder acceder al primer elemento de la lista? ¿Por que al generarla no salta error pero sí que lo hace al calcular la profundidad?

Gracias de antemano!

1
  • He escrito una respuesta explicando qué tipo de lista recursiva es esa. No obstante la respuesta no aclara cómo habría que modificar el código para que funcione correctamente. Y la razón es que no entiendo realmente qué se supone que debe hacer ese código ¿cuál sería la salida que esperabas? Si me lo aclaras puedo extender la respuesta
    – abulafia
    el 15 dic. 2021 a las 12:15

1 respuesta 1

5

Es una estructura de datos recursiva, efectivamente.

Las listas en python lo que almacenan son referencias a otros objetos (que pueden ser a su vez listas), pero si una de esas referencias apunta a la misma lista, entonces tienes una estructura recursiva.

La forma más simple de crear una lista así es:

lista = []
lista.append(lista)

Gráficamente se entiende que la creación de esta lista no supone problema alguno, pues simplemente da lugar a lo siguiente:

imagen

Es una lista con un solo elemento. Ese elemento es ella misma. No hay problema tampoco en acceder a ese elemento usando lista[0], lo que obtienes es lista:

>>> lista[0] is lista
True

El problema con una lista así aparece en dos lugares:

  1. Al tratar de mostrarla. Al ser infinitamente recursiva Python empezaría a abrir corchetes sin parar para no cerrarlos nunca. Por suerte Python es listo, detecta que la lista es recursiva, y la representa de una forma especial: [[...]]

  2. Al tratar de descender por ella para hacer copias en profundidad. El descenso no terminará nunca. Por ejemplo con copy.deepcopy(lista) (aunque creo recordar que éste también es listo y detecta la recursividad). O en funciones como la depth() que has mostrado.

En cambio el cálculo de la longitud no daría problema len(lista) es 1 (pues solo tiene un elemento aunque sea ella misma)

En definitiva, tu método recursivo no es correcto si genera una lista recursiva como esta. Deberás replantearte en qué momento estás metiendo la misma lista otra vez dentro de ella como uno de sus elementos. Posiblemente lo que querrías hacer en ese punto sería meter una copia de la lista.

1

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.