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?

Answers


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

Example:

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

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[0], list):
        return flatten(S[0]) + flatten(S[1:])
    return S[:1] + flatten(S[1:])


Need Your Help

How best to parse a simple grammar?

python parsing nlp pyparsing ply

Ok, so I've asked a bunch of smaller questions about this project, but I still don't have much confidence in the designs I'm coming up with, so I'm going to ask a question on a broader scale.

onPause() and onStop() in Activity

android android-emulator onpause

I am new to Android development and I am still not able to understand the onPause() and onStop() methods in an activity.