How to overcome maximum recursion depth exceeded error here?

Question

The problem statement is as follows:

Return the sum of the numbers in the array, except ignore sections of numbers starting with a 6 and extending to the next 7 (every 6 will be followed by at least one 7). Return 0 for no numbers.

sum67([1, 2, 2]) → 5
sum67([1, 2, 2, 6, 99, 99, 7]) → 5
sum67([1, 1, 6, 7, 2]) → 4

I'm aware of the same problem being posted here on stack overflow but I don't want to request a new solution, rather I want to know what might be the problems with my own recursive solution to the problem.

My attempt:

def sum67(nums):
  def rem67(nums):
    if 6 not in nums:
      return nums
    index6 = nums.index(6)
    index7 = nums.index(7)
    nums = nums[:index6] + nums[(index7 + 1):]
    return rem67(nums)
  return sum(rem67(nums))

The server keeps throwing maximum recursion depth exceeded error which I'm unable to rectify on the server. Any leads will be appreciated.

Your `rem67` will break if the first `7` comes before the first `6`. — 0x5453, Jul 02 '21 at 12:56

Sefan · Answer 1 · 2021-07-02T13:09:51.957

2

The recursion limit is 1000 by default. You could use a while true instead, like:

def sum67(nums):
    while True:
        if 6 not in nums:
            break
        index6 = nums.index(6)
        index7 = nums.index(7)
        nums = nums[:index6] + nums[(index7 + 1):]
    return sum(nums)

Like 0x5453 commented, it breaks if you have a 7 before a 6. So you probably want to add something like this:

if index6 > index7:
    return -1

edited Jul 02 '21 at 13:09

answered Jul 02 '21 at 13:01

Sefan

699
1
8
23

1

while True doesn't work as it is like you've shown but I figured out a way around it. Thank you – iamakhilverma Jul 02 '21 at 14:03

Pippet39 · Answer 2 · 2021-07-02T13:51:01.997

If a 7 occurs in the array before its 6 counterpart, then on one iteration the new array formed in rem67() will be composed of a section with a 7 but no 6, followed by a section with a 6. This sets up the same condition in the new array, which will result in infinite recursion.

If it is allowed that two consecutive 7's may occur, or for a 7 to occur first, then it would be better to do the following:

index7 = nums.index(7, index6)

This makes index7 reference the first 7 that follows the 6, thus ignoring any 7's that may occur before the 6.

Otherwise returning an error code as suggested by Sefan is good.

Hope this fixes things :)

score 0 · Answer 3 · answered Jul 02 '21 at 13:07

0

This isn't a safe mode:

import sys

my_limit = sys.getrecursionlimit()
sys.setrecursionlimit(my_limit + 200)
print(sys.getrecursionlimit())

answered Jul 02 '21 at 13:07

Alexandre Simões

1
2

score 0 · Accepted Answer · answered Jul 02 '21 at 14:48

As per @0x5453 's comment, I modified the index7 which now looks for only those 7 which come after we encounter 6.

Here's the modified code which works correctly:

def sum67(nums):
  def rem67(nums):
    if 6 not in nums:
      return nums
    index6 = nums.index(6)
    index7 = nums[index6:].index(7) + index6
    nums = nums[:index6] + nums[(index7 + 1):]
    return rem67(nums)
  return sum(rem67(nums))

How to overcome maximum recursion depth exceeded error here?

4 Answers4