CODEWITHSUNDEEP
pythonrecursionpass-by-referencevariable-assignment
lexie
lexie

Reputation: 77

Why does assignment to outer variables not take effect in recursive algorithm?

I am trying to solve a interview question: how to convert a BST to a double linked list. Below is my code. I am really confused about how python recursion works. Why after the convert2DoubleLst_recursive , the prev and head remain to be None, I have assigned a new value to these two variables, why after this method call, I cannot save the change. I remembered that python pass arguments by reference, but why here I cannot save the changes. Many thanks in advance.

def convert2_recursive(node):
    prev,head=None,None
    convert2DoubleLst_recursive(node,prev,head)
    end=head.lChild
    printList(head,end)

def convert2DoubleLst_recursive(node,prev,head):
    if node:
        convert2DoubleLst_recursive(node.lChild,prev,head)
        node.lChild=prev
        if prev:
           prev.rChild=node
        else:
           head=node
        nextNode=node.rChild
        head.lChild=node
        node.rChild=head
        prev=node
        convert2DoubleLst_recursive(nextNode,prev,head)

Upvotes: 1

Views: 382

Answers (2)

bterwijn
bterwijn

Reputation: 328

Nice problem, I couldn't resist. I've split my solution in 2 parts and have used package memory_graph to visualize my approach:

import memory_graph as mg # see above link for install instructions

class Node:

    def __init__(self, value, lChild=None, rChild=None):
        self.lChild = lChild
        self.value = value
        self.rChild = rChild

    def __repr__(self):
        return str(self.value)

def print_bst(current):
    if current:
        print_bst(current.lChild)
        print(current.value)
        print_bst(current.rChild)

def get_nodes_in_order(order, current):
    if current:
        get_nodes_in_order(order, current.lChild)
        order.append(current)
        get_nodes_in_order(order, current.rChild)

def transform_to_list(order):
    current = order[0]
    for i in range(1, len(order)):
        current.rChild = order[i]
        order[i].lChild = current
        current = order[i]
    return order[0]

def print_list(current):
    while current:
        print(current.value)
        current = current.rChild

# To setup we first build a binary search tree
bst_head = Node(11, Node(10), Node(13, Node(12), Node(14)))
print_bst(bst_head)
mg.render(mg.get_call_stack(), "setup_bst.png")

# Step1: get the BST nodes in sorted order
order = []
get_nodes_in_order(order, bst_head)
print('order:', order)
mg.render(mg.get_call_stack(), "get_nodes_in_order.png")

# Step2: loop over 'order' and transform each node to double linked list
list_head = transform_to_list(order)
bst_head = None # not valid anymore
order = None # not needed anymore
print_list(list_head)
mg.render(mg.get_call_stack(), "transform_to_list.png")

To setup we first build a binary search tree (BST):

setup_bst.png

Step1: get the BST nodes in sorted order:

get_nodes_in_order.png

Step2: loop over order and transform each node to double linked list:

transform_to_list.png

It may be possible to do it all in 1 step, but this 2 step solution is much simpler and simpler solutions are generally preferred, unless performance or memory usage are of the upmost importance.

The recursion in the get_nodes_in_order() function is now easier to understand. It is clear that order is changed after calling this function showing that Python uses pass by reference (each Python variable is a reference to a value). But only values of mutable types can be changed in this way and in Python a reassignment is not a change of a value (like it is in C/C++ using pointers). I recommend using memory_graph to more easily get an understanding of the Python Data Model.

Full disclosure: I am the developer of memory_graph.

Upvotes: -1

user3850
user3850

Reputation:

Naively put, because there is no pass-by-reference in Python. Recursion is not your problem.

It may become a little clearer, when you think "There are no variables in Python, only names and values".

When the statement convert2DoubleLst_recursive(node.lChild, prev, head) is executed, actually the function convert2DoubleLst_recursive is called with the values that node.lChild, prev and head point to at that time.

Then, within convert2DoubleLst_recursive, those values are given the (local) names node, etc. (which are different names from those before!).

Later you assign new values to those names, recurse (which is not actually relevant in your code) and essentially Python forgets the names and their values when exiting the function.

Basically, between line 8 and 10 prev does not change it's value (as you experienced), because the name used in the caller is never seen inside of the callee. The value assigned to that name is not changed in line 3 and it is not relevant what happens inside the callee.

If you want to pass values back to your caller, you have to return them.

Alternatively you could replace None by a guardian object that behaves like your node class and represents None.

Usually, though, there are better data structures you would use in Python than linked lists. (Python lists for example are already linked lists internally and can be used instead.)

A much deeper analysis can be found here: https://stackoverflow.com/a/986145/110707 .

Upvotes: 1

Related Questions