Recursion (computer science)

Recursion in computer programming defines a function in terms of itself. One example application of recursion is in recursive descent parsers for programming languages. The great advantage of recursion is that an infinite set of possible sentences, designs, or other data can be defined, parsed, or produced by a finite computer program.

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

Recursive algorithms

A common method of simplification is to divide a problem into sub-problems of the same type. 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 being 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, in continuation-passing style; and conversely any recursive function can be expressed in terms of iteration.

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 mu-recursive functions and Turing machines at the foundation of ideas about the universality of the modern computer.

Recursive programming

One basic form of recursive computer program is to define one or a few base cases, and then define rules to break down other cases into the base case. This analytic method is a common design for parsers for computer languages; see Recursive descent parser.

Another, similar form is generative, or synthetic, recursion. In this scheme, the computer uses rules to assemble cases, and starts by selecting a base case. This scheme is often used when a computer must design something automatically, such as code, a machine part or some other data.

Examples of Recursively Defined Procedures

Factorial

A classic example of a recursive procedure is the function used to calculate the factorial of an integer.

Function definition: $fact(n)={\begin{cases}1&{\mbox{if }}n=0\\n\times fact(n-1)&{\mbox{if }}n>0\\\end{cases}}$

A recurrence relation is an equation that relates later terms in the sequence to earlier terms.
Recurrence relation for factorial:
b_n = n * b_n-1
b₀ = 1

Computing the recurrence relation for n = 4:
b4 = 4 * b3 = 4 * 3 * b2 = 4 * 3 * 2 * b1 = 4 * 3 * 2 * 1 * b0 = 4 * 3 * 2 * 1 * 1 = 4 * 3 * 2 * 1 = 4 * 3 * 2 = 4 * 6 = 4 * 6 = 24

Example Implementations:

Scheme (programming language):	C (programming language):	Pascal (programming language):
;; Input: Integer n such that n >= 1 (define (fact n) (if (= n 1) 1 (* n (fact (- n 1)))))	//INPUT: n is an Integer such that n >= 1. int fact(int n) { if (n == 1) return 1; else return n * fact(n - 1); }	{INPUT: x is an Integer such that x >= 1} function Factorial(x: integer): integer; begin if x = 1 then Factorial := 1 else Factorial := x * Factorial(x-1); end

These factorial procedures can also be described in C (programming language) and Pascal (programming language) without using recursion. These procedures make use of the typical looping constructs found in imperative programming languages. Scheme (programming language), 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.

Scheme (programming language):	C (programming language):	Pascal (programming language):
;; Input: Integer n such that n >= 1 (define (fact n) (fact-iter 1 n)) (define (fact-iter prd n) (if (= n 1) prd (fact-iter (* prd n) (- n 1))))	//INPUT: n is an Integer such that n > 0. int fact(int n) { int prd = 1; while(n >= 1) { prd *= n; n--; } return prd; }	{INPUT: x is an Integer such that x >= 1} function Factorial(x: integer): integer; var i, tmp: integer; begin tmp := 1; for i := 1 to x do tmp := tmp * i Factorial := tmp end

Fibonacci

Another well known recursive sequence is the Fibonacci numbers. The first few elements of this sequence are: 0, 1, 1, 2, 3, 5, 8, 13, 21...

Function definition: $fib(n)={\begin{cases}0&{\mbox{if }}n=0\\1&{\mbox{if }}n=1\\fib(n-1)+fib(n-2)&{\mbox{if }}n>=2\\\end{cases}}$

Recurrence relation for Fibonacci:
b_n = b_n-1 + b_n-2
b₁ = 1, b₀ = 0

Computing the recurrence relation for n = 4:
b4 = b3 + b2 = b2 + b1 + b1 + b0 = b1 + b0 + 1 + 1 + 0 = 1 + 0 + 1 + 1 + 0 = 3

Example Implementations:

Scheme (programming language):	C (programming language):	Pascal (programming language):
;; n is an integer such that n >= 0 (define (fib n) (cond ((= n 0) 0) ((= n 1) 1) (else (+ (fib (- n 1)) (fib (- n 2))))))	//INPUT: n is an integer such that n >= 0 int fib(int n) { if (n == 0) return 0; else if (n == 1) return 1; else return fib(n-1) + fib(n-2); }	{INPUT: x is an Integer such that x >= 0} function Fib(x: integer): integer; begin if x = 0 then Fib := 0 else if x = 1 then Fib := 1 else Fib := Fib(x-1) + Fib(x-2) end

These implementations are especially bad. That is because there are 2 recursive calls. This version of Fibonacci demonstrates, in fact, typical "tree recursion" and grows exponentially in time and linearly in space requirements.

Greatest Common Divisor

Another comparison that even more clearly demonstrates the relative "elegance" of recursive functions is the Euclidean algorithm, used to compute the greatest common divisor of two integers.

Using C (programming language):

 int gcd(int x, int y)
 {
   if (y == 0)
      return x;
   else
      return gcd(y, x % y);
 }

Below is the same algorithm using an iterative approach:

Using C (programming language):

 int gcd(int x, int y)
 {
     int r;

     while (y != 0) {
         r = x % y;
         x = y;
         y = r;
     }
     return 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 they are very similar in their steps.

In simple case a recursive function calls itself, in complex cases function A calls function B, function B calls function C, function C calls function A. More long chain and branches may be possible, for example, for Recursive descent parser.

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.
   
   INTPUT: 
        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)/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

An important application of recursion in computer science is in defining dynamic data structures such as Lists and Trees.

"Recursive algorithms are particularly appropriate when the underlying problem or the data to be treated are defined in recursive terms."

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. The "List" data structure can now 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.

 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
     }
 }

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

Main article: Tail recursion

Tail-recursive functions are functions ending in a recursive call. For example, the following C function to locate a value in a linked list is tail-recursive, because the last thing it does is call itself:

 struct node {
     int data;
     struct node *next;
 }
 
 struct node *find_value(struct node *head, int value)
 {
     if (head == NULL)
       return NULL;
     if (head->data == value)
       return head;
     return find_value(head->next, value);
 }

The Euclidean Algorithm function, following a similar structure, is also tail-recursive. On the other hand, the Factorial function used as an example in the previous section is not tail-recursive, because after it receives the result of the recursive call, it must multiply that result by x before returning to its caller. That kind of function is sometimes called augmenting recursive.

The Factorial function can be turned into a tail-recursive function:

 function Factorial(acc: integer, x: integer): integer;
 begin
   if x <= 1 then
     Factorial := acc
   else
     Factorial := Factorial(x * acc, x - 1);
 end

Function should then be called by Factorial(1, x).

Notice that a single function may be both tail-recursive and augmenting recursive, such as this function to count the odd integers in a linked list:

 int count_odds(struct node *head)
 {
     if (head == NULL)
       return 0;
     if (head->data % 2 == 1)
       return count_odds(head->next) + 1;  /* augmenting recursion */
     return count_odds(head->next);  /* tail recursion */
 }

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\n", num); 
       recursiveFunction(num+1);    
    }
 }

Function 2 with swapped lines

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

See also

• Kleene-Rosser paradox
• McCarthy 91 function
• Recursion

External links

• Harold Abelson and Gerald Sussman: "Structure and Interpretation Of Computer Programs"
• IBM DeveloperWorks: "Mastering Recursive Programming"
• David S. Touretzky: "Common Lisp: A Gentle Introduction to Symbolic Computation"
• Matthias Felleisen: "How To Design Programs: An Introduction to Computing and Programming"