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)