How can I make this Python recursive function return a flat list?
Look at this simple function
def prime_factors(n): for i in range(2,n): if n % i == 0: return i, prime_factors(n / i) return n
Here's the result of prime_factors(120)
(2, (2, (2, (3, 5))))
Instead of nested tuples, I want it to return one flat tuple or list.
(2, 2, 2, 3, 5)
Is there a simple way to do that?
def prime_factors(n): for i in range(2,n): if n % i == 0: return [i] + prime_factors(n / i) return [n]
def prime_factors(n): for i in range(2,n): if n % i == 0: yield i for p in prime_factors(n / i): yield p return yield n
>>> tuple(prime_factors(100)) (2, 2, 5, 5)
Without changing the original function, from Python Tricks:
def flatten(x): """flatten(sequence) -> list Returns a single, flat list which contains all elements retrieved from the sequence and all recursively contained sub-sequences (iterables). Examples: >>> [1, 2, [3,4], (5,6)] [1, 2, [3, 4], (5, 6)] >>> flatten([[[1,2,3], (42,None)], [4,5], , 7, MyVector(8,9,10)]) [1, 2, 3, 42, None, 4, 5, 6, 7, 8, 9, 10]""" result =  for el in x: #if isinstance(el, (list, tuple)): if hasattr(el, "__iter__") and not isinstance(el, basestring): result.extend(flatten(el)) else: result.append(el) return result
liw.fi suggested in a comment:
Instead of creating a new list for each return value, you could pass the list as an argument and append to it. If the list gets large, this may save some space and time.
Here's an implementation of liw.fi's suggestion.
def prime_factors(n, factors=None): if factors is None: factors =  for i in range(2,n): if n % i == 0: factors.append(i) return prime_factors(n / i, factors) factors.append(n) return factors
I don't know how relevant this is, but this function can help you flatten out deep nested lists (uses recursion), and can just as well be applied to the problem at hand. Though, it is using a hose to water a daisy
def flatten(S): if S == : return S if isinstance(S, list): return flatten(S) + flatten(S[1:]) return S[:1] + flatten(S[1:])