Final recursion
A recursive function f is tail-recursive ( English tail recursive , nor terminal-recursive , iterative recursively , repetitive recursively ) if the recursive function call, the last action for the calculation of f is. The advantage of this function definition is that no additional storage space is required to manage the recursion.
Automatic removal of terminal function calls
With the naive processing of a recursive function, the memory space consumption increases linearly with the recursion depth, since with each function call memory space is used for recording the current continuation of the program flow and the function parameters (e.g. to save the return address and the current stack frame on the call stack ). In addition, additional storage space can be reserved for storing function-local variables while the called function is being processed. In the case of a terminal function call, the values stored in the memory area used for the calling function are only required for the parameter transfer to the terminally called function, so that this memory area can be reused. This means that end recursive functions can be converted automatically (for example as part of an optimization step of the compiler ) into iterative functions whose memory space consumption during processing is independent of the recursion depth. During the conversion, the calls to the terminal function are replaced by appropriate jump instructions ( tail call elimination ).
Some programming languages, such as Scheme, require the automatic transformation of end recursive functions into iterative functions as part of their language definition. Other programming languages such as C , C ++ and C # or Java do not require this conversion, but allow it to be optimized for the respective language implementation. As an optimization, this technique can often be found in compilers for functional programming languages , because when using a functional programming style, the recursive / end-recursive formulation is particularly frequent for many algorithms and therefore such formulations are given special attention in the context of program optimization when compiling by a compiler.
The automatic replacement of function calls by jump instructions with reuse of the current stack frame makes it more difficult to trace a program during error analysis , since the call stack does not fully reflect the call sequence of the functions when a running program is interrupted at a breakpoint .
Explicit end recursion
The Clojure programming language provides the explicit call recurfor end recursion. The advantage of this is that the compiler recognizes when the call is not made from the end position and notifies the programmer of this.
Applicability and generalization
The applicability of the technique for replacing terminal function calls with jumps is not restricted to terminal recursive functions. Scheme requires, for example, the execution of terminal functions with constant memory space consumption ( proper tail recursion ), for example for two functions that call each other terminally.
With the transition to continuation-passing style , programs can in principle be reshaped in such a way that all function calls are replaced by terminal calls. To do this, however, all the functions called must be transformed in such a way that they accept a continuation as a parameter, which they then explicitly activate at the end when the function result is transferred for execution of the further program run. When executing such a reshaped program, constant storage space is then required for storing the activation records (e.g. on the call stack), but the storage space required for storing the continuations is not limited. As a result of this reshaping, the possible recursion depth of a routine is then limited by the memory space available for storing the continuations instead of by the size of the call stack.
Examples
Given is the recursive function sum , which calculates the sum of the first n natural numbers :
sum(n)
if n=0
return 0
else
return n + sum(n-1)
Since it is not the recursive function call but the addition that forms the last action, it is not a final recursive function. The calculation of sum(3)would thus include 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 conversion into a final recursive representation is possible.
sum(n) return add_sum (0, n)
add_sum(m, n)
if n=0
return m
else
return add_sum (m+n, n-1)
The end recursive auxiliary function add_sumreceives two parameters mand nand delivers the sum of mand the sum of the first nnatural numbers as the result . The call add_sum (0, n)thus delivers the desired result, the sum of the first nnatural numbers. While the final recursion is running in add_sum, the intermediate results are maccumulated in the parameter. In this final recursive formulation, the calculation would sum(3)include the following steps:
sum(3) = add_sum(0, 3)
= add_sum(3, 2)
= add_sum(5, 1)
= add_sum(6, 0)
= 6
During the transformation, the associative law was implicitly used for the addition of natural numbers. The original definition of sum(n)computed sum(3)as
3 + (2 + (1 + 0))
The transformed formulation calculates the same value as
((0 + 3) + 2) + 1
Like any primitive recursive function, the final recursion can be represented by iteration .
sum(n)
m := 0
while (n > 0) do
m := m + n
n := n - 1
end-while
return m
Recursive as well as iterative solutions usually represent a direct implementation of a problem that was analyzed step by step. Space savings and readability are at the expense of execution time. It is therefore often worthwhile to look for more efficient algorithms. The best algorithm for calculating the example case has become known primarily through the " Gaussian school history ":
sum(n) = (n*(n+1)) / 2
As an example of final recursion with several functions involved, here are two functions evenand oddto determine whether 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 terminally. Neither function is end recursive by itself.
generalization
In general, a function f is end recursive if it can be defined in the following way:
Here r and s are any functions not defined by f and R is the termination condition.
See also
Individual evidence
- ↑ Harold Abelson, Gerald Jay Sussman, and Julie Sussman: Linear Recursion and Iteration ( Memento of the original from September 3, 2006 in the Internet Archive ) Info: The archive link was automatically inserted and not yet checked. Please check the original and archive link according to the instructions and then remove this notice. . In: Structure and Interpretation of Computer Programs . Second edition, The MIT Press 1996, ISBN 0-262-51087-1
- ↑ recur - clojure.core | ClojureDocs - Community-Powered Clojure Documentation and Examples. In: clojuredocs.org. Retrieved January 18, 2017 .
- ^ Richard Kelsey, William Clinger, Jonathan Rees et al .: Revised 5 Report on the Algorithmic Language Scheme . In: Higher-Order and Symbolic Computation . 11, No. 1, August 1998, pp. 7-105. doi : 10.1023 / A: 1010051815785 .
- ↑ William Clinger: Proper tail recursion and space efficiency ( Memento of the original from October 30, 2015 in the Internet Archive ) Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice. (PDF; 240 kB), Proceedings of the 1998 ACM Conference on Programming Language Design and Implementation, June 1998, pp. 174-185
- ^ Daniel P. Friedman, Mitchell Wand, Christopher T. Haynes: Essentials of Programming Languages . Second edition, MIT Press 2001, ISBN 0262062178
