[Tutor] Question on lists

[Martijn Faassen]

Jon Cosby wrote:
[snip question]
 
> # Factor by trial division:
> def factor(n):
>      a = []                # Is there a better way to define a?
>      k = floor(sqrt(n))
>      for i in range(2, k+1):
>           if n%i == 0:
>              a.insert(len(a), i)
>              factor(n/i)    # Factor quotient
>              break
>      return a

Hullo,

This is a common phenomenon with recursive functions. In your function
you initialize a to a new empty list each time factor() gets called.
Instead, you need to pass the list that you are building along each time
you call the function. The usual Python trick for this is to use default
arguments to functions. This way you can pass the list on to each
recursive function, and the function still works as expected if you use
it with a single argument. 

Here's the improved function:

from math import floor, sqrt

def factor(n, a = []):        # if no second argument is passed, use the
empty list for a
    k = floor(sqrt(n))
    for i in range(2, k+1):
        if n%i == 0:
            a.append(i)       # more efficient and readable than
a.insert(len(a), i)
            factor(n/i, a)    # Factor quotient
            break
    return a

print factor(36) # test things

Note that there is still an algorithmic problem with your function; the
last quotient doesn't appear to be added to the list (k becomes smaller
than 2, namely 1, so the range command generates an empty list
(effectively nothing). The condition that ends the recursion appears to
be wrong (in your program it occurs whenever k <= 2). 

If this one of your first experiences with recursion, welcome to
recursion, that mystical powerful way to program (though it isn't too
fast in Python - go to functional programming languages such as lisp for
that). Do amazing things by just letting functions call themselves; it's
almost something for nothing! At least so it seemed to me at my first
brush with recursion.

Regards and good luck, 

Martijn