Узкое место в моем рекурсивном коде Python

Question

Я написал код ниже, используя рекурсию для выполнения алгоритма CYK, чтобы грамматика G может генерировать любые слова, имеющие одинаковое количество aсопровождается любым количеством bНо почему-то это очень медленно, не знаете почему? Когда я использую s2, это работает, но если я использую s1, который является более длинной строкой, это займет вечность. Кто-нибудь может посоветовать, пожалуйста, так как я не могу понять, где узкое место?

def fn(G, w, i, j, T):
    if T[i, j]:
        print '1'
        return T[i, j]
    elif i == j:
        for r in G:
            print '2'
            if r.endswith(w[i]) and r[0] not in T[i, j]:    
                print '3'
                T[i, j].append(r[0])
    else:
        print '4'
        for k in range(i, j):
            print '5'
            for a in fn(G, w, i, k, T):
                print '6'
                for b in fn(G, w, k+1, j, T):
                    print '7'
                    for r in G:
                        print '8'
                        if r.endswith(a+b) and r[0] not in T[i, j]:
                            print '9'
                            T[i, j].append(r[0])
    return T[i, j]


def fnmain(G, S, w):
    dict = {}
    for x in range(0, len(w)):
        for y in range(x, len(w)):
            dict[x,y] = []
    print dict        
    v = fn(G, w, 0, len(w) - 1, dict)
    print (w, v)
    if S in v:
        print ("T")
        return True
    else:
        print ("F")
        return False

G = ["S->AB", "S->XB", "T->AB", "T->XB", "X->AT", "A->a", "B->b"]

s1 = "aaaaabbbbb"
s1 = "aaaaaaaaabbbbbbbbb"

fnmain(G, "S", s1)

Я использовал cProfile как предложено @wwii и ниже, это результат:

Когда s1 = "aaaaabbbbb" когда s1= "aaaaaaaaabbbbbbbbb"