Printing out prime numbers till N using recursion

Question

L=[]

def Prime(N):
    a=0
    for i in range(2,N):
        if N%i==0:
            a+=1
        if a>0:
            return False
        else:
            return True

def PrimesList(N):
    if N==2:
        L.append(2)
    elif Prime(N):
        L.append(N)
        return PrimesList(N-1)
    else:
        return PrimesList(N-1)

L.reverse() 
print L

If I use it one time, it gives the correct answer. But L is being saved in global environment. How can I bring it inside loop when using recursion? The question might be basic for most of you but I am new to Python. I am supposed to print the prime numbers till N.

Your code as written won't run --- e.g, the a=0 on line 5 needs to be indented. — Rory Yorke, Sep 27 '15 at 08:25
Why do you want to use recursion? Just use a simple loop. BTW, your `Prime` function can be made more efficient. It's hard to know exactly what you're trying to do, due to the indentation errors, but 1) it only needs to test until it finds the first factor of n; and 2) if a number n isn't prime then it must have a factor <= sqrt(n). — PM 2Ring, Sep 27 '15 at 08:26
Also, please fix your indentation. The usual Python convention is to use 4 spaces per indentation level. — PM 2Ring, Sep 27 '15 at 08:27

score 1 · Answer 1 · edited May 23 '17 at 11:44

1

I would do it as a second parameter, using None to avoid this common issue:

def PrimesList(N, L=None):
    if L is None:
        L = []
    ...

Then just include L in the recursive call and make sure you return L from the end of he recursion.

edited May 23 '17 at 11:44

Community

1
1

answered Sep 27 '15 at 08:26

jonrsharpe

115,751
26
228
437

score 0 · Answer 2 · answered Sep 27 '15 at 08:34

To print the first N prime numbers you can just print the first N-1 prime numbers and add next prime. However to compute next prime the list of numbers is also useful so in addition to print it just return the list:

def printFirstPrimes(N):
    if N == 1:
        result = [2]
    else:
        result = printFirstPrimes(N-1)
        # ... compute next prime here ...
        result.append(next_prime)
    print result
    return result

Note that this is not the best approach with Python, deep recursion is not very efficient and tail call optimization is not implemented in the reference implementation CPython.

Printing out prime numbers till N using recursion

2 Answers2