-2

I've been learning about recursion and error handling. I'm having a hard time understanding why my primality test isn't working:

def is_prime4(n):
    """Recursive primality test"""
    try:
        div
    except NameError:
        div = n - 1
    else:
        div = div - 1
    while div >= 2:
        if n % div == 0:
            print 'No, {number} is not prime because it is divisible by {div}.'.format(number = n, div = div)
            return False
        else:
            return is_prime4(n)
    else:
        print 'Yes, {number} is prime indeed.'.format(number = n)
        return 'True'

is_prime4(2)
is_prime4(3)
is_prime4(4)

I believe that the problem is in the try-except-else statement, but I have a difficult time understanding why.

Thank you for your help.

manocormen
  • 747
  • 1
  • 6
  • 17
  • 1
    The main problem is that you have a syntax error in your code. **try: div** is not a legal sequence. You need a command, not an expression. – Prune Feb 12 '16 at 01:34
  • I'm not sure I understand. The `try` is there to test `div` existence, and initialise it if necessary. As far as I can tell, [that part is working](http://stackoverflow.com/questions/843277/how-do-i-check-if-a-variable-exists-in-python). – manocormen Feb 12 '16 at 01:42
  • What Python version are you using? I'm on 2.7, and it fails at the start. Perhaps you have something more advanced; I haven't seen this usage before, so I appreciate the link you gave. – Prune Feb 12 '16 at 01:44
  • Also, is there some particular reason for using this exception syntax? Exceptions in most languages, Python included, are *really* slow. – Prune Feb 12 '16 at 01:46
  • 2.7.3. I do have a return. The problem I face is exceeding the maximum recursion depth. edit: no, no reason, just trying different approaches to a same problem and trying to learn something in the process :) – manocormen Feb 12 '16 at 01:49
  • 1
    Primality testing isn't something that lends itself to a recursive solution. All you are doing is inefficiently implementing a loop. – chepner Feb 12 '16 at 02:55

3 Answers3

2

The recursion depth problem is because div is new with each local context. It is not a global variable. Every time you enter the routine, you get a new context, including a new set of local variables. Thus, if you have n = 7, every call sets div = 6. You never change that, so you go into infinite recursion.

You need to adopt a cleaner solution, such as those suggested by the other posters.

Here is your code, using a global div. Note that you have to reset it after every completion ... somehow ... and it's ugly ...

div = -1

def is_prime4(n):
    """Recursive primality test"""
    global div
    if div < 0:
        div = n - 1
    else:
        div = div - 1

    while div >= 2:
        if n % div == 0:
            print 'No, {number} is not prime because it is divisible by {div}.'.format(number = n, div = div)
            div = -1
            return False
        else:
            return is_prime4(n)
    else:
        print 'Yes, {number} is prime indeed.'.format(number = n)
        div = -1
        return True

    for i in range(20):
        is_prime4(i)

Output:

Yes, 0 is prime indeed.
Yes, 1 is prime indeed.
Yes, 2 is prime indeed.
Yes, 3 is prime indeed.
No, 4 is not prime because it is divisible by 2.
Yes, 5 is prime indeed.
No, 6 is not prime because it is divisible by 3.
Yes, 7 is prime indeed.
No, 8 is not prime because it is divisible by 4.
No, 9 is not prime because it is divisible by 3.
No, 10 is not prime because it is divisible by 5.
Yes, 11 is prime indeed.
No, 12 is not prime because it is divisible by 6.
Yes, 13 is prime indeed.
No, 14 is not prime because it is divisible by 7.
No, 15 is not prime because it is divisible by 5.
No, 16 is not prime because it is divisible by 8.
Yes, 17 is prime indeed.
No, 18 is not prime because it is divisible by 9.
Yes, 19 is prime indeed.
President James K. Polk
  • 40,516
  • 21
  • 95
  • 125
Prune
  • 76,765
  • 14
  • 60
  • 81
  • Thank you. Now I understand. I already had 3 working version of the primality test before asking this question. My objective was exploring of the possibility of doing it this way, with a try-except-else and only one function argument. – manocormen Feb 12 '16 at 02:04
  • Aha! Okay. How about making **div** a global, but initialize it externally to -1 to indicate "unused"? I *suspect* that violates what you're trying to do. – Prune Feb 12 '16 at 02:10
  • I'd rather not use globals, but admittedly, this is something I've also tried and couldn't get it to work. Every value was returned as being prime... – manocormen Feb 12 '16 at 02:19
  • You have an information problem, then: your repeated steps require the "candidate prime" as well as the dividend to test. These are two distinct parameters that every iteration requires; you *must* supply that information in some fashion. As best I can see, the only way to reduce this to a single parameter is to pack the two data into a single object somehow. For instance, pass a 2-tuple. I know, this is bandying semantics, rather than solving the problem of elegance. I believe that the recursion inherently breaks the continuity required for elegance. – Prune Feb 15 '16 at 17:42
1

Consider the example below. I believe I have simplified your logic some.

def recursive_prime(n,divisor=2):
    if n == divisor : return True
    elif (n % divisor) == 0: return False
    return recursive_prime(n,divisor+1)

for i in range(2,10):
    print i,'is prime',recursive_prime(i)
goCards
  • 1,388
  • 9
  • 10
1

You are basically trying to do a while loop and calling the function recursivly. It could work but not like this. I would recommend either using a loop or recursion.

Your code had two other downsides as well: Your recursion never ended and if it ended your loop would never end.

One example for a loop (that terminates) would be:

def is_prime4(n):
    """Recursive primality test"""
    div = n # very inefficient because one would only need to start at int(sqrt(n))
    while div > 2:
        div -= 1 # So that the loop terminates in the end.
        if n % div == 0:
            print('No, {number} is not prime because it is divisible by {div}.'.format(number = n, div = div))
            return False
    else:
        print('Yes, {number} is prime indeed.'.format(number = n))
        return True

is_prime4(2)
is_prime4(3)
is_prime4(4)
MSeifert
  • 145,886
  • 38
  • 333
  • 352
  • Thank you, but my objective here was to do it with recursion. I already had a working version of the function with a for loop, and with a while + second argument. I should have made that clearer from the beginning. – manocormen Feb 12 '16 at 02:08
  • Please note that the code is just to emphasize my comments about termination. The same argument applies to recursion. So you want a recursive function that takes only one parameter? – MSeifert Feb 12 '16 at 02:15
  • Exactly. I can do it with 2 parameters, but can't for the live of me do it with one. – manocormen Feb 12 '16 at 02:16
  • There is no way I could think of with only one parameter because you would need to resort to a global variable or the one parameter could be a ``tuple`` or ``list``. That's like cheating yourself: "I only need only one parameter for my function but also one global variabel". :-) – MSeifert Feb 12 '16 at 02:20
  • I have been struggling with this problem for a while, thinking that I was missing an obvious solution, so it's actually comforting to read that it actually isn't that simple. ;) – manocormen Feb 12 '16 at 02:23
  • Then please for your next question: Please state what you actually want to know. We can't read your mind and everyone here has invested some time to help you and explained to you why it didn't work - just to figure out that your question was slightly different, you just forgot to mention it. – MSeifert Feb 12 '16 at 02:42
  • Well, what I actually wanted to know at first was why my try-except-else statement wasn't working, and you completely sidestepped my question in your original reply... But sure, I'll be more carefull next time. I'm still new to this. – manocormen Feb 12 '16 at 02:56