CODEWITHSUNDEEP
pythonpython-3.xalgorithmrecursion
Mudits
Mudits

Reputation: 1633

Reaching Recursion depth in python for following code

I have following code to calculate the frequency of a sorted list recursively. I don't understand why there are so many recursive calls happening in this to be precise (997). What am I doing wrong over here.

def frequency_util(A, low, high, freq):
    if A[low] == A[high]:
        freq[A[low]] += high-low+1
    else:
        mid = (low+high)//2
        frequency_util(A, low, mid, freq)
        frequency_util(A, mid, high, freq)

def frequency(A):
    freq = [0]*A[len(A)-1]
    frequency_util(A, 0, len(A)-1, freq)

    return freq


if __name__ == '__main__':
    print(frequency([1, 1, 1, 2, 3, 3, 5, 5]))

Upvotes: 3

Views: 51

Answers (1)

carrdelling
carrdelling

Reputation: 1725

You have an infinite recursion there.

The problem happens at several points, when you have a subproblem of size 2 with different values in each position (e.g. A[3:4] ---> [2,3]). In that case, you code is always spawning 2 additional calls to frequency_util, and one of them will still include the array with size 2 anyway (A[3:4] --> A[3:3], A[3:4])

You can start fixing it by adding an additional stopping condition:

if high - low == 1:
    freq[A[low]] += 1
    freq[A[high]] += 1

Also, note that there are more bugs in your code:

  • You are defining a 0-indexed array to store the counts, but when updating them you are considering 1-indexing instead.
  • mid should be computed like this: mid = (low+high)//2
  • Since both low and high are counted, your second call to frequency_util should include only (mid+1, high)

Here's an example of a valid solution:

def frequency_util(A, low, high, freq):
    if A[low] == A[high]:
        freq[A[low]] += high-low+1
    elif high - low == 1:
        freq[A[low]] += 1
        freq[A[high]] += 1
    else:
        mid = (low+high)//2
        frequency_util(A, low, mid, freq)
        frequency_util(A, mid+1, high, freq)

def frequency(A):
    freq = [0] * (A[len(A)-1] + 1)
    frequency_util(A, 0, len(A)-1, freq)

    return freq


if __name__ == '__main__':
    print(frequency([1, 1, 1, 2, 3, 3, 5, 5]))

Which gives as output:

[0, 3, 1, 2, 0, 2]

Upvotes: 3

Related Questions