Keep Track Of Global Variable In Recursion

For example if we want to keep track of the max number:

class App:
    maxNumber = 0

    nums = [9, -9, 0, 1, 3]
		#   0,  1, 2, 3, 4
    def traverse(self, index, total):
        if index >= len(self.nums): return total
        self.maxNumber = max(self.maxNumber, 
						     self.traverse(index + 1, total + self.nums[index]),
                             self.traverse(index + 1, total))
        return self.maxNumber

app = App()
app.traverse(0, 0)
print(app.maxNumber)

Which in this case should return 13 because that's the maximum sum that can be created using this array.

Note that if we called like the above (we put the recursion function inside the max()) then we need to return self.maxNumber instead of total.

Why?

Because imagine if we return total. In the subsequent calls the maxNumber is not updated. For example

def traverse(self, index, total):
	if index >= len(self.nums): return total
	self.maxNumber = max(self.maxNumber, 
						 self.traverse(index + 1, total + self.nums[index]),
						 self.traverse(index + 1, total))
	return total # HERE

# at index = 0, we call
max(0, traverse(1, 9), ...)
# at index = 1, we call 
max(0, traverse(2, 9 - 9), ...)
# at index = 2, we call 
max(0, traverse(3, 9 - 9 + 0), ...)
# at index = 3, we call 
max(0, traverse(3, 9 - 9 + 0 + 1), ...)
# at index = 4, we call 
max(0, traverse(3, 9 - 9 + 0 + 1 + 3), ...)
# at index = 5, we return 9 - 9 + 0 + 1 + 3 = 4
return 4

# now back at index = 4 we have 
max(0, 4, traverse(3, 9 - 9 + 0 + 1))
# ok so the maxNumber now is 4, but it will return 
# the current total, which is 9 - 9 + 0 + 1 = 1

# now back at index = 3, we have
max(0, 1, traverse(3, 9 - 9 + 0)) 
# anyways as you can see because maxNumber was not 
# updated and we return `1`. So that the maxNumber now
# becomes `1` -- which it should be `4` instead

Solution

Solution 1. Return maxNumber

The solution for that is if we need to return self.maxNumber instead

def traverse(self, index, total):
	if index >= len(self.nums): return total
	self.maxNumber = max(self.maxNumber, 
						 self.traverse(index + 1, total + self.nums[index]),
						 self.traverse(index + 1, total))
	return self.maxNumber

by doing this, we're actually updating the maxNumber. So that the max call looks like below

max(oldMaxNumber, newMaxNumberIfTakeThisNumber, newMaxNumberIfNotTakeThisNumber)

Soluton 2. Store recursion call inside a variable

or if we want to return total still, we put this into a separate variable

def traverse(self, index, total):
	if index >= len(self.nums): return total
	takeThisNumber = self.traverse(index + 1, total + self.nums[index])
	dontTakeThisNumber = self.traverse(index + 1, total)
	self.maxNumber = max(self.maxNumber, takeThisNumber, dontTakeThisNumber)
	return total

The reason for this is in the subsequent call, self.maxNumber will be updated already. Therefore when we reaches

self.maxNumber = max(self.maxNumber, takeThisNumber, dontTakeThisNumber)

The maxNumber is already updated from the previous call. So for each subsequent call, the function is looking like this:

max(newMaxNumber, totalIfTakeTheNumber, totalIfNotTakeTheNumber)