How to return value from recursive function in python?

Question

I'm working with binary tree in python. I need to create a method which searches the tree and return the best node where a new value can be inserted. But i'm have trouble returning a value from this recursive function. I'm a total newbie in python.

def return_key(self, val, node):
    if(val < node.v):
        if(node.l != None):
            self.return_key(val, node.l)
        else:
            print node.v
            return node
    else:
        if(node.r != None):
            #print node.v
            self.return_key(val, node.r)
        else:
            print node.v
            return node

Printing node.v prints the node value, but when i print the returned node :

print ((tree.return_key(6, tree.getRoot().v)))

it prints

None

as result.

Martijn Pieters · Accepted Answer · 2016-08-26T06:32:19.710

You need to return the result of your recursive call. You are ignoring it here:

if(node.l != None):
    self.return_key(val, node.l)

and

if(node.r != None):
    self.return_key(val, node.r)

Recursive calls are no different from other function calls, you still need to handle the return value if there is one. Use a return statement:

if(node.l != None):
    return self.return_key(val, node.l)

# ...

if(node.r != None):
    return self.return_key(val, node.r)

Note that since None is a singleton value, you can and should use is not None here to test for the absence:

if node.l is not None:
    return self.return_key(val, node.l)

# ...

if node.r is not None:
    return self.return_key(val, node.r)

I suspect you are passing in the wrong arguments to the call to begin with however; if the second argument is to be a node, don't pass in the node value:

print(tree.return_key(6, tree.getRoot())) # drop the .v

Also, if all your node classes have the same method, you could recurse to that rather than using self.return_value(); on the Tree just do:

print tree.return_key(6)

where Tree.return_key() delegates to the root node:

def return_key(self, val):
    root = tree.getRoot()
    if root is not None:
        return tree.getRoot().return_key(val)

and Node.return_key() becomes:

def return_key(self, val):
    if val < self.v:
        if self.l is not None:
            return self.l.return_key(val)
    elif val > self.v:
        if self.r is not None:
            return self.r.return_key(val)

    # val == self.v or child node is None
    return self

I updated the val testing logic here too; if val < self.v (or val < node.v in your code) is false, don't assume that val > self.v is true; val could be equal instead.

I don't think adding a return statement there will do any good. Since every time the recursion ends it'll reach the else statement which already has a return function. That being said i did try adding the return statement. It still returns None — Utsav Shrestha, Aug 26 '16 at 06:29
@Utsav: You have other errors too, I've updated my answer to address those. — Martijn Pieters, Aug 26 '16 at 06:32
I actually have two separate classes for Node and Tree. Here's my code for the tree implemention http://pastebin.com/wD17VdY6 — Utsav Shrestha, Aug 26 '16 at 06:38
@Utsav: right, so you have the option to implement separate `Tree.return_key()` and `Node.return_key()` methods. The same applies to `Tree.add()` and `Tree.printTree()`; these also recurse but could delegate the per-node recursion to `Node.*` methods instead. — Martijn Pieters, Aug 26 '16 at 06:52
@Utsav: Your `Tree._printTree` method could be implemented as a `Node.printNode()` method instead, so all `Tree.printTree()` has to do is call `self.root.printNode()`. — Martijn Pieters, Aug 26 '16 at 07:23

How to return value from recursive function in python?

1 Answers1