Understanding a factorial function in python

Question

I'm trying to understand if the following Python function:

def factorial(i):
    if not hasattr(factorial, 'lstFactorial'):
        factorial.lstFactorial = [None] * 1000
    if factorial.lstFactorial[i] is None:
        iProduct = 1
        for iFactor in xrange(1, i+1):
            iProduct *= iFactor
        factorial.lstFactorial[i] = iProduct
    return factorial.lstFactorial[i]

would produce the same results as the equivalent in C#:

long factorial(long n) 
{ 
   return n <= 1 ? 1 : n * factorial(n-1);
}

for a value of 12 or less.

I know nothing about Python but have just converted some Python code to C#. This was the only function that I didn't fully understand.

Answer 1

here is main algorithm

iProduct = 1
for iFactor in xrange(1, i+1):
    iProduct *= iFactor

other code is for caching results.

Answer 2

it will return the same results, but the Python version will probably have better performance, because it memoizes the results

Answer 3

Even without knowing Python, it must be clear to you that the two functions are far from identical. The C# version is calculating the factorial via recursion, whereas the Python one is doing it via iteration (although in a slightly weird way, with some odd memoization/caching going on - I guess in case you want to calculate multiple factorials in the lifetime of a program).

Anyway, since calculating a factorial is a very simple algorithm, it works out the same in both cases.

Answer 4

IANAPG (Python Guru), but it looks to me like the function is creating a static array of 1000 entries, then filling them on an as-needed basis to prevent recalculation. In C++, it'd be something like:

long factorial(int i){
    //Cache array
    static long factorials[1000];
    if (!factorials[i]){ //If not cached, calculate & store
        int product = 1;
        for (int idx = 1; idx <= i + 1; ++idx){
            product *= idx;
        }
        factorials[i] = product;
    }
    return factorials[i]; //Return cached value
}

Answer 5

It just attaches an attribute called lstFactorial to factorial. This attribute is a list of 1000 values used to cache the results of previous calls.

Answer 6

def factorial(i):
    if not hasattr(factorial, 'lstFactorial'): #program checks whether caching list exists
        factorial.lstFactorial = [None] * 1000 #if so, it creates a list of thousand None elements (it is more or less equivalent to C/C++'s NULL
    if factorial.lstFactorial[i] is None: #prog checks if that factorial has been already calculated
        iProduct = 1 #set result to 1
        for iFactor in xrange(1, i+1): # C's for(iFactor = 1; iFactor <= i+1; iFactor++)
            iProduct *= iFactor #we multiply result times current loop counter
        factorial.lstFactorial[i] = iProduct #and put result in caching list
    return factorial.lstFactorial[i] #after all, we return the result, calculated jest now or obtained from cache

To be honest, it is not the best algorithm, since it uses cache only partially.

The simple, user-friendly factorial function (no caching) would be:

def factorial(i):
    if i == 0 or i == 1:
        return 1
    return i*factorial(i-1)

Of for lazy python programmers, most similiar to that C# example:

f = lambda i: i and i*f(i-1) or 1