Recursive Function

From GM-RKB
Jump to navigation Jump to search

A Recursive Function is a function whose function definition includes a reference to the function.



References

2015

  • (Wikipedia, 2015) ⇒ http://en.wikipedia.org/wiki/recursion_(computer_science)#Recursion_versus_iteration Retrieved:2015-7-9.
    • Recursion and iteration are equally expressive: recursion can be replaced by iteration with an explicit stack, while iteration can be replaced with tail recursion. Which approach is preferable depends on the problem under consideration and the language used. In imperative programming, iteration is preferred, particularly for simple recursion, as it avoids the overhead of function calls and call stack management, but recursion is generally used for multiple recursion. By contrast, in functional languages recursion is preferred, with tail recursion optimization leading to little overhead, and sometimes explicit iteration is not available.

      Compare the templates to compute xn defined by xn = f(n, xn-1) from xbase:

function recursive(n)
    if n==base
        return xbase
    else
        return f(n, recursive(n-1)) 
function iterative(n)
    x = xbase
    for i = n downto base
        x = f(i, x)
    return x
For imperative language the overhead is to define the function, for functional language the overhead is to define the accumulator variable x.

For example, the factorial function may be implemented iteratively in C by assigning to an loop index variable and accumulator variable, rather than passing arguments and returning values by recursion:

unsigned int factorial(unsigned int n) {
 unsigned int product = 1; // empty product is 1
 while (n) {
   product *= n;
   --n;
 }
 return product;
}