0

I was writing this code to create a binary tree from inorder and postorder traversals and I stumbled on a recursive solution that was confusing, because the program behaved like a tail-recursive call instead of standard recursion.

I've transformed the code into something general so that it's easier for everyone to understand

class Test:
    def func(self, array):      
        if not array:
            return 0
        print(array)
        array.pop(0)
        temp1 = self.func(array)
        temp2 = self.func(array)

x = [1,2,3,4,5,6]
temp = Test()
temp.func(x)

I expect the 2 function calls to have the same output twice. That is the first call should result in [2,3,4,5,6], [3,4,5,6] ... [6]. The second function call should do the same. Instead, the second call results in nothing happening. Shouldn't the recursion stack hold the current state of the array, why is it getting updated?

Arslan Siddiqui
  • 3
  • 1
  • 2
    By the time the second `self.func()` is called, the first one (and its recursive children) has eaten the entire array. – John Gordon Jun 13 '19 at 19:04
  • 2
    The stack doesn't contain a copy of the entire array (i.e. list). It contains a reference to it. There is only one list. Any chance made to it is reflected in all references to it. – Tom Karzes Jun 13 '19 at 19:05

3 Answers3

3

Lists are mutable. In your recursive call you pass the list, in the body of the function you mutate the list. Every call is mutating the list. The recursion stack should not "hold the current state of the array"

slothropbodine
  • 78
  • 4
  • Thanks for the answer. To make a comparison to C++, do recursive calls in python only take objects by reference, or is it only lists? I thought every call would make a copy of the list and then perform the operation – Arslan Siddiqui Jun 13 '19 at 19:14
  • This is a complicated subject, refer to this question: https://stackoverflow.com/questions/986006/how-do-i-pass-a-variable-by-reference – slothropbodine Jun 13 '19 at 19:16
  • 1
    @ArslanSiddiqui it is not that complicated. Nothing in Python ever uses call by reference semantics. Every object is passed "by assignment", which *is neither call by reference* (since assignments to the argument are not seen by the caller) *nor is it call by value* (since data is not copied). The *type* of the object doesn't matter at all. – juanpa.arrivillaga Jun 13 '19 at 19:24
2

array is a list, a mutable object. Thus, func is working on a direct reference to the original, rather than a local copy. Changes made in func are made to that original.

Prune
  • 76,765
  • 14
  • 60
  • 81
0

The reason the second call does not produce any output is because of the recursive call on the line above. The value of the array is [] by the time temp2 is called because lists are mutable in this context.

temp1 = self.func(array) will produce the following output:

>>> temp.func(x)
[1, 2, 3, 4, 5, 6]
[2, 3, 4, 5, 6]
[3, 4, 5, 6]
[4, 5, 6]
[5, 6]
[6]

After this function completes, the list has been mutated and the value of array is now []. You may want to create a deepcopy of your list before performing any mutations on it.

apoclyps
  • 501
  • 5
  • 9