Recursive Sieve of Erasthotenes returning None

Question

I implemented a recursive Sieve of Erasthotenes, which, from the debug statements used, appears to work, but returns None.

The code with the debug statements looks like this:

def sieb2 (iterable, container):
    print("Just called:", iterable, container, '\n')
    if len(iterable) != 1:
        container.append(iterable [0])
        iterable = [item for item in iterable if item % iterable [0] != 0]
        print("New call:", iterable, container, '\n')
        sieb2(iterable, container)
    else: 
        container.append(iterable[0])
        print("Return:", iterable, container, '\n')
        print("Container:", container)
        return container

The function is (for instance) called with:

lst = list(range(2, 10) # I might add statements for removing everything <2 and sorting
primes = []

print(sieb2(lst, primes))

The output for this input looks like this:

# Debug-Statements from the function:
Just called: [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] [] 

New call: [3, 5, 7, 9, 11, 13, 15, 17, 19] [2] 

Just called: [3, 5, 7, 9, 11, 13, 15, 17, 19] [2] 

New call: [5, 7, 11, 13, 17, 19] [2, 3] 

Just called: [5, 7, 11, 13, 17, 19] [2, 3] 

New call: [7, 11, 13, 17, 19] [2, 3, 5] 

Just called: [7, 11, 13, 17, 19] [2, 3, 5] 

New call: [11, 13, 17, 19] [2, 3, 5, 7] 

Just called: [11, 13, 17, 19] [2, 3, 5, 7] 

New call: [13, 17, 19] [2, 3, 5, 7, 11] 

Just called: [13, 17, 19] [2, 3, 5, 7, 11] 

New call: [17, 19] [2, 3, 5, 7, 11, 13] 

Just called: [17, 19] [2, 3, 5, 7, 11, 13] 

Mew call: [19] [2, 3, 5, 7, 11, 13, 17] 

Just called: [19] [2, 3, 5, 7, 11, 13, 17] 

Return: [19] [2, 3, 5, 7, 11, 13, 17, 19] 

Container: [2, 3, 5, 7, 11, 13, 17, 19]

# Printed return:

None

From what I can see the function works as it should and goes into the else-statement with the return, the print-statement is executed properly too and outputs the final container.

Why does the return-statement output a NoneType and not the container list?

@MisterMiyagi Sorry, I couldn't find that post initially. Should I leave it or should I delete the question? — E. Staikov, May 04 '19 at 11:32
@MisterMiyagi Would the question be OK if I were to ask wether this implementation is efficient too? Or should I ask a new question for that? — E. Staikov, May 04 '19 at 11:39
@E.Staikov Yes, you should make a new question for that, **but** you should post it on: https://codereview.stackexchange.com/, since it's off-topic here. — ruohola, May 04 '19 at 11:40

ruohola · Accepted Answer · 2019-05-04T11:36:39.043

1

You're just missing one return statement from your recursive function:

def sieb2(iterable, container):
    print("Just called:", iterable, container, '\n')
    if len(iterable) != 1:
        container.append(iterable[0])
        iterable = [item for item in iterable if item % iterable[0] != 0]
        print("New call:", iterable, container, '\n')
        return sieb2(iterable, container)  # FIXED
    else: 
        container.append(iterable[0])
        print("Return:", iterable, container, '\n')
        print("Container:", container)
        return container

Always remember to return the functions which you're calling recursively so that their values get correctly returned to the stack.

edited May 04 '19 at 11:36

answered May 04 '19 at 11:23

ruohola

21,987
6
62
97

Thanks, this worked, but I'm still not sure why my implementation didn't work... It went into the else-statement with the full container but still returned the NoneType, why is that? – E. Staikov May 04 '19 at 11:27
@E.Staikov You will not get the values from the deeper `sieb2` calls returned to the original call of the function without returning the recursive call. It's a common mistake when practicing recursion and will become second nature with time. – ruohola May 04 '19 at 11:28
Thanks, I'll accept the answer when it's possible (5 mins is the minimum). Now I'm wondering wether this implementation of the sieve is efficient, should I change something else? Is there something better than ```filter``` in this situation? – E. Staikov May 04 '19 at 11:33
@E.Staikov I'm not too sure, I'm not really familiar with this algorithm. You're not using `filter` here anyways? – ruohola May 04 '19 at 11:38

score 0 · Answer 2 · answered May 04 '19 at 11:24

def sieb2 (iterable, container):
    print("Just called:", iterable, container, '\n')
    if len(iterable) != 1:
        container.append(iterable [0])
        iterable = [item for item in iterable if item % iterable [0] != 0]
        print("New call:", iterable, container, '\n')

        # Added return
        return sieb2(iterable, container)
    else: 
        container.append(iterable[0])
        print("Return:", iterable, container, '\n')
        print("Container:", container)
        return container

lst = list(range(2, 10)) # I might add statements for removing everything <2 and sorting
primes = []

r = sieb2(lst, primes)
print('r ', r)

Updated content:
return sieb2(iterable, container)

Recursive Sieve of Erasthotenes returning None

2 Answers2