Majority function 'recursion limit exceded' in Python

Question

I am working on a majority function that should count if an element is in a list more than length of the list divided by 2 plus 1: (len(list) // 2 + 1).

Here is my code until now:

def majority(mylist):
    global global_length 
    global_length = len(mylist)
    counter=0   
    if len(mylist)>0:
        for x in mylist:     #counts how many times the first element is in the list
            if x == mylist[0]:
                counter+=1
        eval (mylist,counter)  #eval checks if an element is a majority or not.
    else:
        return ("The list has no majority")


def eval(mylist,counter):  
        if counter>global_length:
            return (mylist[0], "is majority")
        else:
            A1 =[y for y in A if y!=A[0]] #new list w/ non-majority Element
        majority(A1)

I am using #pythontutor to check where the problem is, and the function does give the wanted result at some point, but then does not stop and at the end it gives no output or mistake.

Does anyone see what is going on? I am new in Python and after 2 hours I don't see it.

Answer 1

For auld lang syne, let's review your code issues: first, don't use built-in Python function names for your functions, i.e. let's call eval() something like is_majority(); the is_majority() does the wrong test, comparing counter to global_length instead of global_length // 2 + 1; the is_majority() function should return the result of the majority(A1) call instead of implicitly returning None; similarly, the majority() function should return the result of the call to is_majority() instead of dropping it on the floor; the is_majority() function refers to its list argument by two different names, mylist and A -- should be the same thing.

I believe the answer to your 'recursion limit exceeded' is a combination of the above plus this logic:

def majority(mylist):
    global global_length 
    global_length = len(mylist)

Although you've made global_length global, it's still changing on every recursion so is useless as a test. To make it useful, we'd need to do something like:

global_length = 0

def majority(mylist):
    global global_length
    ...
    if len(mylist) > 0:
        if global_length == 0:
            global_length = len(mylist)

i.e. only set it on the first call but use it on the recursions.

Let's start over. First, let's use the full flavor of Python to define the majority() function to determine a gold standard result. We'll make the function return a tuple, (element, count), or None, and let the caller print this result nicely for the user:

from collections import Counter

def majority(mylist):
    [(element, count)] = Counter(mylist).most_common(1)

    if count > len(mylist) // 2:
        return (element, count)

    return None

test_list = ['A', 'B', 'A', 'C', 'A', 'D', 'A']

result = majority(test_list)

if result:
    element, count = result

    print(element, "is majority")
else:
    print("The list has no majority")

Although we don't use the count portion of the result, it might be of interest to the user and we'll need it in our recursive solution below.

Now that we've defined how this should work, let's return to your implementation. You used an approach with two mutually recursive functions. To simplify things, I'm going to reduce this down to one recursive function that returns results as defined above. I'm also going to eliminate the global variable which always complicates recursion:

def majority(mylist):
    if mylist:
        target = len(mylist) // 2
        element = mylist[0]
        count = 0

        for x in mylist:
            if x == element:
                count += 1

        if count > target:
            return (element, count)

        mysublist = [y for y in mylist if y != element]

        # if element is majority of mylist, must be majority of mysublist
        result = majority(mysublist)

        if result:
            element, count = result

            if count > target:
                return (element, count)

    return None

USAGE

> python3 test.py
A is majority
>