# Better implementation to find the root of an element in QuickUnion implementation of UnionFind problem

I wanted to know which implementation is better to find the root of the element in the Quick Union implementation of the UnionFind problem. The professor has used a while loop to find the root of the element, while I have implemented it using a recursive approach. Which approach is better in terms of space complexity, and scalability for large arrays?

//Quick union method for Union-find algorithm. Lazy approach

import java.util.Scanner;

public class QuickUnionUF {

private int [] id;
public QuickUnionUF(int N)
{
id= new int[N];
for(int i=0; i<id.length;++i)
{
id[i]=i;
}
}

public int root(int p)
{
if(id[p]==p) return p;
else return(root(id[p]));
}

public boolean isConnected(int p, int q)
{
return (root(p)==root(q));
}

public void union(int p, int q){
int proot= root(p);
int qroot= root(q);

id[proot]= qroot;
}

}


For the root function, the professor has used -

public int root(int p) {
while (p != id[p])
p = id[p];
return p;
}


https://algs4.cs.princeton.edu/15uf/

The time complexity for both versions is exactly the same. It is linear in terms of the distance between $$p$$ and the $$root$$.
This might give problems, if the distance between $$p$$ and $$root$$ is very long. Image a tree with $$id[0] = 0$$ and $$id[p] = p - 1$$ for $$p > 0$$. Then finding the root for a large element $$p$$ might exceed the allocated stack and crash the program.
However in practice the situation might look a bit different. Depending on the programming language, the compiler/interpreter, configuration this linear space can be optimized to constant space. The concept that allows such an optimization is called tail recursion. E.g. gcc -O3 will generate exactly the same assembler code for both versions: example. But be careful, not all languages, compiler / interpreter have these optimizations implemented.