Recursive Algorithm

From GM-RKB
(Redirected from Recursion)
Jump to navigation Jump to search

A Recursive Algorithm is an algorithm (that applies a recursive function.



References

2015a

  • (Wikipedia, 2015) ⇒ http://en.wikipedia.org/wiki/recursion_(computer_science) Retrieved:2015-7-9.
    • Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem (as opposed to iteration). The approach can be applied to many types of problems, and recursion is one of the central ideas of computer science.

      "The power of recursion evidently lies in the possibility of defining an infinite set of objects by a finite statement. In the same manner, an infinite number of computations can be described by a finite recursive program, even if this program contains no explicit repetitions."

      Most computer programming languages support recursion by allowing a function to call itself within the program text. Some functional programming languages do not define any looping constructs but rely solely on recursion to repeatedly call code. Computability theory provesthat these recursive-only languages are Turing complete; they are as computationally powerful as Turing complete imperative languages, meaning they can solve the same kinds of problems as imperative languages even without iterative control structures such as “while” and “for”.

2015b

  • (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;
}

1996

1990

1976