Any alternative or improvement of my recursive/iterative approach?

Question

I'm trying to write a parent searching code using python 3.

Parent is a 0-based-array that contain a parent of that element. For example, parent=[0,0] means that

1. Parent of the first element is itself.

2. Parent of the second element is the first element, therefore second element value is equal to first element's value

First, I tried using a recursive approach.

def getParent2(table):
    # find parent and compress path
    if table!=parent[table]:
        parent[table]=getParent2(parent[table])
    return parent[table]

Even though this approach seems to shows a very good speed, it faced a stack-overflow problem in a very large parent array.

(*Setting recursionlimit also resulted in a system error code 7.)

I tried modified it in to iterative approach

def getParent3(table):

    while table!=parent[table]:
        table=parent[table]    

    return table

Unfortunately it's running unacceptably slow on the same large parent array.

Any ideas to improve this code without changing the recursionlimit?

Thank you.

---

Sorry for not having a sample data, it's a really a large one (10000+) so here is a small sample of this function.

For example,

parent=[0,0,2,1,2]

getParent(3) will gives 0 as a result

Since parent of the 4th element (0-base) is the 2nd element, and the parent of the 2nd element is 1st element

It goes like this, 3-->1-->0

Answer 1

You didn't give us any data to test it on, so I'm assuming @Cel Skeggs identified the key difference in her comment. Fleshing out her suggestion (but untested because - again - you supplied no data):

def getParent4(table):
    chain = []
    while table != parent[table]:
        chain.append(table)
        table = parent[table]    
    for link in chain:
        parent[link] = table
    return table

But the speed difference you saw doesn't really make sense unless you're calling the function multiple times at the top level - in which case, collapsing paths can make a huge difference. However, you didn't say anything about that either ;-)