Break recursion the right way

Question

Trying to solve Leetcode problem 55. Jump Game; i decided to break recursion with a try except block and custom Exception, do you see a more clever way of doing it ? I feel like I am doing the wrong way to break recursion ...

class Solution(object):
    def canJump(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        reachable = [False]*len(nums)
        class BreackRecursion(Exception):
            pass
        def jump(nums,pos):
            max_step = nums[pos]
            reachable[pos]=True
            if reachable[-1]==True:
                raise BreackRecursion
            for step in range(1,max_step+1):
                print(pos,step,max_step,list(range(1,max_step+1)),reachable)
                try:
                    reachable[pos+step]=True
                    jump(nums,pos+step)
                except IndexError:
                    pass
                
        try:       
            jump(nums,0)
        except BreackRecursion:
            return True
        return False



S= Solution()
inputs =[[2,3,1,1,4],[3,2,1,0,4]]
for input in inputs:
    print("input:",input)
    s = S.canJump(input)
    print(s)

Answer 1

Here is a proposal

class SolutionNew:
    def canJump(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        def jump(nums, pos):
            max_step = nums[pos]

            # 1 -- you are just breaking when reaching last position
            if pos == len(nums) - 1:
                # 2 -- just use a flag to end your recursion
                return False

            for step in range(1, max_step + 1):
                print(pos, step, max_step, list(range(1, max_step + 1)))

                # 3 -- an "if" statement may be more elegant here
                next_pos = pos + step
                if next_pos < len(nums):
                    # 4 -- propagate your "False" flag
                    if not jump(nums, next_pos):
                        return False

            # 5 -- when normal ending, you just flag that a new loop can be performed
            return True

        # 6 -- ensure the logic is ok
        return not jump(nums, 0)

1. Setting reachable[pos] to True and then checking for last value of reachable is just like looking if pos == len(reachable)-1 (or len(nums)-1 since len(reachable) == len(nums).
2. Instead of raising an Exception, you could just set a flag. Then you should just take care of propagating that flag, through #4 (you want to stop immediately if False flag is returned) and #5 (normal ending -> proceed with next iteration).
3. Instead of try ... except you can just see if next_pos fits in. Notice also that reachable[pos + step] = True before calling jump(nums, pos + step) was reduntant, since the jump call sets it to True almost immediately. At this point, indeed, you do not even need reachable anymore.
4. See #2.
5. See #2.
6. Just to adjust the logic, in order to return True when recursion stops (i.e. BreackRecursion was raised).

Here some test code:

S = Solution()
S_new = SolutionNew()
inputs = [
    [2, 3, 1, 1, 4],
    [3, 2, 1, 0, 4],
    [5, 1, 6, 10, 2, 3, 4, 7, 5, 2],
    [123, 321, 25, 87, 6],
    [5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5],
]
for input in inputs:
    print("input:", input)
    s = S.canJump(input)
    s_new = S_new.canJump(input)
    assert s == s_new, 'Solutions are different!'
    print(s_new)