Tail call
A recursive function f is tail recursive (English tail recursive, also terminally recursive, iterative recursive, repetitive, recursive) if the recursive function call is the last action for the calculation of f. Advantage of this function definition is that no additional space is required to manage the recursion.
Removal of terminal function calls
The naive execution of a recursive function of the memory consumption increases linearly with the depth of recursion, since each function call space for the recording of the current continuation of the program flow and the function parameter is set (about to secure the return address and the current stack frame on the call stack). Furthermore, additional space for storage of function local variables can be allocated during the execution of the called function. In a terminal function call the data stored in occupied for the calling function storage area but values are only needed for passing parameters to the terminal called function, so that this memory area can be reused. Thus, tail-recursive functions can be automatically transformed ( possibly through an optimization step of the compiler ) in iterative functions whose memory consumption is independent of the depth of recursion when processing. When forming the calls of the terminal function are replaced by corresponding jump instructions ( tail call elimination ).
Some programming languages such as Scheme require the automatic conversion of tail-recursive functions into iterative functions as part of their language definition. Other programming languages such as C, C and C # or Java does not require this conversion, but leave them for the specific language implementation as optimization. As an optimization, this technique is commonly found in compilers for functional programming languages , as when using a functional programming style recursive / tail recursive formulation is particularly common for many algorithms, and therefore such formulations in the context of program optimization during translation by a compiler of particular attention.
The automatic replacement of function calls through jump instructions with reuse of the current stack frame makes it difficult to trace a program to determine the cause, because the call stack when interrupting a running program the call sequence of functions does not fully reflect at a breakpoint.
Applicability and generalization
The applicability of the technique for the replacement of terminal function calls with jumps is not limited to tail-recursive functions. Scheme requires, for example, also across functions execution of terminal functions with constant memory usage (proper tail recursion ), for example, two functions that call each other to terminal.
Due to the transition to continuation- passing style can in principle transform programs so that all function calls are replaced by terminal calls. This, however all called functions must be transformed so that they take a continuation as a parameter, which they then explicitly enable terminally with transfer of the function result of the implementation of another program run. When executing a thus -formed program then constant memory available for storing the activation records (eg on the call stack) is needed, but the space required for storing the continuations is not limited. As a result of this conversion, then the recursion levels of a routine by the memory space available for storage of the sequels is limited instead by the size of the call stack.
Examples
Given the recursive function sum that calculates the sum of the first n positive integers:
Sum ( s) if n = 0 return 0 else return sum n ( n-1) Since not the recursive function call but the addition is the final action, it is not a tail recursive function. The calculation of sum ( 3) would therefore involve the following steps:
Sum (3) = 3 Sum (2) Sum (2) = 2 sum ( 1) Sum (1) = 1 SUM ( 0) SUM ( 0) = 0 Sum (1) = 1 0 = 1 Sum (2) = 2 1 = 3 Sum (3) = 3 3 = 6 In this case, however, a transformation into a tail recursive representation is possible.
Sum ( s) add_sum return ( 0, n) add_sum ( m, n) if n = 0 return m else return add_sum (m n, n-1 ) The tail-recursive auxiliary function add_sum receives two parameters m and n and returns as its result the sum of m and the sum of the first n natural numbers. The call add_sum ( 0, n) thus provides the desired result, the sum of the first n natural numbers. During the course of tail recursion in add_sum the intermediate results in the m parameter are accumulated. In this tail-recursive formulation of the calculation of sum ( 3) would contain approximately the following steps:
Sum (3) = add_sum (0, 3) Add_sum = (3, 2 ) Add_sum = (5, 1) Add_sum = (6, 0) = 6 When forming the associative law for addition of natural numbers has been implicitly exploited. The original definition of sum ( s) calculated sum ( 3) as
3 ( 2 ( 1 0) ) The transformed formulation calculates the same value as
( (0 3 ) 2 ) 1 Like any recursive function can be represented by means of iteration, the tail recursion.
Sum ( s) m: = 0 while ( n> 0) do m: = m n n: = n - 1 end -while return m Recursive such iterative solutions usually represent a direct reaction to a problem that has been analyzed step by step. Saving space and readability mean sacrificing the execution time. In many cases, therefore, worth the search for more efficient algorithms. Thus, the best algorithm for computing the example case above all by the " Gaussian school history " has become known:
Sum (n) = (n * (n 1) ) / 2 As an example of tail recursion with multiple functions involved here even two odd functions and to determine if a given natural number is even or odd.
Even ( n ) if n = 0 return true else return odd ( n-1) odd ( n ) if n = 0 return false else return even ( n-1) The two functions call each other on terminal. By itself, none of the two functions is tail recursive.
Generalization
In general, a function f is tail recursive if it can be defined as follows:
Here, r and s are not defined by any functions f and R is the termination condition.