Lõpprekursioon

Lõpprekursioon, or tail recursion, is a special case of recursion where the recursive call is the very last operation in a function. This means that after the recursive call is made, no further computation is performed within the current function's scope. This property is significant because it allows compilers and interpreters to optimize the function call, often transforming it into an iterative loop.

The optimization of tail recursion is known as tail call optimization (TCO). When TCO is applied, the system can reuse the current stack frame for the recursive call instead of allocating a new one. This prevents the stack from growing with each recursive call, thereby avoiding potential stack overflow errors that can occur with deep or infinite recursion. In essence, the function behaves like a loop, consuming constant stack space.

Many functional programming languages, such as Scheme and Haskell, guarantee tail call optimization. However, it is not universally implemented across all programming languages. For instance, standard C and C++ compilers may not perform TCO by default, though it can sometimes be enabled with specific compiler flags or under certain conditions. Languages that do not support TCO will still execute tail-recursive functions, but they will consume stack space equivalent to non-tail-recursive functions.

Recognizing and implementing tail recursion can be a valuable technique for writing efficient and stack-safe recursive algorithms, particularly in contexts where deep recursion is expected. It often involves restructuring the recursive function to pass intermediate results as parameters to the next recursive call.