How can I make this Python recursive function return a flat list?

Question

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?

Answer 1

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

Example:

>>> tuple(prime_factors(100))
(2, 2, 5, 5)

Answer 2

def prime_factors(n):
  for i in range(2,n):
    if n % i == 0:
      return [i] + prime_factors(n / i)
  return [n]

Answer 3

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], [6], 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

Answer 4

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