Recursion (computer science)
The approach can be applied to many types of problems, and recursion is one of the central ideas of computer science.
[3] The power of recursion evidently lies in the possibility of defining an infinite set of objects by a finite statement.
Some functional programming languages (for instance, Clojure)[5] do not define any looping constructs but rely solely on recursion to repeatedly call code.
This is often referred to as the divide-and-conquer method; when combined with a lookup table that stores the results of previously solved sub-problems (to avoid solving them repeatedly and incurring extra computation time), it can be referred to as dynamic programming or memoization.
(Functions that are not intended to terminate under normal circumstances—for example, some system and server processes—are an exception to this.)
Neglecting to write a base case, or testing for it incorrectly, can cause an infinite loop.
Standard examples of single recursion include list traversal, such as in a linear search, or computing the factorial function, while standard examples of multiple recursion include tree traversal, such as in a depth-first search.
Examples of generative recursion include: gcd, quicksort, binary search, mergesort, Newton's method, fractals, and adaptive integration.This distinction is important in proving termination of a function.
These include: On the basis of elegance, wrapper functions are generally approved, while short-circuiting the base case is frowned upon, particularly in academia.
Wrapper functions can be used to validate parameters (so the recursive function can skip these), perform initialization (allocate memory, initialize variables), particularly for auxiliary variables such as "level of recursion" or partial computations for memoization, and handle exceptions and errors.
Short-circuiting is primarily a concern when many base cases are encountered, such as Null pointers in a tree, which can be linear in the number of function calls, hence significant savings for O(n) algorithms; this is illustrated below for a depth-first search.
Note that this requires a wrapper function to handle the case when the tree itself is empty (root node is Null).
In fact, the entire control flow of these functions can be replaced with a single Boolean expression in a return statement, but legibility suffers at no benefit to efficiency.
Recursive algorithms are often inefficient for small data, due to the overhead of repeated function calls and returns.
For example, a factorial function may be implemented iteratively in C by assigning to a loop index variable and accumulator variable, rather than by passing arguments and returning values by recursion: Most programming languages in use today allow the direct specification of recursive functions and procedures.
In languages where looping constructs are preferred, the iterative version may be as much as several orders of magnitude faster than the recursive one.
Because recursive algorithms can be subject to stack overflows, they may be vulnerable to pathological or malicious input.
[15] Even in the absence of malware, a stack overflow caused by unbounded recursion can be fatal to the program, and exception handling logic may not prevent the corresponding process from being terminated.
[19] An alternative is to develop a replacement algorithm entirely based on non-recursive methods, which can be challenging.
Thus the program is essentially iterative, equivalent to using imperative language control structures like the "for" and "while" loops.
A classic example of a recursive procedure is the function used to calculate the factorial of a natural number: The function can also be written as a recurrence relation: This evaluation of the recurrence relation demonstrates the computation that would be performed in evaluating the pseudocode above: This factorial function can also be described without using recursion by making use of the typical looping constructs found in imperative programming languages: The imperative code above is equivalent to this mathematical definition using an accumulator variable t: The definition above translates straightforwardly to functional programming languages such as Scheme; this is an example of iteration implemented recursively.
The Euclidean algorithm, which computes the greatest common divisor of two integers, can be written recursively.
: The recursive program above is tail-recursive; it is equivalent to an iterative algorithm, and the computation shown above shows the steps of evaluation that would be performed by a language that eliminates tail calls.
Below is a version of the same algorithm using explicit iteration, suitable for a language that does not eliminate tail calls.
The algorithm exhibits a logarithmic order of growth because it essentially divides the problem domain in half with each pass.
Example implementation of binary search in C: An important application of recursion in computer science is in defining dynamic data structures such as lists and trees.
As long as a programmer derives the template from a data definition, functions employ structural recursion.
Since the number of files in a filesystem may vary, recursion is the only practical way to traverse and thus enumerate its contents.
The time efficiency of recursive algorithms can be expressed in a recurrence relation of Big O notation.
In symbolic form: The logical reading frees the reader from needing to know how the clause is used to solve problems.
