- Recursion (computer science)
is a way of thinking about and solving problems. It is, in fact, one of the central ideas of computer science. [Recursion in computer science*cite book*] Solving a problem using recursion means the solution depends on solutions to smaller instances of the same problem. [

last = Epp

first = Susanna

title = Discrete Mathematics with Applications

year=1995

edition=2nd

page=427*cite book*]

last = Graham

first = Ronald

coauthors = Donald Knuth, Oren Patashnik

title = Concrete Mathematics

year=1990

pages=Chapter 1: Recurrent Problems

url=http://www-cs-faculty.stanford.edu/~knuth/gkp.html"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." [

*cite book*]

last = Wirth

first = Niklaus

title = Algorithms + Data Structures = Programs

pages = 126

publisher=Prentice-Hall

year =1976Most 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 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 technique, this is called divide and conquer, and it is key to the design of many important algorithms, as well as a fundamental part ofdynamic programming .Virtually all

programming language 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 acall stack , although other methods may be used). Conversely, every recursive function can be transformed into an iterative function by using a stack.Any function that can be evaluated by a computer can be expressed in terms of recursive functions without the use of

iteration ,Fact|date=May 2008 incontinuation-passing style ; and conversely any recursive function can be expressed in terms of iteration.Fact|date=May 2008To make a very literal example out 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.

Some languages designed for

logic programming andfunctional programming provide recursion as the only means of repetition directly available to the programmer. Such languages generally maketail recursion as efficient as iteration, letting programmers express other repetition structures (such as Scheme's`map`

and`for`

) in terms of recursion.Recursion is deeply embedded in the

theory of computation , with the theoretical equivalence ofμ-recursive function s andTuring machine 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". [

*cite book*]

last = Felleisen

first = Matthias

authorlink =

coauthors = Robert Bruce Findler, Matthew Flatt, Shriram Krishnamurthi

title = How to Design Programs: An Introduction to Computing and Programming

publisher = MIT Press

date = 2001

location = Cambridge, MASS

pages = Part V "Generative Recursion"

url = http://www.htdp.org/2003-09-26/Book/curriculum-Z-H-31.html

doi =

id =

isbn =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,

quicksort ,binary search ,mergesort ,Newton's method ,fractal s, andadaptive integration . [*Citation*]

last = Felleisen

first = Matthias

contribution = Developing Interactive Web Programs

year = 2002

title = Advanced Functional Programming: 4th International School

editor-last = Jeuring

editor-first = Johan

volume =

pages = 108

place = Oxford, UK

publisher = Springer

id = .**Examples of recursively defined procedures (generative recursion)****Factorial**A classic example of a recursive procedure is the function used to calculate the

factorial of aninteger .Function definition: $fact(n)\; =\; egin\{cases\}\; 1\; mbox\{if\; \}\; n\; =\; 0\; \backslash \; n\; imes\; fact(n-1)\; mbox\{if\; \}\; n\; 0\; \backslash \; end\{cases\}$

This factorial function can also be described without using recursion by making use of the typical looping constructs found in imperative programming languages:

Recurrence relation for Fibonacci:

b_{n}= b_{n-1}+ b_{n-2}

b_{1}= 1, b_{0}= 0Recurrence relation for greatest common divisor, where "x % y" expresses the remainder of x / y:

gcd(x,y) = gcd(y, x % y)

gcd(x,0) = xThe 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. [

*cite book*] [

last = Graham

first = Ronald

coauthors = Donald Knuth, Oren Patashnik

title = Concrete Mathematics

year=1990

pages=Chapter 1, Section 1.1: The Tower of Hanoi

url=http://www-cs-faculty.stanford.edu/~knuth/gkp.html*cite book*] 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.

last = Epp

first = Susanna

title = Discrete Mathematics with Applications

year=1995

edition=2nd

pages=427-430: The Tower of HanoiFunction definition: $hanoi(n)\; =\; egin\{cases\}\; 1\; mbox\{if\; \}\; n\; =\; 1\; \backslash \; 2\; *\; hanoi(n-1)\; +\; 1\; mbox\{if\; \}\; n\; 1\backslash \; end\{cases\}$

Recurrence relation for hanoi:

h_{n}= 2*h_{n-1}+1

h_{1}= 1**Binary search**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:

/* 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) { //Get the midpoint. int mid = start + (end - start)/2; //Integer division //Stop condition. if (start > end) return -1; else if (data [mid] = toFind) //Found? return mid; else if (data [mid] > toFind) //Data is greater than toFind, search lower half return binary_search(data, toFind, start, mid-1); else //Data is less than toFind, search upper half return binary_search(data, toFind, mid+1, 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." [

*cite book*]

last = Wirth

first = Niklaus

title = Algorithms + Data Structures = Programs

pages = p127

publisher=Prentice-Hall

year =1976The 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. [

*Citation*]

last = Felleisen

first = Matthias

contribution = Developing Interactive Web Programs

year = 2002

title = Advanced Functional Programming: 4th International School

editor-last = Jeuring

editor-first = Johan

volume =

pages = 108

place = Oxford, UK

publisher = Springer

id = .Linked list sBelow 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.

// 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.

Binary tree sBelow 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).

// 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.

The above example illustrates an in-order traversal of the binary tree. A

Binary search tree 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 .)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 ; others include theAckermann function anddivide-and-conquer algorithm s such asQuicksort . All of these algorithms can be implemented iteratively with the help of a stack, 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-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 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.

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 ; 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 language:

**Function 1****Function 2 with swapped lines****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 .**ee also***

Mutual recursion

*Anonymous recursion

*μ-recursive function

*Primitive recursive function

*Functional programming

*Kleene-Rosser paradox

*McCarthy 91 function

*Ackermann function

*Sierpiński curve **Notes and References****External links*** [

*http://mitpress.mit.edu/sicp/full-text/book/book.html Harold Abelson and Gerald Sussman: "Structure and Interpretation Of Computer Programs"*]

* [*http://www-128.ibm.com/developerworks/linux/library/l-recurs.html IBM DeveloperWorks: "Mastering Recursive Programming"*]

* [*http://www.cs.cmu.edu/~dst/LispBook/ David S. Touretzky: "Common Lisp: A Gentle Introduction to Symbolic Computation"*]

* [*http://www.htdp.org/2003-09-26/Book/ Matthias Felleisen: "How To Design Programs: An Introduction to Computing and Programming"*]

* [*http://www.codeproject.com/KB/cpp/Recursion_Prmr_CPP_01.aspx Recursion Primer Using C++: Part 1*] byZeeshan Amjad

*Wikimedia Foundation.
2010.*