Drastic efficiency difference when memoizing recursive calls-CodePudding

While doing this LeetCode problem, I noticed that there was a big difference in performance depending on which version I decided to code (see the part that is commented). One of them is more succinct, but I don't see a reason why there should be a difference. An explanation would be greatly appreciated.

class Solution:
    
    def rec_memo(self, nums, index, curr_sum, target, memo):

        if curr_sum == target:
            return True
        elif curr_sum > target or index == len(nums):
            return False
        
        if (index, curr_sum) in memo:
            return memo[(index, curr_sum)]

# This line (below) is significantly more efficient   

#         memo[(index, curr_sum)] = self.rec_memo(nums, index   1, curr_sum   nums[index], target, memo) or self.rec_memo(nums, index   1, curr_sum, target, memo)

# These lines (below) are significantly less efficient

#         choose_num = self.rec_memo(nums, index   1, curr_sum   nums[index], target, memo)
#         not_choose_num = self.rec_memo(nums, index   1, curr_sum, target, memo)
        
#         memo[(index, curr_sum)] = choose_num or not_choose_num
        
        return memo[(index, curr_sum)]
        
        
    def canPartition(self, nums: List[int]) -> bool:
        
        sum = 0
        for i in range(0, len(nums), 1):
            sum  = nums[i]

        if sum % 2 != 0:
            return False
        
        memo = {}
        return self.rec_memo(nums, 0, 0, sum // 2, memo)

CodePudding user response：

The first one:

self.rec_memo(nums, index   1, curr_sum   nums[index], target, memo) or \
self.rec_memo(nums, index   1, curr_sum, target, memo)

won't evaluate the latter call to self.rec_memo() if the first one returns True, due to short-circuit evaluation.

However, with the second one:

choose_num = self.rec_memo(nums, index   1, curr_sum   nums[index], target, memo)
not_choose_num = self.rec_memo(nums, index   1, curr_sum, target, memo)
memo[(index, curr_sum)] = choose_num or not_choose_num

you'll always make the second recursive call, no matter the result of the first call to rec_memo(). The slowdown you're observing is likely the result of these additional recursive calls.