Incomputer science,recursion is a method of solving acomputational problem where the solution depends on solutions to smaller instances of the same problem.[1][2] Recursion solves suchrecursive problems by usingfunctions that call themselves from within their own code. The approach can be applied to many types of problems, and recursion is one of the central ideas of computer science.[3]
The power of recursion evidently lies in the possibility of defining aninfinite set of objects by a finitestatement. 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.
— Niklaus Wirth,Algorithms + Data Structures = Programs, 1976[4]
Most computerprogramming languages support recursion by allowing a function to call itself from within its own code. Somefunctional programming languages (for instance,Clojure)[5] do not define any built-in looping constructs, and instead rely solely on recursion. It is proved incomputability theory that these recursion-only languages areTuring complete; this means that they are as powerful (they can be used to solve the same problems) asimperative languages based on control structures such aswhile andfor.
Repeatedly calling a function from within itself may cause thecall stack to have a size equal to the sum of the input sizes of all involved calls. It follows that, for problems that can be solved easily by iteration, recursion is generally lessefficient, and, for certain problems, algorithmic or compiler-optimization techniques such astail call optimization may improve computational performance over a naive recursive implementation.[citation needed]
 | This sectionneeds additional citations forverification. Please helpimprove this article byadding citations to reliable sources in this section. Unsourced material may be challenged and removed.(November 2025) (Learn how and when to remove this message) |
The development ofrecursion in computer science grew out ofmathematical logic and later became an essential part ofprogramming language design.[6] The early work done byChurch,Gödel,Kleene, andTuring on recursive function andcomputability laid the groundwork that made recursion possible in programming languages.[6] Recursion has been used by mathematicians for a long time, but it only became a practical tool for programming in the late 1950s and early 1960s.[7] Key figures such asJohn McCarthy and theALGOL 60 design committee contributed to introducing recursion into programming.[7]
John McCarthy took the first steps by creating the programming languageLISP in 1960.[8] In his paperRecursive Functions of Symbolic Expressions and Their Computation by Machine, Part I, McCarthy showed that recursion could be core in a programming language that works with symbols by processing them step by step.[8] In LISP, recursion could be used in functions using simple rules, and there was also a way to evaluate them in the language.[8] This demonstrated that recursion was a practical way to write programs and that it also describes the process of computation.[6] Therefore, LISP became one of the first programming languages to use recursion as a main feature, and later on also influenced other languages that followed.[7]
During that time, recursion was also added toALGOL 60.[9] TheReport on the Algorithmic Language ALGOL 60, which was published in 1960, was the outcome of an international attempt at designing a standard language.[9] Allowing procedures to call themselves was one of the new important features of the language.[7] Before that, onlyloops were allowed to be used by programmers, so it was a significant change.[7] Recursion allowed programmers to describe algorithms in a more natural and flexible way.[7]
The definition of a recursivefunction is typically divided into two parts: one or more base case(s) and one or more recursive case(s).[10] This structure mirrors the logic ofmathematical induction, which is a proof technique where proving the base case(s) and the inductive step ensures that a given theorem holds for all valid inputs.
The base case specifies input values for which the function can provide a result directly, without any further recursion.[11] These are typically the simplest or smallest possible inputs (which can be solved trivially), allowing a computation to terminate. Base cases are essential because they prevent infinite regress. In other words, they define a stopping condition that terminates the recursion.
An example is computing thefactorial of an integer n, which is the product of all integers from 0 to n. For this problem, the definition 0! = 1 is a base case. Without it, the recursion may continue indefinitely, leading to non-termination or evenstack overflow errors in actual implementations.
Designing a correct base case is crucial for both theoretical and practical reasons. Some problems have a natural base case (e.g., the empty list is a base case in some recursive list-processing functions), while others require an additional parameter to provide a stopping criterion (e.g., using a depth counter in recursivetree traversal).
In recursivecomputer programming, omitting the base case or defining it incorrectly may result in unintended infinite recursion. In a study, researchers showed that many students struggle to identify appropriate base cases.[11]
The recursive case describes how to break down a problem into smaller sub-problems of the same form.[11] Each recursive step transforms the input so that it approaches a base case, ensuring progress toward termination. If the reduction step fails to progress toward a base case, the algorithm can get trapped in aninfinite loop.
In thefactorial example, the recursive case is defined as:
n! = n * (n-1)!, n > 0
Here, each invocation of the function decreases the input n by 1. Thus, it ensures that the recursion eventually reaches the base case of n = 0.
The recursive case is analogous to the inductive step in a proof byinduction: it assumes that the function works for a smaller instance and then extends this assumption to the current input. Recursive definitions and algorithms thus closely parallel inductive arguments inmathematics, and their correctness often relies on similar reasoning techniques.
There are several practical applications of recursion that follow the base case and recursive case structure. These are widely used to solve complex problems in computer science.
Manycomputer programs must process or generate an arbitrarily large quantity ofdata. Recursion is a technique for representing data whose exact size is unknown to theprogrammer: the programmer can specify this data with aself-referential definition. There are two types of self-referential definitions: inductive andcoinductive definitions.
An inductively defined recursive data definition is one that specifies how to construct instances of the data. For example,linked lists can be defined inductively (here, usingHaskell syntax):
dataListOfStrings=EmptyList|ConsStringListOfStrings
The code above specifies a list of strings to be either empty, or a structure that contains a string and a list of strings. The self-reference in the definition permits the construction of lists of any (finite) number of strings.
Another example of inductivedefinition is thenatural numbers (or positiveintegers):
A natural number is either 1 or n+1, where n is a natural number.
Similarly recursivedefinitions are often used to model the structure ofexpressions andstatements in programming languages. Language designers often express grammars in a syntax such asBackus–Naur form; here is such a grammar, for a simple language of arithmetic expressions with multiplication and addition:
<expr>::=<number> | (<expr> *<expr>) | (<expr> +<expr>)
This says that an expression is either a number, a product of two expressions, or a sum of two expressions. By recursively referring to expressions in the second and third lines, the grammar permits arbitrarily complicated arithmetic expressions such as(5 * ((3 * 6) + 8)), with more than one product or sum operation in a single expression.
A coinductive data definition is one that specifies the operations that may be performed on a piece of data; typically, self-referential coinductive definitions are used for data structures of infinite size.
A coinductive definition of infinitestreams of strings, given informally, might look like this:
A stream of strings is an object s such that: head(s) is a string, and tail(s) is a stream of strings.
This is very similar to an inductive definition of lists of strings; the difference is that this definition specifies how to access the contents of the data structure—namely, via theaccessor functionshead andtail—and what those contents may be, whereas the inductive definition specifies how to create the structure and what it may be created from.
Corecursion is related to coinduction, and can be used to compute particular instances of (possibly) infinite objects. As a programming technique, it is used most often in the context oflazy programming languages, and can be preferable to recursion when the desired size or precision of a program's output is unknown. In such cases the program requires both a definition for an infinitely large (or infinitely precise) result, and a mechanism for taking a finite portion of that result. The problem of computing the first nprime numbers is one that can be solved with a corecursive program (e.g.here).
Recursion that contains only a single self-reference is known assingle recursion, while recursion that contains multiple self-references is known asmultiple recursion. Standard examples of single recursion include list traversal, such as in a linear search, or computing the factorial function, while standard examples of multiple recursion includetree traversal, such as in a depth-first search.
Single recursion is often much more efficient than multiple recursion, and can generally be replaced by an iterative computation, running in linear time and requiring constant space. Multiple recursion, by contrast, may require exponential time and space, and is more fundamentally recursive, not being able to be replaced by iteration without an explicit stack.
Multiple recursion can sometimes be converted to single recursion (and, if desired, thence to iteration). For example, while computing the Fibonacci sequence naively entails multiple iteration, as each value requires two previous values, it can be computed by single recursion by passing two successive values as parameters. This is more naturally framed as corecursion, building up from the initial values, while tracking two successive values at each step – seecorecursion: examples. A more sophisticated example involves using athreaded binary tree, which allows iterative tree traversal, rather than multiple recursion.
Most basic examples of recursion, and most of the examples presented here, demonstratedirect recursion, in which a function calls itself.Indirect recursion occurs when a function is called not by itself but by another function that it called (either directly or indirectly). For example, iff callsf, that is direct recursion, but iff callsg which callsf, then that is indirect recursion off. Chains of three or more functions are possible; for example, function 1 calls function 2, function 2 calls function 3, and function 3 calls function 1 again.
Indirect recursion is also calledmutual recursion, which is a more symmetric term, though this is simply a difference of emphasis, not a different notion. That is, iff callsg and theng callsf, which in turn callsg again, from the point of view off alone,f is indirectly recursing, while from the point of view ofg alone, it is indirectly recursing, while from the point of view of both,f andg are mutually recursing on each other. Similarly a set of three or more functions that call each other can be called a set of mutually recursive functions.
Recursion is usually done by explicitly calling a function by name. However, recursion can also be done via implicitly calling a function based on the current context, which is particularly useful foranonymous functions, and is known asanonymous recursion.
Some authors classify recursion as either "structural" or "generative". The distinction is related to where a recursive procedure gets the data that it works on, and how it processes that data:
[Functions that consume structured data] typically decompose their arguments into their immediate structural components and then process those components. If one of the immediate components belongs to the same class of data as the input, the function is recursive. For that reason, we refer to these functions as (STRUCTURALLY) RECURSIVE FUNCTIONS.
— Felleisen, Findler, Flatt, and Krishnaurthi,How to Design Programs, 2001[14]
Thus, the defining characteristic of a structurally recursive function is that the argument to each recursive call is the content of a field of the original input. Structural recursion includes nearly all tree traversals, including XML processing, binary tree creation and search, etc. By considering the algebraic structure of the natural numbers (that is, a natural number is either zero or the successor of a natural number), functions such as factorial may also be regarded as structural recursion.
Generative recursion is the alternative:
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, andadaptive integration.
— Matthias Felleisen,Advanced Functional Programming, 2002[15]
This distinction is important inproving termination of a function.
In actual implementation, rather than a pure recursive function (single check for base case, otherwise recursive step), a number of modifications may be made, for purposes of clarity or efficiency. These include:
On the basis of elegance, wrapper functions are generally approved, while short-circuiting the base case is frowned upon, particularly in academia. Hybrid algorithms are often used for efficiency, to reduce the overhead of recursion in small cases, and arm's-length recursion is a special case of this.
Awrapper function is a function that is directly called but does not recurse itself, instead calling a separate auxiliary function which actually does the recursion.
Wrapper functions can be used to validate parameters (so the recursive function can skip these), perform initialization (allocate memory, initialize variables), particularly for auxiliary variables such as "level of recursion" or partial computations formemoization, and handle exceptions and errors. In languages that supportnested functions, the auxiliary function can be nested inside the wrapper function and use a shared scope. In the absence of nested functions, auxiliary functions are instead a separate function, if possible private (as they are not called directly), and information is shared with the wrapper function by usingpass-by-reference.
| Ordinary recursion | Short-circuit recursion |
|---|---|
intfac1(intn){if(n<=0){return1;}else{returnfac1(n-1)*n;}} | intfac2(intn){// assert(n >= 2);if(n==2){return2;}else{returnfac2(n-1)*n;}}intfac2wrapper(intn){if(n<=1){return1;}else{returnfac2(n);}} |
Short-circuiting the base case, also known asarm's-length recursion, consists of checking the base casebefore making a recursive call – i.e., checking if the next call will be the base case, instead of calling and then checking for the base case. Short-circuiting is particularly done for efficiency reasons, to avoid the overhead of a function call that immediately returns. Note that since the base case has already been checked for (immediately before the recursive step), it does not need to be checked for separately, but one does need to use a wrapper function for the case when the overall recursion starts with the base case itself. For example, in the factorial function, properly the base case is 0! = 1, while immediately returning 1 for 1! is a short circuit, and may miss 0; this can be mitigated by a wrapper function. The box showsC code to shortcut factorial cases 0 and 1.
Short-circuiting is primarily a concern when many base cases are encountered, such as Null pointers in a tree, which can be linear in the number of function calls, hence significant savings forO(n) algorithms; this is illustrated below for a depth-first search. Short-circuiting on a tree corresponds to considering a leaf (non-empty node with no children) as the base case, rather than considering an empty node as the base case. If there is only a single base case, such as in computing the factorial, short-circuiting provides onlyO(1) savings.
Conceptually, short-circuiting can be considered to either have the same base case and recursive step, checking the base case only before the recursion, or it can be considered to have a different base case (one step removed from standard base case) and a more complex recursive step, namely "check valid then recurse", as in considering leaf nodes rather than Null nodes as base cases in a tree. Because short-circuiting has a more complicated flow, compared with the clear separation of base case and recursive step in standard recursion, it is often considered poor style, particularly in academia.[16]
A basic example of short-circuiting is given indepth-first search (DFS) of a binary tree; seebinary trees section for standard recursive discussion.
The standard recursive algorithm for a DFS is:
In short-circuiting, this is instead:
In terms of the standard steps, this moves the base case checkbefore the recursive step. Alternatively, these can be considered a different form of base case and recursive step, respectively. Note that this requires a wrapper function to handle the case when the tree itself is empty (root node is Null).
In the case of aperfect binary tree of heighth, there are 2h+1−1 nodes and 2h+1 Null pointers as children (2 for each of the 2h leaves), so short-circuiting cuts the number of function calls in half in the worst case.
In C, the standard recursive algorithm may be implemented as:
booltree_contains(structBinaryTree*node,inti){if(!node){returnfalse;// base case}elseif(node->data==i){returntrue;}else{returntree_contains(node->left,i)||tree_contains(node->right,i);}}
The short-circuited algorithm may be implemented as:
#include<assert.h>// Wrapper function to handle empty treebooltree_contains(structBinaryTree*node,inti){if(!node){returnfalse;// empty tree}else{returntree_contains_aux(node,i);// call auxiliary function}}// Assumes node != NULLbooltree_contains_aux(structBinaryTree*node,inti){assert(node);if(node->data==i){returntrue;// found}else{// recursereturn(node->left&&tree_contains_aux(node->left,i))||(node->right&&tree_contains_aux(node->right,i));}}
Note the use ofshort-circuit evaluation of the Boolean && (AND) operators, so that the recursive call is made only if the node is valid (non-Null). Note that while the first term in the AND is a pointer to a node, the second term is a Boolean, so the overall expression evaluates to a Boolean. This is a common idiom in recursive short-circuiting. This is in addition to the short-circuit evaluation of the Boolean || (OR) operator, to only check the right child if the left child fails. In fact, the entirecontrol flow of these functions can be replaced with a single Boolean expression in a return statement, but legibility suffers at no benefit to efficiency.
Recursive algorithms are often inefficient for small data, due to the overhead of repeated function calls and returns. For this reason efficient implementations of recursive algorithms often start with the recursive algorithm, but then switch to a different algorithm when the input becomes small. An important example ismerge sort, which is often implemented by switching to the non-recursiveinsertion sort when the data is sufficiently small, as in thetiled merge sort. Hybrid recursive algorithms can often be further refined, as inTimsort, derived from a hybrid merge sort/insertion sort.
Recursion anditeration are equally expressive: recursion can be replaced by iteration with an explicitcall stack, while iteration can be replaced withtail recursion. Which approach is preferable depends on the problem under consideration and the language used. Inimperative programming, iteration is preferred, particularly for simple recursion, as it avoids the overhead of function calls and call stack management, but recursion is generally used for multiple recursion. By contrast, infunctional languages recursion is preferred, with tail recursion optimization leading to little overhead. Implementing an algorithm using iteration may not be easily achievable.
Compare the templates to compute xn defined by xn = f(n, xn-1) from xbase:
function recursive(n)if n == basereturn xbaseelsereturn f(n, recursive(n - 1)) | function iterative(n) x = xbasefor i = base + 1 to n x = f(i, x)return x |
For an imperative language the overhead is to define the function, and for a functional language the overhead is to define the accumulator variable x.
For example, afactorial function may be implemented iteratively inC by assigning to a loop index variable and accumulator variable, rather than by passing arguments and returning values by recursion:
unsignedintfactorial(unsignedintn){unsignedintproduct=1;// empty product is 1while(n>0){product*=n;--n;}returnproduct;}
Mostprogramming languages in use today allow the direct specification of recursive functions and procedures. When such a function is called, the program'sruntime environment keeps track of the variousinstances of the function (often using acall stack, although other methods may be used). Every recursive function can be transformed into an iterative function by replacing recursive calls withiterative control constructs and simulating the call stack with astack explicitly managed by the program.[17][18]
Conversely, all iterative functions and procedures that can be evaluated by a computer (seeTuring completeness) can be expressed in terms of recursive functions; iterative control constructs such aswhile loops andfor loops are routinely rewritten in recursive form infunctional languages.[19][20] However, in practice this rewriting depends ontail call elimination, which is not a feature of all languages.C,Java, andPython are notable mainstream languages in which all function calls, includingtail calls, may cause stack allocation that would not occur with the use of looping constructs; in these languages, a working iterative program rewritten in recursive form mayoverflow the call stack, although tail call elimination may be a feature that is not covered by a language's specification, and different implementations of the same language may differ in tail call elimination capabilities.
In languages (such asC andJava) that favor iterative looping constructs, there is usually significant time and space cost associated with recursive programs, due to the overhead required to manage the stack and the relative slowness of function calls; infunctional languages, a function call (particularly atail call) is typically a very fast operation, and the difference is usually less noticeable.
As a concrete example, the difference in performance between recursive and iterative implementations of the "factorial" example above depends highly on thecompiler used. In languages where looping constructs are preferred, the iterative version may be as much as severalorders of magnitude faster than the recursive one. In functional languages, the overall time difference of the two implementations may be negligible; in fact, the cost of multiplying the larger numbers first rather than the smaller numbers (which the iterative version given here happens to do) may overwhelm any time saved by choosing iteration.
In some programming languages, the maximum size of thecall stack is much less than the space available in theheap, and recursive algorithms tend to require more stack space than iterative algorithms. Consequently, these languages sometimes place a limit on the depth of recursion to avoidstack overflows;Python is one such language.[21] Note the caveat below regarding the special case oftail recursion.
Because recursive algorithms can be subject to stack overflows, they may be vulnerable topathological ormalicious input.[22] Some malware specifically targets a program's call stack and takes advantage of the stack's inherently recursive nature.[23] Even in the absence of malware, a stack overflow caused by unbounded recursion can be fatal to the program, andexception handlinglogic may not prevent the correspondingprocess from beingterminated.[24]
Multiply recursive problems are inherently recursive, because of prior state they need to track. One example istree traversal as indepth-first search; though both recursive and iterative methods are used,[25] they contrast with list traversal and linear search in a list, which is a singly recursive and thus naturally iterative method. Other examples includedivide-and-conquer algorithms such asQuicksort, and functions such as theAckermann function. All of these algorithms can be implemented iteratively with the help of an explicitstack, but the programmer effort involved in managing the stack, and the complexity of the resulting program, arguably outweigh any advantages of the iterative solution.
Recursive algorithms can be replaced with non-recursive counterparts.[26] One method for replacing recursive algorithms is to simulate them usingheap memory in place ofstack memory.[27] An alternative is to develop a replacement algorithm entirely based on non-recursive methods, which can be challenging.[28] For example, recursive algorithms formatching wildcards, such asRich Salz'wildmat algorithm,[29] were once typical. Non-recursive algorithms for the same purpose, such as theKrauss matching wildcards algorithm, have been developed to avoid the drawbacks of recursion[30] and have improved only gradually based on techniques such as collectingtests andprofiling performance.[31]
Tail-recursive functions are functions in which all recursive calls aretail calls and hence do not build up any deferred operations. For example, the gcd function (shown again below) is tail-recursive. In contrast, the factorial function (also below) isnot tail-recursive; because its recursive call is not in tail position, it builds up deferred multiplication operations that must be performed after the final recursive call completes. With acompiler orinterpreter that treats tail-recursive calls asjumps rather than function calls, a tail-recursive function such as gcd will execute using constant space. Thus the program is essentially iterative, equivalent to using imperative language control structures like the "for" and "while" loops.
| Tail recursion: | Augmenting recursion: |
|---|---|
/** * @brief computes GCD using Euclidean algorithm * @param x an int * @param y an int, such that x >= y >= 0 * @returns the GCD of x and y */intgcd(intx,inty){if(y==0){returnx;}else{returngcd(y,x%y);}} | /** * @brief computes the factorial of a non-negative integer * @param n an int * @returns the factorial of n */unsignedintfactorial(unsignedintn){if(n==0){return1;}else{returnn*factorial(n-1);}} |
The significance of tail recursion is that when making a tail-recursive call (or any tail call), the caller's return position need not be saved on thecall stack; when the recursive call returns, it will branch directly on the previously saved return position. Therefore, in languages that recognize this property of tail calls, tail recursion saves both space and time.
Consider these two functions:
#include<stdio.h>voidrecursiveFunction(intnum){printf("%d\n",num);if(num<4){recursiveFunction(num+1);}}
#include<stdio.h>voidrecursiveFunction(intnum){if(num<4){recursiveFunction(num+1);}printf("%d\n",num);}
The output of function 2 is that of function 1 with the lines swapped.
In the case of a function calling itself only once, instructions placed before the recursive call are executed once per recursion before any of the instructions placed after the recursive call. The latter are executed repeatedly after the maximum recursion has been reached.
Also note that theorder of the print statements is reversed, which is due to the way the functions and statements are stored on thecall stack.
A classic example of a recursive procedure is the function used to calculate thefactorial of anatural number:
| Pseudocode (recursive): |
|---|
function factorial is: |
The function can also be written as arecurrence relation:
This evaluation of the recurrence relation demonstrates the computation that would be performed in evaluating the pseudocode above:
| 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 = 24 |
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: |
The imperative code above is equivalent to this mathematical definition using an accumulator variablet:
The definition above translates straightforwardly tofunctional programming languages such asScheme; this is an example of iteration implemented recursively.
TheEuclidean algorithm, which computes thegreatest common divisor of two integers, can be written recursively.
Function definition:
| Pseudocode (recursive): |
|---|
function gcd is:input: integerx, integery such thatx > 0 andy >= 0 |
Recurrence relation for greatest common divisor, where expresses theremainder of:
| Computing the recurrence relation for x = 27 and y = 9: |
|---|
gcd(27, 9) = gcd(9, 27% 9) = gcd(9, 0) = 9 |
| Computing the recurrence relation for x = 111 and y = 259: |
gcd(111, 259) = gcd(259, 111% 259) = gcd(259, 111) = gcd(111, 259% 111) = gcd(111, 37) = gcd(37, 111% 37) = gcd(37, 0) = 37 |
The recursive program above istail-recursive; it is equivalent to an iterative algorithm, and the computation shown above shows the steps of evaluation that would be performed by a language that eliminates tail calls. Below is a version of the same algorithm using explicit iteration, suitable for a language that does not eliminate tail calls. By maintaining its state entirely in the variablesx andy and using a looping construct, the program avoids making recursive calls and growing the call stack.
| Pseudocode (iterative): |
|---|
function gcd is: |
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.
The Towers of Hanoi is a mathematical puzzle whose solution illustrates recursion.[32][33] There are three pegs which can hold stacks of disks of different diameters. A larger disk may never be stacked on top of a smaller. Starting withn disks on one peg, they must be moved to another peg one at a time. What is the smallest number of steps to move the stack?
Function definition:
Recurrence relation for hanoi:
| Computing the recurrence relation for n = 4: |
|---|
hanoi(4) = 2×hanoi(3) + 1 = 2×(2×hanoi(2) + 1) + 1 = 2×(2×(2×hanoi(1) + 1) + 1) + 1 = 2×(2×(2×1 + 1) + 1) + 1 = 2×(2×(3) + 1) + 1 = 2×(7) + 1 = 15 |
Example implementations:
| Pseudocode (recursive): |
|---|
function hanoi is: |
Although not all recursive functions have an explicit solution, the Tower of Hanoi sequence can be reduced to an explicit formula.[34]
| An explicit formula for Towers of Hanoi: |
|---|
h1 = 1 = 21 - 1h2 = 3 = 22 - 1h3 = 7 = 23 - 1h4 = 15 = 24 - 1h5 = 31 = 25 - 1h6 = 63 = 26 - 1h7 = 127 = 27 - 1 In general:hn = 2n - 1, for all n >= 1 |
Thebinary search algorithm is a method of searching asorted array for a single element by cutting the array in half with each recursive 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 at the midpoint, 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 in C:
/** * @brief Call binary_search with proper initial conditions. * @param data an array of integers SORTED in ASCENDING order * @param target the integer to search for * @param count the total number of elements in the array * @returns result of binary_search */intsearch(intdata[],inttarget,intcount){// Start = 0 (beginning index)// End = count - 1 (top index)returnbinary_search(data,target,0,count-1);}/** * @brief Binary Search Algorithm. * @param data an array of integers SORTED in ASCENDING order * @param target the integer to search for * @param start the minimum array index * @param end the maximum array index * @returns position of the integer toFind within array data, -1 if not found */intbinary_search(intdata[],inttarget,intstart,intend){//Get the midpoint.intmid=start+(end-start)/2;//Integer divisionif(start>end){return-1;// Stop condition (base case)}elseif(data[mid]==target){returnmid;// Found, return index}elseif(data[mid]>target){// Data is greater than target, search lower halfreturnbinary_search(data,target,start,mid-1);}else{// Data is less than target, search upper halfreturnbinary_search(data,target,mid+1,end);}}
An important application of recursion in computer science is in defining dynamic data structures such aslists andtrees. Recursive data structures can dynamically grow to a theoretically infinite size in response to runtime requirements; in contrast, the size of a static array 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."[35]
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.[15]
Below is a C definition of a linked list node structure. Notice especially how the node is defined in terms of itself. The "next" element ofLinkedList is a pointer to another linked list, effectively creating a list type.
structLinkedList{intdata;// some integer datastructLinkedList*next;// pointer to another node of the linked list};
Because thestruct node data structure is defined recursively, procedures that operate on it can be implemented naturally as recursive procedures. Thelist_print procedure defined below walks down the list until the list is empty (i.e., the list pointer has a value of NULL). For each node it prints the data element (an integer). In the C implementation, the list remains unchanged by thelist_print procedure.
voidlist_print(structLinkedList*list){// base caseif(list){printf("%d ",list->data);// print integer data followed by a spacelist_print(list->next);// recursive call on the next node}}
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).
structBinaryTree{intdata;// some integer datastructBinaryTree*left;// pointer to the left subtreestructBinaryTree*right;// pointer to the right subtree};
Operations on the tree can be implemented using recursion. Note that because there are two self-referencing pointers (left and right), tree operations may require two recursive calls:
// Test if tree_node contains i; return 1 if so, 0 if not.inttree_contains(structBinaryTree*node,inti){if(!node){return0;// base case}elseif(node->data==i){return1;}else{returntree_contains(node->left,i)||tree_contains(node->right,i);}}
At most two recursive calls will be made for any given call totree_contains as defined above.
// Inorder traversal:voidtree_print(structBinaryTree*node){// base caseif(node){tree_print(node->left);// go leftprintf("%d ",node->data);// print the integer followed by a spacetree_print(node->right);// go right}}
The above example illustrates anin-order traversal of the binary tree. ABinary search tree is a special case of the binary tree where the data elements of each node are in order.
Since the number of files in afilesystem may vary,recursion is the only practical way to traverse and thus enumerate its contents. Traversing a filesystem is very similar to that oftree traversal, therefore the concepts behind tree traversal are applicable to traversing a filesystem. More specifically, the code below would be an example of apreorder traversal of a filesystem.
packageorg.wikipedia.examples;importjava.io.File;publicclassExample{/** * Obtains the filesystem roots * Proceeds with the recursive filesystem traversal */privatestaticvoidtraverse(){File[]fs=File.listRoots();for(inti=0;i<fs.length;i++){System.out.println(fs[i]);if(fs[i].isDirectory()&&fs[i].canRead()){rtraverse(fs[i]);}}}/** * Recursively traverse a given directory * * @param fd indicates the starting point of traversal */privatestaticvoidrtraverse(Filefd){File[]fss=fd.listFiles();for(inti=0;i<fss.length;i++){System.out.println(fss[i]);if(fss[i].isDirectory()&&fss[i].canRead()){rtraverse(fss[i]);}}}publicstaticvoidmain(String[]args){traverse();}}
This code is both recursion anditeration - the files and directories are iterated, and each directory is opened recursively.
The "rtraverse" method is an example of direct recursion, whilst the "traverse" method is a wrapper function.
The "base case" scenario is that there will always be a fixed number of files and/or directories in a given filesystem.
Thetime efficiency of recursive algorithms can be expressed in arecurrence relation ofBig O notation. They can (usually) then be simplified into a single Big-O term.
If the time-complexity of the function is in the form
Then the Big O of the time-complexity is thus:
wherea represents the number of recursive calls at each level of recursion,b represents by what factor smaller the input is for the next level of recursion (i.e. the number of pieces you divide the problem into), andf(n) represents the work that the function does independently of any recursion (e.g. partitioning, recombining) at each level of recursion.
In the procedural interpretation oflogic programs, clauses (or rules) of the formA:-B are treated as procedures, which reduce goals of the formA to subgoals of the formB.For example, theProlog clauses:
path(X,Y):-arc(X,Y).path(X,Y):-arc(X,Z),path(Z,Y).
define a procedure, which can be used to search for a path fromX toY, either by finding a direct arc fromX toY, or by finding an arc fromX toZ, and then searching recursively for a path fromZ toY. Prolog executes the procedure by reasoning top-down (orbackwards) and searching the space of possible paths depth-first, one branch at a time. If it tries the second clause, and finitely fails to find a path fromZ toY, it backtracks and tries to find an arc fromX to another node, and then searches for a path from that other node toY.
However, in the logical reading of logic programs, clauses are understooddeclaratively as universally quantified conditionals. For example, the recursive clause of the path-finding procedure is understood asrepresenting the knowledge that, for everyX,Y andZ, if there is an arc fromX toZ and a path fromZ toY then there is a path fromX toY. In symbolic form:
The logical reading frees the reader from needing to know how the clause is used to solve problems. The clause can be used top-down, as in Prolog, to reduce problems to subproblems. Or it can be used bottom-up (orforwards), as inDatalog, to derive conclusions from conditions. Thisseparation of concerns is a form ofabstraction, which separates declarative knowledge from problem solving methods (seeAlgorithm#Algorithm = Logic + Control).[36]
A common mistake among programmers is not providing a way to exit a recursive function, often by omitting or incorrectly checking the base case, letting it run (at least theoretically) infinitely by endlessly calling itself recursively. This is calledinfinite recursion, and the program will never terminate. In practice, this typically exhausts the availablestack space. In most programming environments, a program with infinite recursion will not really run forever. Eventually, something will break and the program will report an error.[37]
Below is a Java code that would use infinite recursion:
publicclassInfiniteRecursion{staticvoidrecursive(){// Recursive function with no way outrecursive();}publicstaticvoidmain(String[]args){recursive();// Executes the recursive function upon runtime}}
Running this code will result in astack overflow error.