recursiones - recursiveness python

Python recursión y declaraciones de retorno

Question

Soy bastante nuevo en Python y las funciones recursivas en general, así que perdona mi ignorancia.

Estoy tratando de implementar un árbol de búsqueda binario en Python y tengo el siguiente método de inserción (tomado 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 alcanza un valor Ninguno y actualiza el nodo con la clave para insertar.

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

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

"Insertar" la clave raíz de nuevo devuelve 0 (de la línea 15) como 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, pero no devolverá nada después de la primera inserción. ¿Por qué es esto? (Estoy bastante seguro de que me falta información básica sobre Python y la recursión)

Gracias por tu ayuda,

Ivan

PD: He leído que la recursión no es la mejor manera de implementar un BST, así que buscaré otras soluciones, pero me gustaría saber la respuesta a esto antes de continuar.

Answer 1

En tus líneas recursivas, no devuelves nada. Si desea que devuelva 0, debe reemplazarlos con líneas como:

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

en lugar de solo

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

Answer 2

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

def function():
return value

En su caso, desea devolver el valor devuelto por una llamada de función, por lo que tiene que hacerlo.

def function():
return another_function()

Sin embargo usted hace

def function():
another_function()

¿Por qué crees que debería funcionar? Por supuesto, usas la recursión, pero en tal caso deberías recordar el Zen de Python que simplemente dice:

Los casos especiales no son lo suficientemente especiales para romper las reglas.