CODEWITHSUNDEEP
pythonrecursion
dessigma
dessigma

Reputation: 29

How to retain value in recursion

def numb_fact(number): 
    factor_list = []
    for d in range(2, number+1, 1):
        if number % d == 0:
            factor_list.append(d)
        else:
            pass
    return factor_list
def factorize(number):

    allfact_list = numb_fact(number)
    final_list = []
    if len(allfact_list) > 0:
        d = allfact_list[0]
        if number % d == 0:
            final_list.append(d)
            divided_numb = int(number / d)
            factorize(divided_numb)
        else:
            if len(allfact_list) > 1:
                allfact_list.remove(d)
            else:
                return final_list
        print(final_list)
    return final_list

factorize(12)

Sample output
[3]
[2]
[2]

So I'm writing a code to displays a number in multiples of prime numbers. In order to do so, I wanted to start off from making a function that gives me 'list of numbers' that if all the numbers in list were multiplied together, it would form original number.

I thought the only way to write this was recursion, leaving my efficiency of code aside for now - because I know it looks terrible) - this function that I wrote does not retain values in factor_list. (well obviously! since I'm restarting the code, and its initially defined as '= []') So I've been wondering for hours if there is a way to work this out in a single function.

Upvotes: 0

Views: 3038

Answers (2)

hsnsd
hsnsd

Reputation: 1823

I dont know why you are first generating the factors, and then recursively checking. There is no need for that.

When using recursion, try not to define a variable within recursive function and then returning it. As you mentioned yourself, it gets reset everytime and hence retains only the last value in it.

But here is how you can retain the values in your code:

def numb_fact(number): 
    factor_list = []
    for d in range(2, number+1, 1):
        if number % d == 0:
            factor_list.append(d)
        else:
            pass
    return factor_list
def factorize(number):

    allfact_list = numb_fact(number)
    if len(allfact_list) > 0:
        d = allfact_list[0]
        if number % d == 0:
            divided_numb = int(number / d)
            return [d] + factorize(divided_numb)
    else:
        return []
print(factorize(12))

Here is another short/better recursive solution that i came up with.

def factor(num,div = 2):
    if num != 1:
        if num%div==0:
            return [div] + (factor(num/div,div))
        else:
            return (factor(num,div+1))

    else:
        return []
print(factor(12))

Output : [2, 2, 3]

Upvotes: 2

Mia
Mia

Reputation: 2676

I know I did not answer your question directly. But for your purpose, you do not need to use recursion at all. Simple iteration suffices. 

class PrimeGenerator:
    def __init__(self):
        self.current=2 # 1 is not prime number

    def __iter__(self):
        while True:
            for n in range(2,int(self.current**0.5)+1):
                if self.current%n==0: # checking if it's not prime
                    break
            else:
                yield self.current
            self.current+=1

    def reset(self):
        self.current=1 # because the generator increases by one after it hits yield

def factorize(n):
    generator=PrimeGenerator()
    result=[]
    for prime in generator:
        if n%prime==0:
            result.append(prime)
            n//=prime
            generator.reset()
        if n==1:
            break
    return result

print(factorize(12))

I know there are better algorithms to check for prime number, but unless you are dealing with extremely large number, this implementation is fast enough.

Upvotes: 1

Related Questions