Python RuntimeError: maximum recursion depth exceeded

Question

I am new about Python. I wrote a function about returns the number of occurences of x in the sorted repeated elements array A:

def FindFirstIndex(A, low, high, x, n):
   low = 0
   high = len(A) - 1
   if low <= high:
      mid = low + (high - low) / 2
      if (mid == 0 or x > A[mid - 1]) and A[mid] == x:
          return mid
      elif x > A[mid]:
          return FindFirstIndex(A, (mid + 1), high, x, n)
      else:
          return FindFirstIndex(A, low, (mid - 1), x, n)        
   return -1


def FindLastIndex(A, low, high, x, n):
   low = 0
   high = len(A) - 1
   if low <= high:
       mid = low + (high - low) / 2
       if (mid == n - 1 or x < A[mid + 1]) and A[mid] == x:
          return mid
       elif x < A[mid]:
          return FindFirstIndex(A, low, (mid - 1), x, n)
       else:
          return FindFirstIndex(A, (mid + 1), high, x, n)           
   return -1

def COUNT(A, x):
   i = FindFirstIndex(A, 0, len(A) - 1, x, len(A))
   if i == -1:
      return i
   j = FindLastIndex(A, i, len(A) - 1, x, len(A))
   length = j - i + 1
   return length

The error is: RuntimeError: maximum recursion depth exceeded. Anybody knows how to solve it?

in fuction `FindFirstIndex` please provide a `elif` condition what you have to check.Otherwise it is repeating every time if above two `if` conditions are false — itzMEonTV, Feb 15 '15 at 06:00
Hey @MohitBhasi man you are referring to the same question , kindly edit your comment .Thanks — ZdaR, Feb 15 '15 at 06:04
Check your `FindFirstIndex`. `low=0` `high=len(A) - 1`. `if low<=high` from else condition `else: return FindFirstIndex(A, low, (mid - 1), x, n)`, Here now check, `low,high` is always fixed if your else condiion satisfies.So it is recursively repeating.Thats the error. You are changing `mid` to `mid-1` in recursive function.But it is not checking anywhere.Also you defined `mid` as a value from `low` and `high` which never changing if above condition satisfies — itzMEonTV, Feb 15 '15 at 06:53

score 0 · Answer 1 · answered Feb 15 '15 at 06:57

A recursive fuction should check arguments in every recursion.Also must change the values of arguments.Otherwise it never ends.For example

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)

Which provides factorial of n

score 0 · Answer 2 · answered Jul 14 '17 at 20:58

sure you can use:

import sys
sys.setrecursionlimit(3000)

I believe Python's default is 1000 so this should do. I caution you though if you try and test your implementation on a very large list python might crash so I would encourage you to re-implement your code iteratively

Python RuntimeError: maximum recursion depth exceeded

2 Answers2

Linked