What do you mean by the function itself being tail-recursive?

Yes, tail recursion is being applied to those calls. It is not to the nested calls. This avoids creating many stack frames. But as you walk right, you will still get a deep stack.

So the function is benefitting from the optimization. But only on half of your recursive calls. What do you want to call that?