Declaraciones de retorno y recursión de Python

Question

Soy bastante nuevo en Python y en las funciones recursivas como un todo, así que disculpe mi ignorancia.

Estoy tratando de implementar un árbol binario de búsqueda en Python y tienen el siguiente método de inserción (sacado de una clase):

def insert(self, key, root=None): 
    '''Inserts a node in the tree''' 
    if root == None: 
     root = self.root 
    if root.key == None: 
     self._update(root, key) 
     return 0 
    else: 
     tmp = root 
     if key > tmp.key: # we work with the right subtree 
      self.insert(key, root=tmp.right) 
     elif key < tmp.key: # we work with the left subtree 
      self.insert(key, root=tmp.left) 
     else: # key already exists 
      return 0 

No estoy seguro de si esto es legible, pero atraviesa el árbol hasta que llegue a un valor Ninguno y actualice el nodo con la clave para insertar.

Ahora, el método funciona bien y crea correctamente una BST desde cero. Pero hay un problema con las declaraciones de devolución, ya que solo devuelve 0 si no se realiza recursividad.

>>> bst.insert(10) 
0 
>>> bst.insert(15) 
>>> bst.root.right.key 
15 
>>> 

"Insertar" nuevamente la clave raíz devuelve 0 (de la línea 15) de la manera que debería.

>>> bst.insert(10) 
0 

No puedo entender por qué sucede esto. Si pongo una declaración de impresión en la línea 6, se ejecuta correctamente, sin embargo, no devolverá nada después de la primera inserción. ¿Por qué es esto? (Estoy bastante seguro de que me falta algo de información básica con respecto a Python y recursividad)

Gracias por su ayuda,

Ivan

PS: He leído que la repetición no es la mejor manera de Implementar un BST, entonces buscaré otras soluciones, pero me gustaría saber la respuesta a esto antes de continuar.

Answer 1

En sus líneas recursivas, no devuelve nada. Si quieres que vuelva 0, debe reemplazarlos con líneas como:

return self.insert(key, root=tmp.left) 

en lugar de sólo

self.insert(key, root=tmp.left) 

Answer 2

Estás dentro de una función y desea devolver un valor, ¿qué haces? Usted escribe

def function(): 
    return value 

En su caso, debe devolver el valor devuelto por una llamada a la función, por lo que debe hacerlo.

def function(): 
    return another_function() 

Sin embargo, usted

def function(): 
    another_function() 

¿Por qué cree que debería funcionar? Por supuesto que utiliza recursividad, pero en tal caso debe recordar el Zen de Python que simplemente dice:

Los casos especiales no son lo suficientemente especiales como para infringir las reglas.