CODEWITHSUNDEEP
pythonrecursiontree
Arslan Siddiqui
Arslan Siddiqui

Reputation: 3

Why does this code behave like tail recursion

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?

Upvotes: 0

Views: 76

Answers (3)

apoclyps
apoclyps

Reputation: 521

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.

Upvotes: 0

slothropbodine
slothropbodine

Reputation: 78

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"

Upvotes: 3

Prune
Prune

Reputation: 77847

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.

Upvotes: 2

Related Questions