Tail vs Non-Tail Recursion

Recursion can be broadly categorized into tail recursion and non-tail (or head) recursion, with the distinction having significant implications for performance and memory usage. A recursive function is said to be 'tail-recursive' if the recursive call is the absolute last thing the function does. There should be no pending operations to be performed on the return of the recursive call. For instance, a function `return func(n-1) + 1;` is non-tail recursive because an addition operation (`+ 1`) must be performed after the recursive call `func(n-1)` returns. A tail-recursive version might look like `return func(n-1, acc+1);`, where the result is built up in an accumulator argument. The major advantage of tail recursion is that it can be optimized by the compiler. This is called Tail Call Optimization (TCO). With TCO, the compiler can reuse the current stack frame for the next recursive call instead of creating a new one. This transforms the recursion into an iteration under the hood, effectively giving it the O(1) space complexity of a loop and preventing stack overflow errors for deep recursion. Not all languages or compilers perform TCO, but it's a standard feature in functional programming languages. Understanding this distinction is important for writing efficient and safe recursive code, especially for problems that could lead to a large recursion depth.