Three Partition-Function Algorithms Comparison I have implemented three algorithms codes, in Swift:

1- Polynomial coefficient:

 // create polynomial
func arrangePoly(ofTerms term: Int, toLength len: Int) -&gt; [Int] {
    var a = Array(repeating: 0, count: len+1)

    for i in stride(from: 0, to: a.count, by: term) {
        a[i] = 1
    }
    return a
}
// polynomial product
func productToN(array1 a: [Int], arrayb b: [Int], toPower n: Int) -&gt; [Int] {
    var res = Array(repeating: 0, count: n+1)

    for (pa, ca) in a.enumerated() {
        for (pb, cb) in b.enumerated() {
            if pa+pb &lt;= n {
                res[pa+pb] += ca*cb
            }
        }
    }
    return res
}
// test code: partition of N
var p1 = arrangePoly(ofTerms: 1, toLength: N)
var res = p1

for i in 2...N {
    res = productToN(array1: res, arrayb: arrangePoly(ofTerms: i, toLength: N), toPower: N)
}
print(res[N])   // coefficient of x^N


2- Euler recurrence relations:

func eulerPartition(_ n: Int) -&gt; Int {
    if n &lt; 0 {
        return 0
    } else if n == 0 {
        return 1
    } else {
        var k = 1
        var sum = 0
        while k &lt;= n {
            let sign = power(-1, k-1)
            sum += sign * (eulerPartition(n-(k*((3*k)-1)/2)) + eulerPartition(n-(k*((3*k)+1)/2)))
            k += 1
        }
        return sum
    }
}


3- Divisor sum formula:

// sigma(k) is the well-known sum of divisors of k
func part(_ n: Int) -&gt; Int {
    if n &lt; 0 {
        return 0
    } else if n == 0 {
        return 1
    } else {
        var k = 1
        var sum = 0
        while k &lt;= n {
            sum += sigma(k) * part(n-k)
            k += 1
        }
        return sum / n
    }
}


All the three versions gives the same results for each n >= 1, but with different efficiency. While the Euler recurrence algorithm is assumed, theoretically, to be the fastest of the three, the polynomial coefficient algorithm works the best on my core2duo  laptop in spite of it is not recursively coded like the others. I am sure I have done something wrong, but I can not figure what or where. 

Any idea?
Your implementation of the Euler method doesn't use memoization, so you keep computing and recomputing the same values. This is like computing the Fibonacci numbers along the following lines:

Fibonacci(n)
  if n = 0 or n = 1, return n
  otherwise, return Fibonacci(n-1) + Fibonacci(n-2)


You should modify the implementation so that after calculating eulerPartition for a certain $n$, if you are given the same $n$ again then you immediately return the previously calculated value.