Recursion (computer science)

Recursion in computer science is a way of thinking about and solving problems. It is, in fact, one of the central ideas of computer science. [cite book
last = Epp
first = Susanna
title = Discrete Mathematics with Applications
year=1995
edition=2nd
page=427] Solving a problem using recursion means the solution depends on solutions to smaller instances of the same problem. [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 =1976]

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 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 of dynamic programming.

Virtually all programming languages 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, 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 in continuation-passing style; and conversely any recursive function can be expressed in terms of iteration.Fact|date=May 2008

To 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 and functional programming provide recursion as the only means of repetition directly available to the programmer. Such languages generally make tail 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 functions and Turing machines 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, fractals, and adaptive 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 an integer.

Function definition:

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, b₀ = 0

Recurrence relation for greatest common divisor, where "x % y" expresses the remainder of x / y:
gcd(x,y) = gcd(y, x % y)
gcd(x,0) = x

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. [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
last = Epp
first = Susanna
title = Discrete Mathematics with Applications
year=1995
edition=2nd
pages=427-430: The Tower of Hanoi] 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.

Function definition:
Recurrence relation for hanoi:
h_n = 2*h_n-1+1
h₁ = 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:

/* 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) { // Start = 0 (beginning index) // End = count - 1 (top index) return binary_search(data, toFind, 0, count-1); }

/* 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 =1976]

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. [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 lists

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{ int n; // some data struct node *next; // pointer to another 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.

void printList(LIST lst){ if (!isEmpty(lst)) // base case { printf("%d ", lst->n); // print integer followed by a space printList(lst->next); // recursive call

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{ int n; // some data struct node *left; // pointer to the left subtree struct node *right; // point to the right subtree};

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

void printTree(TREE t) { if (!isEmpty(t)) { // base case printTree(t->left); // go left printf("%d ", t->n); // print the integer followed by a space printTree(t->right); // go right

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 the Ackermann function and divide-and-conquer algorithms such as Quicksort. 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

void recursiveFunction(int num) { if (num < 5) { printf("%d ", num); recursiveFunction(num + 1);

Function 2 with swapped lines

void recursiveFunction(int num) { if (num < 5) { recursiveFunction(num + 1); printf("%d ", 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.

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] by Zeeshan Amjad