loop - recursive programming python

Agregar recursivamente a una lista vinculada ordenada

Question

Estoy intentando crear una función de agregar para agregar recursivamente a una lista vinculada ordenada y parece que no puedo comenzar. Me dieron las dos funciones

    def add(self, item):
        new_node = Node(item)
        curr = self.__head
        prev = None
        self.add_recursive(new_node, curr, prev)

    def add_recursive(self, new_node, curr, prev):
            pass

Sé cómo agregar a una lista vinculada ordenada en un método tradicional, pero no puedo entender cómo hacerlo llamando de esta manera, así como con recursividad. Otras funciones que se pueden usar en esta clase son .is_empty() y .size()

Gracias

Answer 1

Cuando se trata de estructuras jerárquicas (como árboles), el cerebro humano puede visualizar fácilmente la recursión (pensamos recursivamente), pero con estructuras planas como listas enlazadas, esto ciertamente parece más difícil de lograr.

Vamos a romper esto. ¿En qué punto deberíamos agregar un nodo? Ciertamente, cuando sabemos que no hay nodos en frente de curr . En este punto, asignaría curr.next = new_node y lo devolverá. Hasta entonces, avanzas curr y continúas. Esto es lo que sucede también en el sentido iterativo.

Al poner esta comprensión en el código, tendrías

def add_recursive(self, new_node, curr, prev):
    """ note that we aren''t yet taking care of the case when head is None """
    if not curr.next:                
        curr.next = new_node
        return

    return self.add_recursive(new_node, cur.next, cur)

Una consideración importante es el caso de la esquina cuando se está insertando por primera vez. En ese caso, llamaría a .is_empty o size y verificará si la lista vinculada tiene elementos o no, y en consecuencia asignará self.head = new_node :

if self.is_empty():
    self.head = new_node
    return

Este es el primer control que debe hacerse. Entonces, tu función completa ahora se convierte en:

def add_recursive(self, new_node, curr, prev):
    if self.is_empty():
        self.head = new_node
        return

    elif not curr.next:                
        curr.next = new_node
        return

    return self.add_recursive(new_node, cur.next, cur)