I am reading through an Algorithms book and am working through a recursive solution to the following question:
Implement a function to check if a linked list is a palindrome
This is an easy enough task, but the book suggests a recursive solution that I can't seem to wrap my head around. It states that to know when we are at the center of the linked list, we can perform the following operation:
recurse(Node n, int length) {
if (length == 0 || length == 1) {
return [something]; // At middle
}
recurse(n.next, length - 2);
...
}
Why does length - 2
recursively get you to the middle? Can someone explain this in detail? I understand that it works, but not mathematically why it works.