CODEWITHSUNDEEP
python
JayRoar
JayRoar

Reputation: 61

Printing out prime numbers till N using recursion

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.

Upvotes: 2

Views: 869

Answers (2)

6502
6502

Reputation: 114559

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.

Upvotes: 0

jonrsharpe
jonrsharpe

Reputation: 122090

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.

Upvotes: 1

Related Questions