Python – Reach the recursive depth of the following code in python

I have the following code to recursively count the frequency of sorting a list. I don’t understand why so many recursive calls happen, (997) exactly. What am I doing wrong 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]))

There is infinite recursion there.

The problem occurs at several points, and when you have a subproblem of size 2, each location has a different value (e.g. A[3:4] —> [2,3]). In this case, your code always spawns 2 extra calls to frequency_util, one of which will still contain an array of size 2 (

A[3:4] –> A[3:3], A[3:4]).

You can start fixing it by adding an extra stop condition:

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

Also note that there are more errors in your code:

• You are defining a 0-indexed array to store the counts, but you are considering indexing 1-based instead.
• MID should be calculated 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 is an example of an effective 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]))

The output is:

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