I was just writing some simple utility that calculates the length of a linkedList such that the linkedList doesn't host an "internal" counter of its size/length. With this is mind, I had 3 simple approaches:
- Iterate over the linkedList until you hit the "end"
- Recursively calculate the length
- Recursively calculate the length without needing to return control to the calling function (using some flavor of tail-call recursion)
Below is some code that captures these 3 cases:
// 1. iterative approach
public static <T> int getLengthIteratively(LinkedList<T> ll) {
int length = 0;
for (Node<T> ptr = ll.getHead(); ptr != null; ptr = ptr.getNext()) {
length++;
}
return length;
}
// 2. recursive approach
public static <T> int getLengthRecursively(LinkedList<T> ll) {
return getLengthRecursively(ll.getHead());
}
private static <T> int getLengthRecursively(Node<T> ptr) {
if (ptr == null) {
return 0;
} else {
return 1 + getLengthRecursively(ptr.getNext());
}
}
// 3. Pseudo tail-recursive approach
public static <T> int getLengthWithFakeTailRecursion(LinkedList<T> ll) {
return getLengthWithFakeTailRecursion(ll.getHead());
}
private static <T> int getLengthWithFakeTailRecursion(Node<T> ptr) {
return getLengthWithFakeTailRecursion(ptr, 0);
}
private static <T> int getLengthWithFakeTailRecursion(Node<T> ptr, int result) {
if (ptr == null) {
return result;
} else {
return getLengthWithFakeTailRecursion(ptr.getNext(), result + 1);
}
}
Now I'm aware that the JVM doesn't support tail-recursion out of the box, but when I ran some simple tests that had linkedLists of strings with ~10k nodes, I noticed the getLengthWithFakeTailRecursion consistently outperform the getLengthRecursively method (by ~40%). Could the delta be only attributed to the fact that control is being passed back per node for case#2 and we're forced to traverse across all stack-frames?
Edit: Here's the simple test I used to check the performance numbers:
public class LengthCheckerTest {
@Test
public void testLengthChecking() {
LinkedList<String> ll = new LinkedList<String>();
int sizeOfList = 12000;
// int sizeOfList = 100000; // Danger: This causes a stackOverflow in recursive methods!
for (int i = 1; i <= sizeOfList; i++) {
ll.addNode(String.valueOf(i));
}
long currTime = System.nanoTime();
Assert.assertEquals(sizeOfList, LengthChecker.getLengthIteratively(ll));
long totalTime = System.nanoTime() - currTime;
System.out.println("totalTime taken with iterative approach: " + (totalTime / 1000) + "ms");
currTime = System.nanoTime();
Assert.assertEquals(sizeOfList, LengthChecker.getLengthRecursively(ll));
totalTime = System.nanoTime() - currTime;
System.out.println("totalTime taken with recursive approach: " + (totalTime / 1000) + "ms");
// Interestingly, the fakeTailRecursion always runs faster than the vanillaRecursion
// TODO: Look into whether stack-frame collapsing has anything to do with this
currTime = System.nanoTime();
Assert.assertEquals(sizeOfList, LengthChecker.getLengthWithFakeTailRecursion(ll));
totalTime = System.nanoTime() - currTime;
System.out.println("totalTime taken with fake TCR approach: " + (totalTime / 1000) + "ms");
}
}
