Python solution with no recursion. Finds p(666) in ~0.017s, p(66666) in ~30s.

def third_seq_first():
    val = 0
    while True:
        val += 1
        yield val

def third_seq_second():
    val = 1
    while True:
        val += 2
        yield val

def third_seq():
    first = third_seq_first()
    second = third_seq_second()
    for i, j in zip(first, second):
        yield i
        yield j

def second_seq():
    val = 1
    n = 0
    third = third_seq()
    for i in third:
        yield val
        val += i

def generate_p_list(p_in_progress):
    if tuple(p_in_progress) in gen_p_list_memos:
        return gen_p_list_memos[tuple(p_in_progress)].copy()
    lst = []
    seq = second_seq()
    if p_in_progress[0] <= 0:
        return [[0, p_in_progress[1]]]
    for i in seq:
        curr = p_in_progress[0] - i
        if curr < 0:
            break
        else:
            lst.append(curr)
    for i in range(len(lst)):
        if (i % 4) <= 1:
            lst[i] = [lst[i], 1]
        else:
            lst[i] = [lst[i], -1]
    if p_in_progress[1] == -1:
        for i in lst:
            i[1] = -i[1]
    lst.reverse()
    gen_p_list_memos[tuple(p_in_progress)] = lst.copy()
    return lst
gen_p_list_memos = {}

memos = {0:1}

def p(n):
    sum = 0
    lst = generate_p_list([n, 1])
    while lst != []:
        i = lst.pop()
        if i[0] in memos:
            sum += memos[i[0]] * i[1]
        else:
            flag = False
            temp = generate_p_list(i)
            for j in temp:
                if j[0] not in memos:
                    flag = True
                    break
            if not flag:
                acc = 0
                for j in temp:
                    acc += memos[j[0]] * j[1]
                memos[i[0]] = abs(acc)
                sum += acc
            else:
                lst += temp
    return sum

import time
def timed(num):
    st = time.time()
    p(num)
    print("%s seconds" % (time.time() - st))