CODEWITHSUNDEEP
pythonrecursionfactors
Josh
Josh

Reputation: 63

Factors of a number using Python recursive function

I've got an assignment which requires me to use a Python recursive function to output the factors of a user inputted number in the form of below:

Enter an integer: 6 <-- user input
The factors of 6 are:
1
2
3
6

I feel like a bit lost now and have tried doing everything myself for the past 2 hours but simply cannot get there. I'd rather be pushed in the right direction if possible than shown where my code needs to be changed as I'd like to learn

Below is my code:

def NumFactors(x):
  for i in range(1, x + 1):
    if x == 1:
        return 1
    if x % i == 0:
        return i
    return NumFactors(x-1)


x = int(input('Enter an integer: '))

print('The factors of', x, 'are: ', NumFactors(x))

Upvotes: 2

Views: 2244

Answers (3)

Nebraska
Nebraska

Reputation: 11

Since this question is almost 3 years old, I'll just give the answer rather than the requested push in the right direction:

    def factors (x,c=1):
        if c == x: return x
        else:
            if x%c == 0: print(c)
            return factors(x,c+1)

Upvotes: 1

Abhijith Mahadevan
Abhijith Mahadevan

Reputation: 26

In your code the problem is the for loop inside the method. The loop starts from one and goes to the first if condition and everything terminates there. That is why it only prints 1 as the output this is a slightly modified version of your own code. This should help. If you have any queries feel free to ask.

def factors(x):
    if x == 1:
        print(1 ,end =" ")
    elif num % x == 0:
        factors(x-1)
        print(x, end =" ")
    else:
        factors(x-1)

x = num = int(input('Enter an integer: '))

print('The factors of', x, 'are: ',end =" ")
factors(x)

Upvotes: 1

Alain T.
Alain T.

Reputation: 42143

Your recursion is passing down x-1 which will not give you the right value. For example: the number of factors in 6 cannot be obtained from the number of factors in 5.

I'm assuming that you are not looking for the number of prime factors but only the factors that correspond to the multiplication of two numbers.

This would not normally require recursion so you can decide on any F(n) = F(n-1) pattern. For example, you could use the current factor as a starting point for finding the next one:

def NumFactors(N,F=1):
    count = 1 if N%F == 0 else 0
    if F == N : return count
    return count + NumFactors(N,F+1)

You could also optimize this to count two factors at a time up to the square root of N and greatly reduce the number of recursions:

def NumFactors(N,F=1):
    count = 1 if N%F == 0 else 0
    if N != F : count = count * 2
    if F*F >= N : return count
    return count + NumFactors(N,F+1)

Upvotes: 0

Related Questions