TransWikia.com

Is my code correct to find a prime number by means of recursion in python? or is the answer key?

Stack Overflow Asked by Saleh on December 9, 2021

I am studying Python by the book "a beginner guide to python 3" written by Mr.John Hunt. In chapter 8, which is about recursion, there is an exercise, that demands a code in which a prime number is found by recursion. I wrote first code below independently, but the answer key is written in different structure. Because I am very doubtful about recursion, What is your analysis about these two? Which is more recursive?

My code:

def is_prime(n, holder = 1):
    if n == 2:
        return True
    else:
        if (n-1 + holder)%(n-1) == 0:
            return False
        else:
            return is_prime(n-1, holder+1)

print('is_prime(9):', is_prime(9))
print('is_prime(31):', is_prime(31))

Answer key:

def is_prime(n, i=2):
    # Base cases
    if n <= 2:
        return True if (n == 2) else False
    if n % i == 0:
        return False
    if i * i > n:
        return True

    # Check for next divisor
    return is_prime(n, i + 1)

print('is_prime(9):', is_prime(9))
print('is_prime(31):', is_prime(31))

3 Answers

I'd say the Answer Key needs improvement. We can make it faster and handle the base cases more cleanly:

def is_prime(n, i=3):
    # Base cases
    if n < 2:
        return False

    if n % 2 == 0:
        return n == 2

    if i * i > n:
        return True

    if n % i == 0:
        return False

    # Check for next divisor
    return is_prime(n, i + 2)

The original answer key starts at 2 and counts up by 1 -- here we start at 3 and count up by 2.

As far as your answer goes, there's a different flaw to consider. Python's default stack depth is 1,000 frames, and your function fails shortly above input of 1,000. The solution above uses recursion more sparingly and can handle input of up to nearly 4,000,000 before hitting up against Python's default stack limit.

Answered by cdlane on December 9, 2021

My suggestion in this case would be not to use recursion at all. Whilst I understand that you want to use this as a learning example of how to use recursion, it is also important to learn when to use recursion.

Recursion has a maximum allowed depth, because the deeper the recursion, the more items need to be put on the call stack. As such, this is not a good example to use recursion for, because it is easy to reach the maximum in this case. Even the "model" example code suffers from this. The exact maximum recursion depth may be implementation-dependent, but for example, if I try to use it to compute is_prime(1046527) then I get an error:

RecursionError: maximum recursion depth exceeded while calling a Python object

and inserting a print(i) statement shows that it is encountered when i=998.

A simple non-recursive equivalent of the "model" example will not have this problem. (There are more efficient solutions, but this one is trying to stay close to the model solution apart from not using recursion.)

def is_prime(n):
    
    if n == 2:
        return True

    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1

    return True

(In practice you would probably also want to handle n<2 cases.)

If you want a better example of a problem to practise recursive programming, check out the Tower of Hanoi problem. In this case, you will find that using recursion allows you to make a simpler and cleaner solution than is possible without it, while being unlikely to involve exceeding the maximum recursion depth (you are unlikely to need to consider a tower 1000 disks high, because the solution would require a vast number of moves, 2^1000-1 or about 10^301).

As another good example of where recursion can be usefully employed, try using turtle graphics to draw a Koch snowflake.

Answered by alani on December 9, 2021

Yes your example seems to work correctly. Note However, that by the nature of the implementation, the answer key is more efficient. To verify that a number n is a prime number, your algorithm uses a maximum of n-1 function calls, while the provided answer stops after reaching the iteration count of sqrt(n). Checking higher numbers makes generally no sense since if n is dividable without remainder by a value a > sqrt(n) it has to also be dividable by b = n % a.

Furthermore, your code raises an exception for evaluating at n = 1 since the modulo of 0 is not defined.

Answered by Manumerous on December 9, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP