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

Question

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)

• BartoszKP: Please fix your indentation - this code, as it is, won't compile.
• Wooble: "I remembered that python pass arguments by reference" You remembered incorrectly. (I recommend reading stackoverflow.com/a/986145/110707 )
• tobias_k: I guess you could emulate pass by reference like behaviour by passing the two parameters wrapped in a list or dictionary. But you shouldn't.
• kindall: Python is pass-by-value, where all values are references to objects. There's no way to change what object someone else's variable points to.

Answer 1

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 .