 FACTOID # 14: North Carolina has a larger Native American population than North Dakota, South Dakota and Montana combined.

 Home Encyclopedia Statistics States A-Z Flags Maps FAQ About

 WHAT'S NEW

SEARCH ALL

Search encyclopedia, statistics and forums:

(* = Graphable)

Encyclopedia > Recursion (computer science)

A common method of simplification is to divide a problem into subproblems of the same type. As a computer programming technique, this is called divide and conquer and is key to the design of many important algorithms, as well as being a fundamental part of dynamic programming. Computer code (HTML with JavaScript) in a tool that uses colors to help the developer see the function of each piece of code. ... In computer science, divide and conquer (D&C) is an important algorithm design paradigm. ... In computer science, dynamic programming is a method for reducing the runtime of algorithms exhibiting the properties of overlapping subproblems and optimal substructure, described below. ...

Recursion in computer programming defines a function in terms of itself. One example application of recursion is in 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. A parser is a computer program or a component of a program that analyses the grammatical structure of an input, with respect to a given formal grammar, a process known as parsing. ...

## Contents

### Recursive algorithms

A common method of simplification is to divide a problem into subproblems of the same type. As a computer programming technique, this is called divide and conquer and is key to the design of many important algorithms, as well as being a fundamental part of dynamic programming. Computer code (HTML with JavaScript) in a tool that uses colors to help the developer see the function of each piece of code. ... In computer science, divide and conquer (D&C) is an important algorithm design paradigm. ... In computer science, dynamic programming is a method for reducing the runtime of algorithms exhibiting the properties of overlapping subproblems and optimal substructure, described below. ...

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 stack, although other methods may be used). Conversely, every recursive function can be transformed into an iterative function by using a stack. Computer code (HTML with JavaScript) in a tool that uses syntax highlighting (colors) to help the developer see the function of each piece of code. ... Stack in computing refers to: Stack (data structure) Stack-based memory allocation as opposed to Heap-based memory allocation in computing architecture. ...

Any function that can be evaluated by a computer can be expressed in terms of recursive functions, without use of iteration, and conversely. Iteration is the repetition of a process, typically within a computer program. ...

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. Logic programming (sometimes called logical programming) is a programming paradigm that is claimed to be declarative (i. ... Functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions. ... In computer science, tail recursion is a special case of recursion that can be transformed into an iteration. ... Scheme is a functional programming language and a dialect of Lisp. ...

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. Computation can be defined as finding a solution to a problem from given inputs by means of an algorithm. ... In mathematical logic and computer science, the recursive functions are a class of functions from natural numbers to natural numbers which are computable in some intuitive sense. ... An artistic representation of a Turing Machine . ...

John McCarthy's 91 function is another example of a recursively defined function. John McCarthy (born September 4, 1927, in Boston, Massachusetts, sometimes known affectionately as Uncle John McCarthy), is a prominent computer scientist and notable Usenetter who received the Turing Award in 1971 for his major contributions to the field of Artificial Intelligence. ... In discrete mathematics, the McCarthy 91 function is a recursive function which returns 91 for all positive integer arguments n â‰¤ 101 and returns for n > 101. ...

The Quicksort and Mergesort algorithms are also commonly done using recursion, which allows them to run in an average of O(n log n) time. Quicksort in action on a list of random numbers. ... In computer science, merge sort or mergesort is a sort algorithm for rearranging lists (or any other data structure that can only be accessed sequentially, e. ...

Many operations involving tree data structures also use recursion, as it is often quite difficult to iteratively traverse a tree of unknown length.

In addition, some numerical methods for finding approximate solutions to mathematical equations use recursion. In Newton's method, for example, an approximate root of a function is provided as initial input to the method. The calculated result (output) is then used as input to the method, with the process repeated until a sufficiently accurate value is obtained. In numerical analysis, Newtons method (or the Newton-Raphson method) is an efficient algorithm for finding approximations to the zeros (or roots) of a real-valued function. ...

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 is analytic, and is the most common design for parsers for computer languages.

Another, similar form is generative recursion. This is synthetic. 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.

The commonly used example (using the Euphoria programming language, in this case) is the function used to calculate the factorial of an integer: Euphoria is an interpreted programming language conceived and created by Robert Craig of Rapid Deployment Software. ... In mathematics, the factorial of a natural number n is the product of all positive integers less than and equal to n. ... The integers consist of the positive natural numbers (1, 2, 3, â€¦), their negatives (âˆ’1, âˆ’2, âˆ’3, ...) and the number zero. ...

` function Factorial ( integer X ) if X < 0 then return "Invalid argument" end if if X = 0 then return 1 end if return Factorial(X-1) * X end function `

Although the recursive factorial function is calculating the same value as the iterative function below, depending on language implementation, recursive function may consume additional memory for each call. I.e. factorial(20) may use ten times more memory than factorial(10). The Scheme language is especially efficient at recursion, but naive recursive implementations in earlier versions of C were very notoriously wasteful. Nowadays, only the most performance-hungry software, such as video games, missile guidance systems and graphics card drivers, should worry about whether recursion will be slower than iterative for or while loops. Scheme is a functional programming language and a dialect of Lisp. ... The C Programming Language, Brian Kernighan and Dennis Ritchie, the original edition that served for many years as an informal specification of the language The C programming language is a standardized imperative computer programming language developed in the early 1970s by Dennis Ritchie for use on the Unix operating system. ...

Recursive functions are often regarded as more elegant than alternative implementations and they are usually shorter and simpler. For example, above function coded in the same language without recursion would be as follows:

` function Factorial ( integer X ) integer temp_result if X < 0 then return "Invalid argument" end if temp_result = 1 for i = 1 to X do temp_result *= i end for return temp_result end function `

In this particular example the iterative implementation is slightly faster in practice than the recursive one. (Note that an even faster implementation for the Factorial function is that of using a lookup table.) There are other types of problems that seem to have an inherently recursive solution, i.e. they need to keep track of prior state. One example is tree traversal, which is possible to implement iteratively with the help of a stack, but the need for the stack arguably defeats the purpose of the iterative solution. Another possible reason for choosing an iterative rather than a recursive algorithm is that in today's programming languages, thread stacks are often much smaller than memory available in the heap, and recursive algorithms tend to require more stack space than iterative algorithms. In computer science, a lookup table is a data structure, usually an array or associative array, used to replace a runtime computation with a simpler lookup operation. ... In computer science, tree traversal is the process of visiting each node in a tree data structure. ... Look up Stack in Wiktionary, the free dictionary This is a disambiguation page: a list of articles associated with the same title. ...

### recursion vs. iteration

While recursion can simplify the solution of a problem, often resulting in shorter, more easily understood source code, it is often less efficient, in terms of both time and space, than iterative solutions. There are some methods to convert recursive algorithm into an iterative algorith using a loop and branching structure.

## Recursive functions

Main article: recursive function

Functions whose domains can be recursively defined can be given recursive definitions patterned after the recursive definition of their domain. In mathematical logic and computer science, the recursive functions are a class of functions from natural numbers to natural numbers which are computable in some intuitive sense. ...

The canonical example of a recursively defined function is the following definition of the factorial function f(n): In mathematics, the factorial of a natural number n is the product of all positive integers less than and equal to n. ...

` f(0) = 1 f(n) = n * f(n − 1) for any natural number n > 0 `

Given this definition, also called a recurrence relation, we work out f(3) as follows:

` f(3) = 3 * f(3 − 1)  = 3 * f(2)  = 3 * 2 * f(2 − 1)  = 3 * 2 * f(1)  = 3 * 2 * 1 * f(1 − 1)  = 3 * 2 * 1 * f(0)  = 3 * 2 * 1 * 1  = 6 `

A Sierpinski triangle â€”a confined recursion of triangles to form a geometric lattice. ...

Share your thoughts, questions and commentary here
Press Releases | Feeds | Contact