Recursion is a way of thinking about and solving problems. In fact, Recursion_ is one of the central ideas of computer science. Solving a problem using recursion means the solution depends on solutions to smaller instances of the same problem.... is a way of thinking about and solving problems. In fact, recursion
Recursion (computer science)
Recursion is a way of thinking about and solving problems. In fact, Recursion_ is one of the central ideas of computer science. Solving a problem using recursion means the solution depends on solutions to smaller instances of the same problem.... is one of the central ideas of computer science. Solving a problem using recursion means the solution depends on solutions to smaller instances of the same problem.
"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 high-level computer programming languages support recursion by allowing a function to call itself within the program text.
Discussion
Ask a question about 'Recursion (computer science)'
Start a new discussion about 'Recursion (computer science)'
Recursion is a way of thinking about and solving problems. In fact, Recursion_ is one of the central ideas of computer science. Solving a problem using recursion means the solution depends on solutions to smaller instances of the same problem.... is a way of thinking about and solving problems. In fact, recursion
Recursion (computer science)
Recursion is a way of thinking about and solving problems. In fact, Recursion_ is one of the central ideas of computer science. Solving a problem using recursion means the solution depends on solutions to smaller instances of the same problem.... is one of the central ideas of computer science. Solving a problem using recursion means the solution depends on solutions to smaller instances of the same problem.
"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 high-level computer programming languages support recursion by allowing a function to call itself within the program text. Imperative languages define looping constructs like “while” and “for” loops that are used to perform repetitive actions. Some functional programming languages do not define any looping constructs but rely solely on recursion to repeatedly call code. Computability theory
Computability theory (computer science)
In computer science, computability theory is the branch of the theory of computation that studies which problems are computationally solvable using different Model of computation.... has proven that these recursive only languages are mathematically equivalent to the imperative languages, meaning they can solve the same kinds of problems even without the typical control structures like “while” and “for”.
Recursive algorithms
A common method of simplification is to divide a problem into sub-problems of the same type. This is known as dialecting. As a computer programming
Computer programming
Computer programming is the process of writing, testing, debugging/troubleshooting, and maintaining the source code of computer programs. This source code is written in a programming language.... technique, this is called divide and conquer
Divide and conquer algorithm
In computer science, divide and conquer is an important algorithm design paradigm based on multi-branched recursion. A divide and conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same type, until these become simple enough to be solved directly.... , and it is key to the design of many important algorithms, as well as a fundamental part of dynamic programming
Dynamic programming
In mathematics and computer science, dynamic programming is a method of solving problems that exhibit the properties of overlapping subproblems and optimal substructure .... .
A programming language is a machine-readable artificial language designed to express computations that can be performed by a machine, particularly a computer.... s in use today allow the direct specification of recursive functions and procedures. When such a function is called, the computer (for most languages on most stack-based architectures) or the language implementation keeps track of the various instances of the function (on many architectures, by using a call stack
Call stack
In computer science, a call stack is a dynamic Stack data structure that stores information about the active subroutines of a computer program.... , although other methods may be used). Conversely, every recursive function can be transformed into an iterative function by using a stack
Stack (data structure)
In computer science, a stack is an abstract data type and data structure based on the principle of LIFO . Stacks are used extensively at every level of a modern computer system.... .
Most (but not all) functions and procedures that can be evaluated by a computer can be expressed in terms of a recursive function (without having to use pure iteration
In functional programming, continuation-passing style is a style of programming in which control flow is passed explicitly in the form of a continuation.... ; conversely any recursive function can be expressed in terms of (pure) iteration, since recursion in itself is iterative too. In order to evaluate a function by means of recursion, it has to be defined as a function of itself (e.g. the factorial n! = n * (n - 1)! , where 0! is defined as 1). Clearly thus, not all function evaluations lend themselves to a recursive approach. In general, all non-infinite functions can be described recursively directly; infinite functions (e.g. the series for e = 1/1! + 2/2! + 3/3!...) need an extra 'stopping criterion', e.g. the number of iterations, or the number of significant digits, because otherwise recursive iteration would result in an endless loop
Infinite loop
An infinite loop is a sequence of instructions in a computer program which control flow#Loops endlessly, either due to the loop having no terminating condition or having one that can never be met.... .
To give a very literal example of this: If an unknown word is seen in a book, the reader can make a note of the current page number and put the note on a stack (which is empty so far). The reader can then look the new word up and, while reading on the subject, may find yet another unknown word. The page number of this word is also written down and put on top of the stack. At some point an article is read that does not require any explanation. The reader then returns to the previous page number and continues reading from there. This is repeated, sequentially removing the topmost note from the stack. Finally, the reader returns to the original book. This is a recursive approach.
Logic programming is, in its broadest sense, the use of mathematical logic for computer programming. In this view of logic programming, which can be traced at least as far back as John McCarthy 's [1958] Advice taker proposal, logic is used as a purely Declarative programming language representation language, and a automated theorem proving o... and functional programming
Functional programming
In computer science, functional programming is a programming paradigm that treats computation as the evaluation of function s and avoids program state and immutable object data.... provide recursion as the only means of repetition directly available to the programmer. Such languages generally make tail recursion
Tail recursion
In computer science, tail recursion is a special case of Recursion_ in which the last operation of the function, the tail call, is a recursive call.... as efficient as iteration, letting programmers express other repetition structures (such as Scheme's map and for) in terms of recursion.
The theory of computation is the branch of computer science that deals with whether and how efficiently problems can be solved on a model of computation, using an algorithm.... , with the theoretical equivalence of µ-recursive functions and Turing machine
Turing machine
Turing machines are basic abstract symbol-manipulating devices which, despite their simplicity, can be adapted to simulate the logic of any computer algorithm.... s at the foundation of ideas about the universality of the modern computer.
Recursive programming
Creating a recursive procedure essentially requires defining a "base case", and then defining rules to break down more complex cases into the base case. Key to a recursive procedure is that with each recursive call, the problem domain must be reduced in such a way that eventually the base case is arrived at.
Some authors classify recursion as either "generative" or "structural". The distinction is made based on where the procedure gets the data that it works on. If the data comes from a data structure like a list, then the procedure is "structurally recursive"; otherwise, it is "generatively recursive".
Many well-known recursive algorithms generate an entirely new piece of data from the given data and recur on it. HTDP (How To Design Programs) refers to this kind as generative recursion. Examples of generative recursion include: gcd
Greatest common divisor
In mathematics, the greatest common divisor , sometimes known as the greatest common factor or highest common factor , of two non-zero integers, is the largest positive integer that divisor both numbers without remainder.... , quicksort
Quicksort
Quicksort is a well-known sorting algorithm developed by C. A. R. Hoare that, average performance, makes comparisons to sort n items. However, in the Best, worst and average case, it makes comparisons.... , binary search, mergesort, Newton's method
Newton's method
In numerical analysis, Newton's method is perhaps the best known method for finding successively better approximations to the zeroes of a Real number-valued function .... , fractal
Fractal
A fractal is generally "a rough or fragmented Shape that can be split into parts, each of which is a reduced-size copy of the whole," a property called self-similarity.... s, and adaptive integration.
Examples of recursively defined procedures (generative recursion)
Factorial
A classic example of a recursive procedure is the function used to calculate the factorial
Factorial
In mathematics, the factorial of a negative and non-negative numbers integer n, denoted by n!, is the Product of all positive integers less than or equal to n.... of an integer
Integer
The integers are natural numbers including 0 and their negative and non-negative numberss . They are numbers that can be written without a fractional or decimal component, and fall within the set .... .
Pseudocode is a compact and informal high-level description of a computer programming algorithm that uses the structural conventions of some programming language, but is intended for human reading rather than machine reading.... (recursive):
function factorial is: input: integer n such that n >= 0 output: [n × (n-1) × (n-2) × … × 1]
1. if n is 0, return 1
2. otherwise, return [ n × factorial(n-1) ]
end factorial
In mathematics, a recurrence relation is an equation that defines a sequence recursion: each term of the sequence is defined as a Function of the preceding terms.... is an equation that relates later terms in the sequence to earlier terms.
This factorial function can also be described without using recursion by making use of the typical looping constructs found in imperative programming languages:
Pseudocode is a compact and informal high-level description of a computer programming algorithm that uses the structural conventions of some programming language, but is intended for human reading rather than machine reading.... (iterative):
function factorial is: input: integer n such that n >= 0 output: [n × (n-1) × (n-2) × … × 1]
1. create new variable called running_total with a value of 1
2. begin loop
1. if n is 0, exit loop
2. setrunning_total to (running_total × n)
3. decrementn
4. repeat loop
3. returnrunning_total end factorial
Scheme, however, is a functional programming language and does not define any looping constructs. It relies solely upon recursion to perform all looping. Because Scheme is tail-recursive, a recursive procedure can be defined that implements the factorial procedure as an iterative process — meaning that it uses constant space but linear time.
In mathematics, the Fibonacci numbers are a sequence of numbers named after Leonardo of Pisa, known as Fibonacci . Fibonacci's 1202 book Liber Abaci introduced the sequence to Western European mathematics, although the sequence had been previously described in Indian mathematics.... s. The first few elements of this sequence are: 0, 1, 1, 2, 3, 5, 8, 13, 21...
Pseudocode is a compact and informal high-level description of a computer programming algorithm that uses the structural conventions of some programming language, but is intended for human reading rather than machine reading....
function fib is:
input: integer n such that n >= 0
1. if n is 0, return 0
2. if n is 1, return 1
3. otherwise, return [ fib(n-1) + fib(n-2) ]
end fib
In mathematics, a recurrence relation is an equation that defines a sequence recursion: each term of the sequence is defined as a Function of the preceding terms.... for Fibonacci:
bn = bn-1 + bn-2
b1 = 1, b0 = 0
This Fibonacci algorithm is especially bad because each time the function is executed, it will make two function calls to itself each of which in turn makes two more function calls and so on until they "bottom out" at 1 or 0. This is an example of "tree recursion", and grows exponentially in time and linearly in space requirements.
In number theory, the Euclidean algorithm is an algorithm to determine the greatest common divisor of two elements of any Euclidean domain . Its major significance is that it does not require factorization the two integers, and it is also significant in that it is one of the oldest algorithms known, dating back to the ancient Greeks.... , used to compute the greatest common divisor
Greatest common divisor
In mathematics, the greatest common divisor , sometimes known as the greatest common factor or highest common factor , of two non-zero integers, is the largest positive integer that divisor both numbers without remainder.... of two integers.
Function definition:
Pseudocode is a compact and informal high-level description of a computer programming algorithm that uses the structural conventions of some programming language, but is intended for human reading rather than machine reading.... (recursive):
function gcd is:
input: integer x, integer y such that x >= y and y > 0
1. if y is 0, returnx
2. otherwise, return [ gcd( y, (remainder of x/y) ) ]
end gcd
Recurrence relation for greatest common divisor, where expresses the remainder of :
Computing the recurrence relation for x = 27 and y = 9:
gcd(27, 9) = gcd(9, 27 % 9)
= gcd(9, 0)
= 9
Computing the recurrence relation for x = 259 and y = 111:
Notice that the "recursive" algorithm above is in fact merely tail-recursive, which means it is equivalent to an iterative algorithm. Below is the same algorithm using explicit iteration. It does not accumulate a chain of deferred operations; rather, its state is maintained entirely in the variables x and y. Its "number of steps grows the as the logarithm of the numbers involved."
Pseudocode is a compact and informal high-level description of a computer programming algorithm that uses the structural conventions of some programming language, but is intended for human reading rather than machine reading.... (iterative):
function gcd is: input: integer x, integer y such that x >= y and y > 0
1. create new variable called remainder
2. begin loop
1. if y is zero, exit loop
2. setremainder to the remainder of x/y
3. set x to y
4. set y to remainder
5. repeat loop
3. returnx end gcd
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
For a full discussion of this problem's description, history and solution see the main article or one of the many references. Simply put the problem is this: given three pegs, one with a set of N disks of increasing size, determine the minimum (optimal) number of steps it take to move all the disks from their initial position to another peg without placing a larger disk on top of a smaller one.
Pseudocode is a compact and informal high-level description of a computer programming algorithm that uses the structural conventions of some programming language, but is intended for human reading rather than machine reading.... (recursive):
function hanoi is: input: integer n, such that n >= 1
1. if n is 1 then return 1
2. return [2 * [call hanoi(n-1)] + 1]
end hanoi
Although not all recursive functions have an explicit solution, the Tower of Hanoi sequence can be reduced to an explicit formula.
The binary search algorithm is a method of searching an ordered array for a single element by cutting the array in half with each 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, 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:
/*
Call binary_search with proper initial conditions.
INPUT:
data is a 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. Recursive data structures can dynamically grow to a theoretically infinite size in response to runtime requirements; in contrast, a static array's size requirements 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.
In computer science, a linked list is one of the fundamental data structures, and can be used to implement other data structures. It consists of a sequence of node s, each containing arbitrary data Field s and one or two reference s pointing to the next and/or previous nodes.... s
Below is a simple definition of a linked list node. Notice especially how the node is defined in terms of itself. The "next" element of struct node is a pointer to a struct node.
struct node
;
// LIST is simply a synonym for struct node * (aka syntactic sugar).
typedef struct node *LIST;
Procedures that operate on the LIST data structure can be implemented naturally as a recursive procedure because the data structure it operates on (LIST) is defined recursively. The printList procedure defined below walks down the list until the list is empty (NULL), for each node it prints the data element (an integer). In the C implementation, the list remains unchanged by the printList procedure.
In computer science, a binary tree is a Tree in which each node has at most two child node. Typically the child nodes are called left and right.... s
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
;
// TREE is simply a synonym for struct node * (aka syntactic sugar).
typedef struct node *TREE;
Operations on the tree can be implemented using recursion. Note that because there are two self-referencing pointers (left and right), that tree operations will require two recursive calls. For a similar example see the Fibonacci function and explanation above.
In computer science, tree-traversal refers to the process of visiting each node in a tree data structure, exactly once, in a systematic way. Such traversals are classified by the order in which the nodes are visited.... of the binary tree. A Binary search tree
Binary search tree
In computer science, a binary search tree is a binary tree data structurewhich has the following properties:* Each node has a distinct value.... is a special case of the binary tree where the data elements of each node are in order.
Recursion versus iteration
In the "factorial" example the iterative implementation is likely to be slightly faster in practice than the recursive one. This is almost definite for the Euclidean Algorithm implementation. This result is typical, because iterative functions do not pay the "function-call overhead" as many times as recursive functions, and that overhead is relatively high in many languages. (Note that an even faster implementation for the factorial function on small integers is to use a lookup table
Lookup table
In computer science, a lookup table is a data structure, usually an array or associative array, often used to replace a runtime computation with a simpler array indexing operation.... .)
There are other types of problems whose solutions are inherently recursive, because they need to keep track of prior state. One example is tree traversal
Tree traversal
In computer science, tree-traversal refers to the process of visiting each node in a tree data structure, exactly once, in a systematic way. Such traversals are classified by the order in which the nodes are visited.... ; others include the Ackermann function
Ackermann function
In computability theory, the Ackermann function or Ackermann?P?ter function is a simple example of a computable function that is not Primitive recursive function.... and divide-and-conquer algorithms such as Quicksort
Quicksort
Quicksort is a well-known sorting algorithm developed by C. A. R. Hoare that, average performance, makes comparisons to sort n items. However, in the Best, worst and average case, it makes comparisons.... . All of these algorithms can be implemented iteratively with the help of a stack
Stack (data structure)
In computer science, a stack is an abstract data type and data structure based on the principle of LIFO . Stacks are used extensively at every level of a modern computer system.... , but the need for the stack arguably nullifies the advantages of the iterative solution.
Another possible reason for choosing an iterative rather than a recursive algorithm is that in today's programming languages, the stack space available to a thread is often much less than the space available in the heap, and recursive algorithms tend to require more stack space than iterative algorithms. However, see the caveat below regarding the special case of tail recursion
Tail recursion
In computer science, tail recursion is a special case of Recursion_ in which the last operation of the function, the tail call, is a recursive call.... .
Tail-recursive functions
Tail-recursive functions are functions ending in a recursive call that does not build-up any deferred operations. For example, the gcd function (re-shown below) is tail-recursive; however, the factorial function (also re-shown below) is "augmenting recursive" because it builds up deferred operations that must be performed even after the final recursive call completes. With a compiler
Compiler
A compiler is a computer program that transforms source code written in a programming language into another computer language . The most common reason for wanting to transform source code is to create an executable program.... that automatically optimizes tail-recursive calls, a tail-recursive function such as gcd will execute using constant space. Thus the process it generates is iterative and equivalent to using imperative language control structures like the "for" and "while" loops.
In computer science, tail recursion is a special case of Recursion_ in which the last operation of the function, the tail call, is a recursive call.... :
Augmenting recursion:
//INPUT: Integers x, y such that x >= y and y > 0
int gcd(int x, int y)
//INPUT: n is an Integer such that n >= 1
int fact(int n)
The significance of tail recursion is that when making a tail-recursive call, the caller's return position need not be saved on the call stack
Call stack
In computer science, a call stack is a dynamic Stack data structure that stores information about the active subroutines of a computer program.... ; when the recursive call returns, it will branch directly on the previously saved return position. Therefore, on compilers which support tail-recursion optimization, tail recursion saves both space and time.
Order of function calling
The order of calling a function may change the execution of a function, see this example in C
C (programming language)
C is a general-purpose computer programming language originally developed in 1972 by Dennis Ritchie at the Bell Telephone Laboratories to implement the Unix operating system.... language:
Function 1
void recursiveFunction(int num)
Function 2 with swapped lines
void recursiveFunction(int num)
Direct and indirect recursion
Direct recursion is when function calls itself. Indirect recursion is when (for example) function A calls function B, function B calls function C, and then function C calls function A. Long chains and branches are possible, see Recursive descent parser
Recursive descent parser
A recursive descent parser is a top-down parsing built from a set of Mutual recursion procedures where each such procedure usually implements one of the production rules of the formal grammar.... .
Mutual recursion is a form of recursion where two mathematical or computational functions are defined in terms of each other.For instance, consider two functions even? and odd? defined as follows:...
The primitive recursive functions are defined using primitive Recursion and function composition as central operations and are a strict subset of the ?-recursive functions ....
In computer science, functional programming is a programming paradigm that treats computation as the evaluation of function s and avoids program state and immutable object data....
In mathematics, the Kleene-Rosser paradox is a paradox that shows Alonzo Church's original lambda calculus is inconsistent. It is similar to Russell's paradox, in that it is a statement that asserts its own falsehood if and only if it is true; that is, it is a negation....
In computability theory, the Ackermann function or Ackermann?P?ter function is a simple example of a computable function that is not Primitive recursive function....
Sierpinski curves are a recursively defined sequence of Geometric continuity closed plane fractal curves discovered by Waclaw Sierpinski, which in the limit completely fill the unit square: thus their limit curve, also called the Sierpinski curve, is an example of a space-filling curve....
