rekurencja ogonowa tail call optimization - ghdrako/doc_snipets GitHub Wiki
A tail call is any function call that is in tail position, the final action to be performed before a function returns. When tail call optimization occurs, the compiler emits a jmp instruction for the tail call instead of call. This skips over the bookkeeping that would normally allow the callee g() to return back to the caller f(), like creating a new stack frame or pushing the return address. Instead f() jumps directly to g() as if it were part of the same function, and g() returns directly to whatever function called f(). This optimization is safe because f()’s stack frame is no longer needed once the tail call has begun, since it is no longer possible to access any of f()’s local variables.
it has two very important properties unlock new possibilities in the kinds of algorithms we can write. First, it reduces the stack memory from from O(n)O(n) to O(1)O(1) when making nn consecutive tail calls, which is important because stack memory is limited and stack overflow will crash your program. This means that certain algorithms are not actually safe to write unless this optimization is performed. Secondly, jmp eliminates the performance overhead of call, such that a function call can be just as efficient as any other branch. These two properties enable us to use tail calls as an efficient alternative to normal iterative control structures like for or while.
Podczas optymalizacji wywołania ogonowego (tail call optimization), stos poprzedniej funkcji może zostać zwolniony, gdyż operacja jmp powoduje bezpośrednie przejście do nowej funkcji bez tworzenia nowej ramki stosu. Oznacza to, że ramka stosu funkcji wywołującej nie jest już potrzebna, ponieważ nie będzie już dostępu do jej lokalnych zmiennych. Dzięki temu unika się nadmiarowego zużycia pamięci i można zapobiec przepełnieniu stosu w przypadku głębokiej rekurencji.