recursive function: a procedure or subroutine, implemented in a programming language, whose implementation references itself .
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. [1] Solving a problem using recursion means the solution depends on solutions to smaller instances of the same problem. [2]
"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." [3]
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”.
Tree created using the Logo programming language and relying heavily on recursion.Contents [hide]
1 Recursive algorithms
2 Recursive programming
2.1 Examples of recursively defined procedures (generative recursion)
2.1.1 Factorial
2.1.2 Fibonacci
2.1.3 Greatest common divisor
2.1.4 Towers of Hanoi
2.1.5 Binary search
2.2 Recursive data structures (structural recursion)
2.2.1 Linked lists
2.2.2 Binary trees
2.3 Recursion versus iteration
3 Tail-recursive functions
4 Order of function calling
4.1 Function 1
4.2 Function 2 with swapped lines
5 Direct and indirect recursion
6 See also
7 Notes and References
8 External links
[edit] 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,[citation needed] in continuation-passing style; and conversely any recursive function can be expressed in terms of iteration.[citation needed]
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.
[edit] 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".[4]
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.[5]
[edit] Examples of recursively defined procedures (generative recursion)
[edit] Factorial
A classic example of a recursive procedure is the function used to calculate the factorial of an integer.
Function definition:
Pseudocode (recursive):
function factorial is:input: integer n such that n >= 1output: [n × (n-1) × (n-2) × … × 1]
1. if n is 1, return 1
2. otherwise, return [ (n) × factorial(n-1) ]
end factorial
A recurrence relation is an equation that relates later terms in the sequence to earlier terms[6].
Recurrence relation for factorial:
bn = n * bn-1
b0 = 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):
;; 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);
}
This factorial function can also be described without using recursion by making use of the typical looping constructs found in imperative programming languages:
Pseudocode (iterative):
function factorial is:input: integer n such that n >= 1output: [n × (n-1) × (n-2) × … × 1]
1. create new variable called running_total with a value of 1
2. begin loop
1. if n < 1, exit loop
2. set running_total to (running_total × n)
3. decrement n
4. repeat loop
3. return running_total
end factorial
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.
Example implementations:
Scheme (programming language): C (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;
}
[edit] 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:
Pseudocode
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
Recurrence relation for Fibonacci:
bn = bn-1 + bn-2
b1 = 1, b0 = 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):
;; 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) ]
}
These implementations are 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.[7]
[edit] Greatest common divisor
Another famous recursive function is the Euclidean algorithm, used to compute the greatest common divisor of two integers.
Function definition:
Pseudocode (recursive):
function gcd is:
input: integer x, integer y such that x >= y and y > 0
1. if y is 0, return x
2. otherwise, return [ cgd( y, (remainder of x/y) ) ]
end gcd
Recurrence relation for greatest common divisor, where "x % y&q