![recursiveTree](https://upload.wikimedia.org/wikipedia/commons/f/f7/RecursiveTree.JPG)
In
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includi ...
, recursion is a method of solving a
computational problem
In theoretical computer science, a computational problem is a problem that may be solved by an algorithm. For example, the problem of factoring
:"Given a positive integer ''n'', find a nontrivial prime factor of ''n''."
is a computational probl ...
where the solution depends on solutions to smaller instances of the same problem. Recursion solves such
recursive problems by using
functions that call themselves from within their own code. The approach can be applied to many types of problems, and recursion is one of the central ideas of computer science.
Most computer
programming language
A programming language is a system of notation for writing computer programs. Most programming languages are text-based formal languages, but they may also be graphical. They are a kind of computer language.
The description of a programming ...
s support recursion by allowing a function to call itself from within its own code. Some
functional programming
In computer science, functional programming is a programming paradigm where programs are constructed by applying and composing functions. It is a declarative programming paradigm in which function definitions are trees of expressions that ...
languages (for instance,
Clojure
Clojure (, like ''closure'') is a dynamic and functional dialect of the Lisp programming language on the Java platform. Like other Lisp dialects, Clojure treats code as data and has a Lisp macro system. The current development process is comm ...
) do not define any looping constructs but rely solely on recursion to repeatedly call code. It is proved in
computability theory that these recursive-only languages are
Turing complete
Alan Mathison Turing (; 23 June 1912 – 7 June 1954) was an English mathematician, computer scientist, logician, cryptanalyst, philosopher, and theoretical biologist. Turing was highly influential in the development of theoretical co ...
; this means that they are as powerful (they can be used to solve the same problems) as
imperative languages based on control structures such as and .
Repeatedly calling a function from within itself may cause the
call stack
In computer science, a call stack is a stack data structure that stores information about the active subroutines of a computer program. This kind of stack is also known as an execution stack, program stack, control stack, run-time stack, or m ...
to have a size equal to the sum of the input sizes of all involved calls. It follows that, for problems that can be solved easily by iteration, recursion is generally less
efficient, and, for large problems, it is fundamental to use optimization techniques such as
tail call
In computer science, a tail call is a subroutine call performed as the final action of a procedure. If the target of a tail is the same subroutine, the subroutine is said to be tail recursive, which is a special case of direct recursion. Tail recur ...
optimization.
Recursive functions and algorithms
A common
algorithm design
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing c ...
tactic is to divide a problem into sub-problems of the same type as the original, solve those sub-problems, and combine the results. This is often referred to as the
divide-and-conquer method
In computer science, divide and conquer is an algorithm design paradigm. A divide-and-conquer algorithm recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved dire ...
; 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
Dynamic programming is both a mathematical optimization method and a computer programming method. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics. ...
or
memoization.
Base case
A recursive function definition has one or more ''base cases'', meaning input(s) for which the function produces a result
trivial
Trivia is information and data that are considered to be of little value. It can be contrasted with general knowledge and common sense.
Latin Etymology
The ancient Romans used the word ''triviae'' to describe where one road split or forked ...
ly (without recurring), and one or more ''recursive cases'', meaning input(s) for which the program recurs (calls itself). For example, the
factorial function can be defined recursively by the equations and, for all , . Neither equation by itself constitutes a complete definition; the first is the base case, and the second is the recursive case. Because the base case breaks the chain of recursion, it is sometimes also called the "terminating case".
The job of the recursive cases can be seen as breaking down complex inputs into simpler ones. In a properly designed recursive function, with each recursive call, the input problem must be simplified in such a way that eventually the base case must be reached. (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
In computer programming, an infinite loop (or endless loop) is a sequence of instructions that, as written, will continue endlessly, unless an external intervention occurs ("pull the plug"). It may be intentional.
Overview
This differs from:
* ...
.
For some functions (such as one that computes the
series
Series may refer to:
People with the name
* Caroline Series (born 1951), English mathematician, daughter of George Series
* George Series (1920–1995), English physicist
Arts, entertainment, and media
Music
* Series, the ordered sets used in ...
for ) there is not an obvious base case implied by the input data; for these one may add a
parameter
A parameter (), generally, is any characteristic that can help in defining or classifying a particular system (meaning an event, project, object, situation, etc.). That is, a parameter is an element of a system that is useful, or critical, when ...
(such as the number of terms to be added, in our series example) to provide a 'stopping criterion' that establishes the base case. Such an example is more naturally treated by
corecursion
In computer science, corecursion is a type of operation that is dual to recursion. Whereas recursion works analytically, starting on data further from a base case and breaking it down into smaller data and repeating until one reaches a base case, ...
, where successive terms in the output are the partial sums; this can be converted to a recursion by using the indexing parameter to say "compute the ''n''th term (''n''th partial sum)".
Recursive data types
Many
computer program
A computer program is a sequence or set of instructions in a programming language for a computer to execute. Computer programs are one component of software, which also includes documentation and other intangible components.
A computer program ...
s must process or generate an arbitrarily large quantity of
data
In the pursuit of knowledge, data (; ) is a collection of discrete Value_(semiotics), values that convey information, describing quantity, qualitative property, quality, fact, statistics, other basic units of meaning, or simply sequences of sy ...
. Recursion is a technique for representing data whose exact size is unknown to the
programmer: the programmer can specify this data with a
self-referential
Self-reference occurs in natural or formal languages when a sentence, idea or formula refers to itself. The reference may be expressed either directly—through some intermediate sentence or formula—or by means of some encoding. In philoso ...
definition. There are two types of self-referential definitions: inductive and
coinductive
In computer science, coinduction is a technique for defining and proving properties of systems of concurrent interacting objects.
Coinduction is the mathematical dual to structural induction. Coinductively defined types are known as codata and ...
definitions.
Inductively defined data
An inductively defined recursive data definition is one that specifies how to construct instances of the data. For example,
linked lists can be defined inductively (here, using
Haskell
Haskell () is a general-purpose, statically-typed, purely functional programming language with type inference and lazy evaluation. Designed for teaching, research and industrial applications, Haskell has pioneered a number of programming lan ...
syntax):
data ListOfStrings = EmptyList , Cons String ListOfStrings
The code above specifies a list of strings to be either empty, or a structure that contains a string and a list of strings. The self-reference in the definition permits the construction of lists of any (finite) number of strings.
Another example of inductive
definition is the
natural numbers (or positive
integers
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
):
A natural number is either 1 or n+1, where n is a natural number.
Similarly recursive
definitions are often used to model the structure of
expressions and
statements
Statement or statements may refer to: Common uses
*Statement (computer science), the smallest standalone element of an imperative programming language
*Statement (logic), declarative sentence that is either true or false
*Statement, a declarative ...
in programming languages. Language designers often express grammars in a syntax such as
Backus–Naur form; here is such a grammar, for a simple language of arithmetic expressions with multiplication and addition:
::=
, ( * )
, ( + )
This says that an expression is either a number, a product of two expressions, or a sum of two expressions. By recursively referring to expressions in the second and third lines, the grammar permits arbitrarily complicated arithmetic expressions such as
(5 * ((3 * 6) + 8))
, with more than one product or sum operation in a single expression.
Coinductively defined data and corecursion
A coinductive data definition is one that specifies the operations that may be performed on a piece of data; typically, self-referential coinductive definitions are used for data structures of infinite size.
A coinductive definition of infinite
streams of strings, given informally, might look like this:
A stream of strings is an object s such that:
head(s) is a string, and
tail(s) is a stream of strings.
This is very similar to an inductive definition of lists of strings; the difference is that this definition specifies how to access the contents of the data structure—namely, via the
accessor functions
head
and
tail
—and what those contents may be, whereas the inductive definition specifies how to create the structure and what it may be created from.
Corecursion is related to coinduction, and can be used to compute particular instances of (possibly) infinite objects. As a programming technique, it is used most often in the context of
lazy programming languages, and can be preferable to recursion when the desired size or precision of a program's output is unknown. In such cases the program requires both a definition for an infinitely large (or infinitely precise) result, and a mechanism for taking a finite portion of that result. The problem of computing the first n
prime numbers is one that can be solved with a corecursive program (e.g.
here
Here is an adverb that means "in, on, or at this place". It may also refer to:
Software
* Here Technologies, a mapping company
* Here WeGo (formerly Here Maps), a mobile app and map website by Here Technologies, Here
Television
* Here TV (form ...
).
Types of recursion
Single recursion and multiple recursion
Recursion that contains only a single self-reference is known as , while recursion that contains multiple self-references is known as . 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
In computer science, tree traversal (also known as tree search and walking the tree) is a form of graph traversal and refers to the process of visiting (e.g. retrieving, updating, or deleting) each node in a tree data structure, exactly once. ...
, such as in a depth-first search.
Single recursion is often much more efficient than multiple recursion, and can generally be replaced by an iterative computation, running in linear time and requiring constant space. Multiple recursion, by contrast, may require exponential time and space, and is more fundamentally recursive, not being able to be replaced by iteration without an explicit stack.
Multiple recursion can sometimes be converted to single recursion (and, if desired, thence to iteration). For example, while computing the Fibonacci sequence naively entails multiple iteration, as each value requires two previous values, it can be computed by single recursion by passing two successive values as parameters. This is more naturally framed as corecursion, building up from the initial values, while tracking two successive values at each step – see
corecursion: examples. A more sophisticated example involves using a
threaded binary tree, which allows iterative tree traversal, rather than multiple recursion.
Indirect recursion
Most basic examples of recursion, and most of the examples presented here, demonstrate ''direct'' recursion, in which a function calls itself. ''Indirect'' recursion occurs when a function is called not by itself but by another function that it called (either directly or indirectly). For example, if ''f'' calls ''f,'' that is direct recursion, but if ''f'' calls ''g'' which calls ''f,'' then that is indirect recursion of ''f.'' Chains of three or more functions are possible; for example, function 1 calls function 2, function 2 calls function 3, and function 3 calls function 1 again.
Indirect recursion is also called
mutual recursion
In mathematics and computer science, mutual recursion is a form of recursion where two mathematical or computational objects, such as functions or datatypes, are defined in terms of each other. Mutual recursion is very common in functional progra ...
, which is a more symmetric term, though this is simply a difference of emphasis, not a different notion. That is, if ''f'' calls ''g'' and then ''g'' calls ''f,'' which in turn calls ''g'' again, from the point of view of ''f'' alone, ''f'' is indirectly recursing, while from the point of view of ''g'' alone, it is indirectly recursing, while from the point of view of both, ''f'' and ''g'' are mutually recursing on each other. Similarly a set of three or more functions that call each other can be called a set of mutually recursive functions.
Anonymous recursion
Recursion is usually done by explicitly calling a function by name. However, recursion can also be done via implicitly calling a function based on the current context, which is particularly useful for
anonymous functions, and is known as
anonymous recursion
In computer science, anonymous recursion is recursion which does not explicitly call a function by name. This can be done either explicitly, by using a higher-order function – passing in a function as an argument and calling it – or implicitly ...
.
Structural versus generative recursion
Some authors classify recursion as either "structural" or "generative". The distinction is related to where a recursive procedure gets the data that it works on, and how it processes that data:
Thus, the defining characteristic of a structurally recursive function is that the argument to each recursive call is the content of a field of the original input. Structural recursion includes nearly all tree traversals, including XML processing, binary tree creation and search, etc. By considering the algebraic structure of the natural numbers (that is, a natural number is either zero or the successor of a natural number), functions such as factorial may also be regarded as structural recursion.
is the alternative:
This distinction is important in
proving termination of a function.
* All structurally recursive functions on finite (
inductively defined) data structures can easily be shown to terminate, via
structural induction Structural induction is a proof method that is used in mathematical logic (e.g., in the proof of Łoś' theorem), computer science, graph theory, and some other mathematical fields. It is a generalization of mathematical induction over natural nu ...
: intuitively, each recursive call receives a smaller piece of input data, until a base case is reached.
* Generatively recursive functions, in contrast, do not necessarily feed smaller input to their recursive calls, so proof of their termination is not necessarily as simple, and avoiding
infinite loops requires greater care. These generatively recursive functions can often be interpreted as corecursive functions – each step generates the new data, such as successive approximation in Newton's method – and terminating this corecursion requires that the data eventually satisfy some condition, which is not necessarily guaranteed.
* In terms of
loop variants, structural recursion is when there is an obvious loop variant, namely size or complexity, which starts off finite and decreases at each recursive step.
* By contrast, generative recursion is when there is not such an obvious loop variant, and termination depends on a function, such as "error of approximation" that does not necessarily decrease to zero, and thus termination is not guaranteed without further analysis.
Implementation issues
In actual implementation, rather than a pure recursive function (single check for base case, otherwise recursive step), a number of modifications may be made, for purposes of clarity or efficiency. These include:
* Wrapper function (at top)
* Short-circuiting the base case, aka "Arm's-length recursion" (at bottom)
* Hybrid algorithm (at bottom) – switching to a different algorithm once data is small enough
On the basis of elegance, wrapper functions are generally approved, while short-circuiting the base case is frowned upon, particularly in academia. Hybrid algorithms are often used for efficiency, to reduce the overhead of recursion in small cases, and arm's-length recursion is a special case of this.
Wrapper function
A
wrapper function
A wrapper function is a function (another word for a ''subroutine'') in a software library or a computer program whose main purpose is to call a second subroutine or a system call with little or no additional computation. Wrapper functions are u ...
is a function that is directly called but does not recurse itself, instead calling a separate auxiliary function which actually does the recursion.
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. In languages that support
nested function
In computer programming, a nested function (or nested procedure or subroutine) is a function which is defined within another function, the ''enclosing function''. Due to simple recursive scope rules, a nested function is itself invisible outside ...
s, the auxiliary function can be nested inside the wrapper function and use a shared scope. In the absence of nested functions, auxiliary functions are instead a separate function, if possible private (as they are not called directly), and information is shared with the wrapper function by using
pass-by-reference
In a programming language, an evaluation strategy is a set of rules for evaluating expressions. The term is often used to refer to the more specific notion of a ''parameter-passing strategy'' that defines the kind of value that is passed to the f ...
.
Short-circuiting the base case
Short-circuiting the base case, also known as arm's-length recursion, consists of checking the base case ''before'' making a recursive call – i.e., checking if the next call will be the base case, instead of calling and then checking for the base case. Short-circuiting is particularly done for efficiency reasons, to avoid the overhead of a function call that immediately returns. Note that since the base case has already been checked for (immediately before the recursive step), it does not need to be checked for separately, but one does need to use a wrapper function for the case when the overall recursion starts with the base case itself. For example, in the factorial function, properly the base case is 0! = 1, while immediately returning 1 for 1! is a short circuit, and may miss 0; this can be mitigated by a wrapper function. The box shows
C code to shortcut factorial cases 0 and 1.
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 algorithms; this is illustrated below for a depth-first search. Short-circuiting on a tree corresponds to considering a leaf (non-empty node with no children) as the base case, rather than considering an empty node as the base case. If there is only a single base case, such as in computing the factorial, short-circuiting provides only savings.
Conceptually, short-circuiting can be considered to either have the same base case and recursive step, checking the base case only before the recursion, or it can be considered to have a different base case (one step removed from standard base case) and a more complex recursive step, namely "check valid then recurse", as in considering leaf nodes rather than Null nodes as base cases in a tree. Because short-circuiting has a more complicated flow, compared with the clear separation of base case and recursive step in standard recursion, it is often considered poor style, particularly in academia.
Depth-first search
A basic example of short-circuiting is given in
depth-first search (DFS) of a binary tree; see
binary trees section for standard recursive discussion.
The standard recursive algorithm for a DFS is:
* base case: If current node is Null, return false
* recursive step: otherwise, check value of current node, return true if match, otherwise recurse on children
In short-circuiting, this is instead:
* check value of current node, return true if match,
* otherwise, on children, if not Null, then recurse.
In terms of the standard steps, this moves the base case check ''before'' the recursive step. Alternatively, these can be considered a different form of base case and recursive step, respectively. Note that this requires a wrapper function to handle the case when the tree itself is empty (root node is Null).
In the case of a
perfect binary tree
In computer science, a binary tree is a k-ary k = 2 tree data structure in which each node has at most two children, which are referred to as the ' and the '. A recursive definition using just set theory notions is that a (non-empty) binary t ...
of height ''h,'' there are 2
''h''+1−1 nodes and 2
''h''+1 Null pointers as children (2 for each of the 2
''h'' leaves), so short-circuiting cuts the number of function calls in half in the worst case.
In C, the standard recursive algorithm may be implemented as:
bool tree_contains(struct node *tree_node, int i)
The short-circuited algorithm may be implemented as:
// Wrapper function to handle empty tree
bool tree_contains(struct node *tree_node, int i)
// Assumes tree_node != NULL
bool tree_contains_do(struct node *tree_node, int i)
Note the use of
short-circuit evaluation
A short circuit (sometimes abbreviated to short or s/c) is an electrical circuit that allows a current to travel along an unintended path with no or very low electrical impedance. This results in an excessive current flowing through the circuit. ...
of the Boolean && (AND) operators, so that the recursive call is made only if the node is valid (non-Null). Note that while the first term in the AND is a pointer to a node, the second term is a boolean, so the overall expression evaluates to a boolean. This is a common idiom in recursive short-circuiting. This is in addition to the short-circuit evaluation of the Boolean , , (OR) operator, to only check the right child if the left child fails. In fact, the entire
control flow
In computer science, control flow (or flow of control) is the order in which individual statements, instructions or function calls of an imperative program are executed or evaluated. The emphasis on explicit control flow distinguishes an ''im ...
of these functions can be replaced with a single Boolean expression in a return statement, but legibility suffers at no benefit to efficiency.
Hybrid algorithm
Recursive algorithms are often inefficient for small data, due to the overhead of repeated function calls and returns. For this reason efficient implementations of recursive algorithms often start with the recursive algorithm, but then switch to a different algorithm when the input becomes small. An important example is
merge sort
In computer science, merge sort (also commonly spelled as mergesort) is an efficient, general-purpose, and comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the order of equal elements is the same ...
, which is often implemented by switching to the non-recursive
insertion sort
Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time by comparisons. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. Ho ...
when the data is sufficiently small, as in the
tiled merge sort. Hybrid recursive algorithms can often be further refined, as in
Timsort
Timsort is a hybrid, stable sorting algorithm, derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data. It was implemented by Tim Peters in 2002 for use in the Python programming language. The algor ...
, derived from a hybrid merge sort/insertion sort.
Recursion versus iteration
Recursion and
iteration
Iteration is the repetition of a process in order to generate a (possibly unbounded) sequence of outcomes. Each repetition of the process is a single iteration, and the outcome of each iteration is then the starting point of the next iteration. ...
are equally expressive: recursion can be replaced by iteration with an explicit
call stack
In computer science, a call stack is a stack data structure that stores information about the active subroutines of a computer program. This kind of stack is also known as an execution stack, program stack, control stack, run-time stack, or m ...
, while iteration can be replaced with
tail recursion
In computer science, a tail call is a subroutine call performed as the final action of a procedure. If the target of a tail is the same subroutine, the subroutine is said to be tail recursive, which is a special case of direct recursion. Tail recur ...
. Which approach is preferable depends on the problem under consideration and the language used. In
imperative programming
In computer science, imperative programming is a programming paradigm of software that uses statements that change a program's state. In much the same way that the imperative mood in natural languages expresses commands, an imperative program ...
, 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
In computer science, functional programming is a programming paradigm where programs are constructed by applying and composing functions. It is a declarative programming paradigm in which function definitions are trees of expressions that m ...
recursion is preferred, with tail recursion optimization leading to little overhead. Implementing an algorithm using iteration may not be easily achievable.
Compare the templates to compute x
n defined by x
n = f(n, x
n-1) from x
base:
For an imperative language the overhead is to define the function, and for a functional language the overhead is to define the accumulator variable x.
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:
unsigned int factorial(unsigned int n)
Expressive power
Most
programming language
A programming language is a system of notation for writing computer programs. Most programming languages are text-based formal languages, but they may also be graphical. They are a kind of computer language.
The description of a programming ...
s in use today allow the direct specification of recursive functions and procedures. When such a function is called, the program's
runtime environment
In computer programming, a runtime system or runtime environment is a sub-system that exists both in the computer where a program is created, as well as in the computers where the program is intended to be run. The name comes from the compile t ...
keeps track of the various
instances of the function (often using a
call stack
In computer science, a call stack is a stack data structure that stores information about the active subroutines of a computer program. This kind of stack is also known as an execution stack, program stack, control stack, run-time stack, or m ...
, although other methods may be used). Every recursive function can be transformed into an iterative function by replacing recursive calls with
iterative control constructs and simulating the call stack with a
stack explicitly managed by the program.
Conversely, all iterative functions and procedures that can be evaluated by a computer (see
Turing completeness
In computability theory, a system of data-manipulation rules (such as a computer's instruction set, a programming language, or a cellular automaton) is said to be Turing-complete or computationally universal if it can be used to simulate any Tu ...
) can be expressed in terms of recursive functions; iterative control constructs such as
while loop
In most computer programming languages, a while loop is a control flow statement that allows code to be executed repeatedly based on a given Boolean condition. The ''while'' loop can be thought of as a repeating if statement.
Overview
The ' ...
s and
for loop
In computer science a for-loop or for loop is a control flow statement for specifying iteration. Specifically, a for loop functions by running a section of code repeatedly until a certain condition has been satisfied.
For-loops have two par ...
s are routinely rewritten in recursive form in
functional language
In computer science, functional programming is a programming paradigm where programs are constructed by applying and composing functions. It is a declarative programming paradigm in which function definitions are trees of expressions that ...
s. However, in practice this rewriting depends on
tail call elimination
In computer science, a tail call is a subroutine call performed as the final action of a procedure. If the target of a tail is the same subroutine, the subroutine is said to be tail recursive, which is a special case of direct recursion. Tail recu ...
, which is not a feature of all languages.
C,
Java
Java (; id, Jawa, ; jv, ꦗꦮ; su, ) is one of the Greater Sunda Islands in Indonesia. It is bordered by the Indian Ocean to the south and the Java Sea to the north. With a population of 151.6 million people, Java is the world's mos ...
, and
Python
Python may refer to:
Snakes
* Pythonidae, a family of nonvenomous snakes found in Africa, Asia, and Australia
** ''Python'' (genus), a genus of Pythonidae found in Africa and Asia
* Python (mythology), a mythical serpent
Computing
* Python (pro ...
are notable mainstream languages in which all function calls, including
tail call
In computer science, a tail call is a subroutine call performed as the final action of a procedure. If the target of a tail is the same subroutine, the subroutine is said to be tail recursive, which is a special case of direct recursion. Tail recur ...
s, may cause stack allocation that would not occur with the use of looping constructs; in these languages, a working iterative program rewritten in recursive form may
overflow the call stack, although tail call elimination may be a feature that is not covered by a language's specification, and different implementations of the same language may differ in tail call elimination capabilities.
Performance issues
In languages (such as
C and
Java
Java (; id, Jawa, ; jv, ꦗꦮ; su, ) is one of the Greater Sunda Islands in Indonesia. It is bordered by the Indian Ocean to the south and the Java Sea to the north. With a population of 151.6 million people, Java is the world's mos ...
) that favor iterative looping constructs, there is usually significant time and space cost associated with recursive programs, due to the overhead required to manage the stack and the relative slowness of function calls; in
functional languages
In computer science, functional programming is a programming paradigm where programs are constructed by applying and composing functions. It is a declarative programming paradigm in which function definitions are trees of expressions that m ...
, a function call (particularly a
tail call
In computer science, a tail call is a subroutine call performed as the final action of a procedure. If the target of a tail is the same subroutine, the subroutine is said to be tail recursive, which is a special case of direct recursion. Tail recur ...
) is typically a very fast operation, and the difference is usually less noticeable.
As a concrete example, the difference in performance between recursive and iterative implementations of the "factorial" example above depends highly on the
compiler
In computing, a compiler is a computer program that translates computer code written in one programming language (the ''source'' language) into another language (the ''target'' language). The name "compiler" is primarily used for programs tha ...
used. In languages where looping constructs are preferred, the iterative version may be as much as several
orders of magnitude
An order of magnitude is an approximation of the logarithm of a value relative to some contextually understood reference value, usually 10, interpreted as the base of the logarithm and the representative of values of magnitude one. Logarithmic dis ...
faster than the recursive one. In functional languages, the overall time difference of the two implementations may be negligible; in fact, the cost of multiplying the larger numbers first rather than the smaller numbers (which the iterative version given here happens to do) may overwhelm any time saved by choosing iteration.
Stack space
In some programming languages, the maximum size of the
call stack
In computer science, a call stack is a stack data structure that stores information about the active subroutines of a computer program. This kind of stack is also known as an execution stack, program stack, control stack, run-time stack, or m ...
is much less than the space available in the
heap, and recursive algorithms tend to require more stack space than iterative algorithms. Consequently, these languages sometimes place a limit on the depth of recursion to avoid
stack overflow
In software, a stack overflow occurs if the call stack pointer exceeds the stack bound. The call stack may consist of a limited amount of address space, often determined at the start of the program. The size of the call stack depends on many facto ...
s;
Python
Python may refer to:
Snakes
* Pythonidae, a family of nonvenomous snakes found in Africa, Asia, and Australia
** ''Python'' (genus), a genus of Pythonidae found in Africa and Asia
* Python (mythology), a mythical serpent
Computing
* Python (pro ...
is one such language. Note the caveat below regarding the special case of
tail recursion
In computer science, a tail call is a subroutine call performed as the final action of a procedure. If the target of a tail is the same subroutine, the subroutine is said to be tail recursive, which is a special case of direct recursion. Tail recur ...
.
Vulnerability
Because recursive algorithms can be subject to stack overflows, they may be vulnerable to
pathological
Pathology is the study of the causes and effects of disease or injury. The word ''pathology'' also refers to the study of disease in general, incorporating a wide range of biology research fields and medical practices. However, when used in th ...
or
malicious input. Some malware specifically targets a program's call stack and takes advantage of the stack's inherently recursive nature. Even in the absence of malware, a stack overflow caused by unbounded recursion can be fatal to the program, and
exception handling
In computing and computer programming, exception handling is the process of responding to the occurrence of ''exceptions'' – anomalous or exceptional conditions requiring special processing – during the execution of a program. In general, an ...
logic
Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of logical truths. It is a formal science investigating how conclusions follow from premise ...
may not prevent the corresponding
process
A process is a series or set of activities that interact to produce a result; it may occur once-only or be recurrent or periodic.
Things called a process include:
Business and management
*Business process, activities that produce a specific se ...
from being
terminated.
Multiply recursive problems
Multiply recursive problems are inherently recursive, because of prior state they need to track. One example is
tree traversal
In computer science, tree traversal (also known as tree search and walking the tree) is a form of graph traversal and refers to the process of visiting (e.g. retrieving, updating, or deleting) each node in a tree data structure, exactly once. ...
as in
depth-first search; though both recursive and iterative methods are used, they contrast with list traversal and linear search in a list, which is a singly recursive and thus naturally iterative method. Other examples include
divide-and-conquer algorithm
In computer science, divide and conquer is an algorithm design paradigm. A divide-and-conquer algorithm recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved dire ...
s such as
Quicksort
Quicksort is an efficient, general-purpose sorting algorithm. Quicksort was developed by British computer scientist Tony Hoare in 1959 and published in 1961, it is still a commonly used algorithm for sorting. Overall, it is slightly faster than ...
, and functions such as the
Ackermann function. All of these algorithms can be implemented iteratively with the help of an explicit
stack, but the programmer effort involved in managing the stack, and the complexity of the resulting program, arguably outweigh any advantages of the iterative solution.
Refactoring recursion
Recursive algorithms can be replaced with non-recursive counterparts. One method for replacing recursive algorithms is to simulate them using
heap memory
Memory management is a form of resource management applied to computer memory. The essential requirement of memory management is to provide ways to dynamically allocate portions of memory to programs at their request, and free it for reuse when ...
in place of
stack memory. An alternative is to develop a replacement algorithm entirely based on non-recursive methods, which can be challenging. For example, recursive algorithms for
matching wildcards
In computer science, an algorithm for matching wildcards (also known as globbing) is useful in comparing text strings that may contain wildcard syntax. Common uses of these algorithms include command-line interfaces, e.g. the Bourne shell or Mi ...
, such as
Rich Salz
InterNetNews (INN) is a Usenet news server package, originally released by Rich Salz in 1991, and presented at the Summer 1992 USENIX conference in San Antonio, Texas. It was the first news server with integrated NNTP functionality.
While pr ...
'
wildmat
wildmat is a pattern matching library developed by Rich Salz. Based on the wildcard syntax already used in the Bourne shell, wildmat provides a uniform mechanism for matching patterns across applications with simpler syntax than that typically ...
algorithm, were once typical. Non-recursive algorithms for the same purpose, such as the
Krauss matching wildcards algorithm In computer science, the Krauss wildcard-matching algorithm is a pattern matching algorithm. Based on the wildcard syntax in common use, e.g. in the Microsoft Windows command-line interface, the algorithm provides a non- recursive mechanism for mat ...
, have been developed to avoid the drawbacks of recursion and have improved only gradually based on techniques such as collecting
tests and
profiling performance.
Tail-recursive functions
Tail-recursive functions are functions in which all recursive calls are
tail call
In computer science, a tail call is a subroutine call performed as the final action of a procedure. If the target of a tail is the same subroutine, the subroutine is said to be tail recursive, which is a special case of direct recursion. Tail recur ...
s and hence do not build up any deferred operations. For example, the gcd function (shown again below) is tail-recursive. In contrast, the factorial function (also below) is not tail-recursive; because its recursive call is not in tail position, it builds up deferred multiplication operations that must be performed after the final recursive call completes. With a
compiler
In computing, a compiler is a computer program that translates computer code written in one programming language (the ''source'' language) into another language (the ''target'' language). The name "compiler" is primarily used for programs tha ...
or
interpreter that treats tail-recursive calls as
jumps rather than function calls, a tail-recursive function such as gcd will execute using constant space. Thus the program is essentially iterative, equivalent to using imperative language control structures like the "for" and "while" loops.
The significance of tail recursion is that when making a tail-recursive call (or any tail call), the caller's return position need not be saved on the
call stack
In computer science, a call stack is a stack data structure that stores information about the active subroutines of a computer program. This kind of stack is also known as an execution stack, program stack, control stack, run-time stack, or m ...
; when the recursive call returns, it will branch directly on the previously saved return position. Therefore, in languages that recognize this property of tail calls, tail recursion saves both space and time.
Order of execution
Consider these two functions:
Function 1
void recursiveFunction(int num)
Function 2
void recursiveFunction(int num)
Function 2 is function 1 with the lines swapped.
In the case of a function calling itself only once, instructions placed before the recursive call are executed once per recursion before any of the instructions placed after the recursive call. The latter are executed repeatedly after the maximum recursion has been reached.
Also note that the ''order'' of the print statements is reversed, which is due to the way the functions and statements are stored on the
call stack
In computer science, a call stack is a stack data structure that stores information about the active subroutines of a computer program. This kind of stack is also known as an execution stack, program stack, control stack, run-time stack, or m ...
.
Recursive procedures
Factorial
A classic example of a recursive procedure is the function used to calculate the
factorial of a
natural number
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called ''cardinal ...
:
:
The function can also be written as a
recurrence relation
In mathematics, a recurrence relation is an equation according to which the nth term of a sequence of numbers is equal to some combination of the previous terms. Often, only k previous terms of the sequence appear in the equation, for a parameter ...
:
:
:
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 :
:
The definition above translates straightforwardly to
functional programming language
In computer science, functional programming is a programming paradigm where programs are constructed by applying and composing functions. It is a declarative programming paradigm in which function definitions are trees of expressions that ...
s such as
Scheme; this is an example of iteration implemented recursively.
Greatest common divisor
The
Euclidean algorithm, which computes the
greatest common divisor
In mathematics, the greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers ''x'', ''y'', the greatest common divisor of ''x'' and ''y'' is ...
of two integers, can be written recursively.
''Function definition'':
:
Recurrence relation
In mathematics, a recurrence relation is an equation according to which the nth term of a sequence of numbers is equal to some combination of the previous terms. Often, only k previous terms of the sequence appear in the equation, for a parameter ...
for greatest common divisor, where
expresses the
remainder
In mathematics, the remainder is the amount "left over" after performing some computation. In arithmetic, the remainder is the integer "left over" after dividing one integer by another to produce an integer quotient ( integer division). In algeb ...
of
:
:
if
:
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. By maintaining its state entirely in the variables ''x'' and ''y'' and using a looping construct, the program avoids making recursive calls and growing the call stack.
The iterative algorithm requires a temporary variable, and even given knowledge of the Euclidean algorithm it is more difficult to understand the process by simple inspection, although the two algorithms are very similar in their steps.
Towers of Hanoi
![Tower of Hanoi](https://upload.wikimedia.org/wikipedia/commons/0/07/Tower_of_Hanoi.jpeg)
The Towers of Hanoi is a mathematical puzzle whose solution illustrates recursion. There are three pegs which can hold stacks of disks of different diameters. A larger disk may never be stacked on top of a smaller. Starting with ''n'' disks on one peg, they must be moved to another peg one at a time. What is the smallest number of steps to move the stack?
''Function definition'':
:
''Recurrence relation for hanoi'':
:
:
Example implementations:
Although not all recursive functions have an explicit solution, the Tower of Hanoi sequence can be reduced to an explicit formula.
Binary search
The
binary search
In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the ...
algorithm is a method of searching a
sorted array
A sorted array is an array data structure in which each element is sorted in numerical, alphabetical, or some other order, and placed at equally spaced addresses in computer memory. It is typically used in computer science to implement static l ...
for a single element by cutting the array in half with each recursive pass. The trick is to pick a midpoint near the center of the array, compare the data at that point with the data being searched and then responding to one of three possible conditions: the data is found at the midpoint, the data at the midpoint is greater than the data being searched for, or the data at the midpoint is less than the data being searched for.
Recursion is used in this algorithm because with each pass a new array is created by cutting the old one in half. The binary search procedure is then called recursively, this time on the new (and smaller) array. Typically the array's size is adjusted by manipulating a beginning and ending index. 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:
/*
Call binary_search with proper initial conditions.
INPUT:
data is an array of integers SORTED in ASCENDING order,
toFind is the integer to search for,
count is the total number of elements in the array
OUTPUT:
result of binary_search
*/
int search(int *data, int toFind, int count)
/*
Binary Search Algorithm.
INPUT:
data is a array of integers SORTED in ASCENDING order,
toFind is the integer to search for,
start is the minimum array index,
end is the maximum array index
OUTPUT:
position of the integer toFind within array data,
-1 if not found
*/
int binary_search(int *data, int toFind, int start, int end)
Recursive data structures (structural recursion)
An important application of recursion in computer science is in defining dynamic data structures such as
lists and
trees
In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are u ...
. Recursive data structures can dynamically grow to a theoretically infinite size in response to runtime requirements; in contrast, the size of a static array must be set at compile time.
"Recursive algorithms are particularly appropriate when the underlying problem or the data to be treated are defined in recursive terms."
The examples in this section illustrate what is known as "structural recursion". This term refers to the fact that the recursive procedures are acting on data that is defined recursively.
As long as a programmer derives the template from a data definition, functions employ structural recursion. That is, the recursions in a function's body consume some immediate piece of a given compound value.
Linked lists
Below is a C definition of a linked list node structure. Notice especially how the node is defined in terms of itself. The "next" element of ''struct node'' is a pointer to another ''struct node'', effectively creating a list type.
struct node
;
Because the ''struct node'' data structure is defined recursively, procedures that operate on it can be implemented naturally as recursive procedures. The ''list_print'' procedure defined below walks down the list until the list is empty (i.e., the list pointer has a value of NULL). For each node it prints the data element (an integer). In the C implementation, the list remains unchanged by the ''list_print'' procedure.
void list_print(struct node *list)
Binary trees
Below is a simple definition for a binary tree node. Like the node for linked lists, it is defined in terms of itself, recursively. There are two self-referential pointers: left (pointing to the left sub-tree) and right (pointing to the right sub-tree).
struct node
;
Operations on the tree can be implemented using recursion. Note that because there are two self-referencing pointers (left and right), tree operations may require two recursive calls:
// Test if tree_node contains i; return 1 if so, 0 if not.
int tree_contains(struct node *tree_node, int i)
At most two recursive calls will be made for any given call to ''tree_contains'' as defined above.
// Inorder traversal:
void tree_print(struct node *tree_node)
The above example illustrates an
in-order traversal
In computer science, tree traversal (also known as tree search and walking the tree) is a form of graph traversal and refers to the process of visiting (e.g. retrieving, updating, or deleting) each node in a tree data structure, exactly once. S ...
of the binary tree. A
Binary search tree
In computer science, a binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree data structure with the key of each internal node being greater than all the keys in the respective node's left subtree and ...
is a special case of the binary tree where the data elements of each node are in order.
Filesystem traversal
Since the number of files in a
filesystem
In computing, file system or filesystem (often abbreviated to fs) is a method and data structure that the operating system uses to control how data is Computer data storage, stored and retrieved. Without a file system, data placed in a storage me ...
may vary,
recursion
Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathemati ...
is the only practical way to traverse and thus enumerate its contents. Traversing a filesystem is very similar to that of
tree traversal
In computer science, tree traversal (also known as tree search and walking the tree) is a form of graph traversal and refers to the process of visiting (e.g. retrieving, updating, or deleting) each node in a tree data structure, exactly once. ...
, therefore the concepts behind tree traversal are applicable to traversing a filesystem. More specifically, the code below would be an example of a
preorder traversal of a filesystem.
import java.io.File;
public class FileSystem
This code is both recursion and
iteration
Iteration is the repetition of a process in order to generate a (possibly unbounded) sequence of outcomes. Each repetition of the process is a single iteration, and the outcome of each iteration is then the starting point of the next iteration. ...
- the files and directories are iterated, and each directory is opened recursively.
The "rtraverse" method is an example of direct recursion, whilst the "traverse" method is a wrapper function.
The "base case" scenario is that there will always be a fixed number of files and/or directories in a given filesystem.
Time-efficiency of recursive algorithms
The
time efficiency of recursive algorithms can be expressed in a
recurrence relation
In mathematics, a recurrence relation is an equation according to which the nth term of a sequence of numbers is equal to some combination of the previous terms. Often, only k previous terms of the sequence appear in the equation, for a parameter ...
of
Big O notation. They can (usually) then be simplified into a single Big-O term.
Shortcut rule (master theorem)
If the time-complexity of the function is in the form
Then the Big O of the time-complexity is thus:
* If
for some constant
, then
* If
, then
* If
for some constant
, and if
for some constant and all sufficiently large , then
where represents the number of recursive calls at each level of recursion, represents by what factor smaller the input is for the next level of recursion (i.e. the number of pieces you divide the problem into), and represents the work that the function does independently of any recursion (e.g. partitioning, recombining) at each level of recursion.
See also
*
Functional programming
In computer science, functional programming is a programming paradigm where programs are constructed by applying and composing functions. It is a declarative programming paradigm in which function definitions are trees of expressions that ...
*
Computational problem
In theoretical computer science, a computational problem is a problem that may be solved by an algorithm. For example, the problem of factoring
:"Given a positive integer ''n'', find a nontrivial prime factor of ''n''."
is a computational probl ...
*
Hierarchical and recursive queries in SQL
A hierarchical query is a type of SQL query that handles hierarchical model data. They are special cases of more general recursive fixpoint queries, which compute transitive closures.
In standard SQL:1999 hierarchical queries are implemented ...
*
Kleene–Rosser paradox
In mathematics, the Kleene–Rosser paradox is a paradox that shows that certain systems of formal logic are inconsistent, in particular the version of Haskell Curry's combinatory logic introduced in 1930, and Alonzo Church's original lambda ca ...
*
Open recursion
*
Recursion
Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathemati ...
*
Sierpiński curve
Sierpiński curves are a recursively defined sequence of continuous closed plane fractal curves discovered by Wacław Sierpiński, which in the limit n \to \infty completely fill the unit square: thus their limit curve, also called the Sierpiń ...
*
McCarthy 91 function
*
μ-recursive function
In mathematical logic and computer science, a general recursive function, partial recursive function, or μ-recursive function is a partial function from natural numbers to natural numbers that is "computable" in an intuitive sense – as well as i ...
s
*
Primitive recursive function
In computability theory, a primitive recursive function is roughly speaking a function that can be computed by a computer program whose loops are all "for" loops (that is, an upper bound of the number of iterations of every loop can be determined ...
s
*
Tak (function)
In computer science, the Tak function is a recursive function, named after Ikuo Takeuchi (竹内郁雄). It is defined as follows:
\tau (x,y,z) = \begin
\tau (\tau (x-1,y,z) ,\tau (y-1,z,x) ,\tau (z-1,x,y) ) & \text y Int
tarai x y z
, x < ...
Notes
References
* (viii+64 pages)
*
*
*
*
*
*
*
*
{{DEFAULTSORT:Recursion (Computer Science)
Theoretical computer science
Recursion
Computability theory
Articles with example pseudocode
Programming idioms
Subroutines