Recursion (computer science)

60: 1184:

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 shows

3357: 3947: 2630: 2530: 3823:; 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 variables 3102: 1214:

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.

834:

requires greater care. These generatively recursive functions can often be interpreted as corecursive functions – each step generates the new data, such as successive approximation in Newton's method – and terminating this corecursion requires that the data eventually satisfy some condition, which is

743:

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

532:

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

1734:

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

4354:

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.

4350:

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

1183:

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

1213:

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

241:

The job of the recursive cases can be seen as breaking down complex inputs into simpler ones. In a properly designed recursive function, with each recursive call, the input problem must be simplified in such a way that eventually the base case must be reached. (Functions that are not intended to

2049:

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

1721:

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

726:

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

870:

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

577:

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

895:, 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 using 4098: 1202:

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

581:

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

2792: 3525: 7195: 2638:

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.

95:

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

3352:{\displaystyle {\begin{aligned}\operatorname {fact} (n)&=\operatorname {fact_{acc}} (n,1)\\\operatorname {fact_{acc}} (n,t)&={\begin{cases}t&{\mbox{if }}n=0\\\operatorname {fact_{acc}} (n-1,nt)&{\mbox{if }}n>0\\\end{cases}}\end{aligned}}} 5019:

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

845:

By contrast, generative recursion is when there is not such an obvious loop variant, and termination depends on a function, such as "error of approximation" that does not necessarily decrease to zero, and thus termination is not guaranteed without further

886:

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 for

476:

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

48: 3811:

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

2094:

input. Some malware specifically targets a program's call stack and takes advantage of the stack's inherently recursive nature. Even in the absence of malware, a stack overflow caused by unbounded recursion can be fatal to the program, and

2210:

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.

3937:

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.

1259:

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

238:. Neither equation by itself constitutes a complete definition; the first is the base case, and the second is the recursive case. Because the base case breaks the chain of recursion, it is sometimes also called the "terminating case". 369:

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.

4891:

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 the

4210:

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

3960:

The Towers of Hanoi is a mathematical puzzle whose solution illustrates recursion. 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 with

2030:) 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; in 3977: 6913: 2677: 6918:

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 (or

855:

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:

2424:; 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. 4810:

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.

3398: 499:

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.

2126:; though both recursive and iterative methods are used, they contrast with list traversal and linear search in a list, which is a singly recursive and thus naturally iterative method. Other examples include 8001: 1775:, 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, in 2014:, 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. 744:

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.

700:

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 for

6368: 722:

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:

6067: 3107: 1191:

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 for

6296: 4806:

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.

4798:. 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. 2198:

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 a

6458: 528:

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 of

6223: 6157: 8748: 5087:

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:

830:

Generatively recursive functions, in contrast, do not necessarily feed smaller input to their recursive calls, so proof of their termination is not necessarily as simple, and avoiding

570:. 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 include 513:

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 the

5991: 7907: 3717: 7971: 1722:

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 entire

6522: 6394: 6093: 2066:, 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 avoid 270:(such as the number of terms to be added, in our series example) to provide a 'stopping criterion' that establishes the base case. Such an example is more naturally treated by 4162: 2909: 2194:

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) is

582:

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 – see

152:

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 less

7920: 3785: 7829: 1271:

there are 2−1 nodes and 2 Null pointers as children (2 for each of the 2 leaves), so short-circuiting cuts the number of function calls in half in the worst case.

91:

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.

4196: 3743: 2943: 2010:, 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 may 172:

tactic is to divide a problem into sub-problems of the same type as the original, solve those sub-problems, and combine the results. This is often referred to as the

2142:, but the programmer effort involved in managing the stack, and the complexity of the resulting program, arguably outweigh any advantages of the iterative solution. 3620: 8070: 3652: 2987:

This factorial function can also be described without using recursion by making use of the typical looping constructs found in imperative programming languages:

8005: 2158:. An alternative is to develop a replacement algorithm entirely based on non-recursive methods, which can be challenging. For example, recursive algorithms for 639:

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.

8741: 1779:

recursion is preferred, with tail recursion optimization leading to little overhead. Implementing an algorithm using iteration may not be easily achievable.

2041:

As a concrete example, the difference in performance between recursive and iterative implementations of the "factorial" example above depends highly on the

180:

that stores the results of previously solved sub-problems (to avoid solving them repeatedly and incurring extra computation time), it can be referred to as

686:

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.

7900: 7622: 842:, structural recursion is when there is an obvious loop variant, namely size or complexity, which starts off finite and decreases at each recursive step. 4093:{\displaystyle \operatorname {hanoi} (n)={\begin{cases}1&{\mbox{if }}n=1\\2\cdot \operatorname {hanoi} (n-1)+1&{\mbox{if }}n>1\\\end{cases}}} 2420:

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 the

1825:

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.

6958: 5427:, therefore the concepts behind tree traversal are applicable to traversing a filesystem. More specifically, the code below would be an example of a 274:, where successive terms in the output are the partial sums; this can be converted to a recursion by using the indexing parameter to say "compute the 6721:) 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 from 8134: 2787:{\displaystyle \operatorname {fact} (n)={\begin{cases}1&{\mbox{if }}n=0\\n\cdot \operatorname {fact} (n-1)&{\mbox{if }}n>0\\\end{cases}}} 883:

is a function that is directly called but does not recurse itself, instead calling a separate auxiliary function which actually does the recursion.

8734: 8484: 8346: 6790: 5915: 615:

recursion occurs when a function is called not by itself but by another function that it called (either directly or indirectly). For example, if

1963:, although other methods may be used). Every recursive function can be transformed into an iterative function by replacing recursive calls with 8490: 6745: 4826:

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 of

1726:

of these functions can be replaced with a single Boolean expression in a return statement, but legibility suffers at no benefit to efficiency.

2980:))) = 4 × (3 × (2 × (1 × 1))) = 4 × (3 × (2 × 1)) = 4 × (3 × 2) = 4 × 6 = 24 2150:

Recursive algorithms can be replaced with non-recursive counterparts. One method for replacing recursive algorithms is to simulate them using

8995: 7893: 7800: 7750: 7731: 7245: 6535:

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), and

8675: 8423: 7775: 7132: 7094: 3520:{\displaystyle \gcd(x,y)={\begin{cases}x&{\mbox{if }}y=0\\\gcd(y,\operatorname {remainder} (x,y))&{\mbox{if }}y>0\\\end{cases}}} 7673: 4802:"Recursive algorithms are particularly appropriate when the underlying problem or the data to be treated are defined in recursive terms." 525:—and what those contents may be, whereas the inductive definition specifies how to create the structure and what it may be created from. 2171: 6546:

represents the work that the function does independently of any recursion (e.g. partitioning, recombining) at each level of recursion.

8143: 7632: 7843: 7680: 7384: 7299: 7272: 7208: 7037: 2948:

This evaluation of the recurrence relation demonstrates the computation that would be performed in evaluating the pseudocode above:

1836:

by assigning to a loop index variable and accumulator variable, rather than by passing arguments and returning values by recursion:

4351:

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.

4283:

Although not all recursive functions have an explicit solution, the Tower of Hanoi sequence can be reduced to an explicit formula.

2174:, have been developed to avoid the drawbacks of recursion and have improved only gradually based on techniques such as collecting 8515: 8195: 8139: 7481: 2179: 1951:

in use today allow the direct specification of recursive functions and procedures. When such a function is called, the program's

4887:

data structure is defined recursively, procedures that operate on it can be implemented naturally as recursive procedures. The

8375: 8248: 8179: 8114: 8037: 7054: 6303: 4355:

The algorithm exhibits a logarithmic order of growth because it essentially divides the problem domain in half with each pass.

3363: 8553: 8316: 7946: 7706: 6932: 5923: 330:

An inductively defined recursive data definition is one that specifies how to construct instances of the data. For example,

7551: 7530: 5423:

is the only practical way to traverse and thus enumerate its contents. Traversing a filesystem is very similar to that of

3965:

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?

9005: 8331: 8321: 8099: 3367: 2071: 2003: 7497:"Tricks of the trade: Recursion to Iteration, Part 2: Eliminating Recursion with the Time-Traveling Secret Feature Trick" 6744:

as universally quantified conditionals. For example, the recursive clause of the path-finding procedure is understood as

6002: 8896: 8881: 8715: 8695: 8625: 8568: 8530: 8520: 8480: 8405: 8341: 8311: 8238: 8227: 8124: 8104: 8042: 7425: 6994: 6228: 5886:

The "base case" scenario is that there will always be a fixed number of files and/or directories in a given filesystem.

2127: 538: 9010: 8670: 8433: 8400: 8295: 8271: 8233: 8213: 8109: 8018: 7996: 7981: 7433: 7148: 2027: 1999: 1956: 646:, which is a more symmetric term, though this is simply a difference of emphasis, not a different notion. That is, if 88: 52: 7405: 8951: 8825: 8815: 8795: 8617: 8603: 8510: 8470: 8395: 8301: 8281: 8148: 8027: 7961: 7792: 6399: 2087: 243: 6963: 6164: 6098: 758:

Many well-known recursive algorithms generate an entirely new piece of data from the given data and recur on it.

8830: 8710: 8475: 8385: 8365: 8351: 4791: 504: 260: 173: 2118:

Multiply recursive problems are inherently recursive, because of prior state they need to track. One example is

8690: 8650: 8593: 8525: 8263: 8094: 7511: 2023: 1995: 1833: 1718: 1185: 396: 5883:

The "rtraverse" method is an example of direct recursion, whilst the "traverse" method is a wrapper function.

125:) do not define any looping constructs but rely solely on recursion to repeatedly call code. It is proved in 8969: 8931: 8700: 8680: 8621: 8608: 8588: 8415: 8152: 8056: 8014: 6989: 3660: 3383: 2646:

of the print statements is reversed, which is due to the way the functions and statements are stored on the

2203: 407:; here is such a grammar, for a simple language of arithmetic expressions with multiplication and addition: 400: 2045:

used. In languages where looping constructs are preferred, the iterative version may be as much as several

1240:

recursive step: otherwise, check value of current node, return true if match, otherwise recurse on children

8775: 8660: 8635: 8629: 8573: 8535: 8223: 8218: 8170: 8065: 7966: 7938: 7929: 6948: 6928: 2139: 1968: 1772: 759: 734: 246:—are an exception to this.) Neglecting to write a base case, or testing for it incorrectly, can cause an 153: 118: 64: 31: 7496: 7462: 4790:

An important application of recursion in computer science is in defining dynamic data structures such as

510:

A stream of strings is an object s such that: head(s) is a string, and tail(s) is a stream of strings.

8835: 8805: 8562: 8558: 8500: 8452: 8022: 6953: 6474: 4795: 2067: 1991: 827:: intuitively, each recursive call receives a smaller piece of input data, until a base case is reached. 201: 83:

where the solution depends on solutions to smaller instances of the same problem. Recursion solves such

80: 7535: 7410: 7389: 6373: 6072: 404: 4112: 3090:

The imperative code above is equivalent to this mathematical definition using an accumulator variable

9015: 8946: 8921: 8866: 8705: 8685: 8645: 8447: 8306: 8175: 8162: 7916: 6984: 3831:

and using a looping construct, the program avoids making recursive calls and growing the call stack.

2031: 1948: 1776: 824: 812: 717: 587: 254: 126: 114: 4004: 3428: 3238: 2865: 2704: 1771:. Which approach is preferable depends on the problem under consideration and the language used. In 8956: 8941: 8886: 8640: 8578: 8390: 8370: 8356: 8088: 7956: 7951: 7237: 6979: 6741: 5899: 4785: 3593: 3379: 2856: 2103: 2046: 1987: 1975: 1952: 1264: 820: 794: 770: 705: 695: 325: 314: 181: 134: 9000: 8974: 8876: 8871: 8785: 8457: 8410: 8380: 8326: 8185: 8084: 7976: 7885: 7873: 7853: 7825: 5428: 5404: 3749: 2159: 2135: 2123: 2096: 2063: 1223: 701: 786: 8936: 8780: 8613: 8505: 8360: 8336: 8276: 8243: 8205: 8190: 8129: 7839: 7811: 7796: 7771: 7767: 7746: 7727: 7702: 7638: 7628: 7613: 7295: 7289: 7268: 7241: 7233: 7204: 7191: 7128: 7124: 7114: 7090: 7086: 7080: 7033: 7004: 6718: 6555: 2151: 896: 35: 7262: 7175: 4168: 3722: 2915: 30:

This article is about recursive approaches to solving problems. For proofs by recursion, see

8916: 8901: 8495: 8427: 8291: 8032: 7865: 7717: 7676: 7225: 6920: 2175: 1974:

Conversely, all iterative functions and procedures that can be evaluated by a computer (see

1744: 880: 643: 599: 303: 291: 169: 72: 59: 7482:"How to replace recursive functions using stack and while-loop to avoid the stack-overflow" 866:

Hybrid algorithm (at bottom) – switching to a different algorithm once data is small enough

8891: 8545: 8419: 8285: 7986: 7661: 5895: 3955: 3599: 2086:

Because recursive algorithms can be subject to stack overflows, they may be vulnerable to

892: 529: 378: 160:

optimization may improve computational performance over a naive recursive implementation.

130: 7226: 3629: 2170:

algorithm, were once typical. Non-recursive algorithms for the same purpose, such as the

1978:) can be expressed in terms of recursive functions; iterative control constructs such as 403:

in programming languages. Language designers often express grammars in a syntax such as

55:

and relying heavily on recursion. Each branch can be seen as a smaller version of a tree.

7691:

Felleisen, Matthias; Findler, Robert B.; Flatt, Matthew; Krishnamurthi, Shriram (2001).

5407:

is a special case of the binary tree where the data elements of each node are in order.

769:

refers to this kind as generative recursion. Examples of generative recursion include:

133:; this means that they are as powerful (they can be used to solve the same problems) as 8757: 8597: 8253: 8119: 7821: 7761: 6999: 6968: 5903: 5424: 5400: 3820: 2668: 2217: 2119: 2075: 2011: 1768: 1740: 831: 604:

Most basic examples of recursion, and most of the examples presented here, demonstrate

571: 266:) there is not an obvious base case implied by the input data; for these one may add a 117:

support recursion by allowing a function to call itself from within its own code. Some

7316: 2138:. All of these algorithms can be implemented iteratively with the help of an explicit 8989: 8906: 8861: 8583: 7877: 7120: 7110: 7025: 4343: 2107: 2038:) is typically a very fast operation, and the difference is usually less noticeable. 778: 534: 298:. Recursion is a technique for representing data whose exact size is unknown to the 247: 156:, and, for certain problems, algorithmic or compiler-optimization techniques such as 101: 7363:"27.1. sys — System-specific parameters and functions — Python v2.7.3 documentation" 5880:- the files and directories are iterated, and each directory is opened recursively. 8856: 8820: 8790: 7665: 7617: 7466: 7447: 4347: 2155: 1964: 1723: 839: 177: 208:, meaning input(s) for which the program recurs (calls itself). For example, the 17: 8726: 7786: 2663:

A classic example of a recursive procedure is the function used to calculate the

8810: 8465: 5014: 4821: 1763:

are equally expressive: recursion can be replaced by iteration with an explicit

888: 583: 494: 490: 331: 307: 306:

definition. There are two types of self-referential definitions: inductive and

271: 185: 8800: 5416: 4227: 3946: 3533: 2800: 2647: 2421: 2059: 1979: 1960: 1764: 1736: 392: 374: 299: 149: 3799:

gcd(27, 9) = gcd(9, 27 % 9) = gcd(9, 0) = 9

8761: 7835: 7723: 7698: 6973: 6936: 6908:{\displaystyle \forall X,Y,Z(arc(X,Z)\land path(Z,Y)\rightarrow path(X,Y)).} 5877: 5420: 3623: 2664: 2191: 2163: 2131: 2035: 2007: 1829: 1760: 782: 774: 267: 209: 157: 84: 39: 7362: 7341: 47: 6935:, which separates declarative knowledge from problem solving methods (see 6740:

However, in the logical reading of logic programs, clauses are understood

2074:

is one such language. Note the caveat below regarding the special case of

2199: 2042: 1983: 678:

alone, it is indirectly recursing, while from the point of view of both,

590:, which allows iterative tree traversal, rather than multiple recursion. 514: 382: 2190:

Tail-recursive functions are functions in which all recursive calls are

2006:

are notable mainstream languages in which all function calls, including

863:

Short-circuiting the base case, aka "Arm's-length recursion" (at bottom)

8911: 7869: 7692: 7591:, pp. 447–448: An Explicit Formula for the Tower of Hanoi Sequence 6924: 2635:

The output of function 2 is that of function 1 with the lines swapped.

2629: 2529: 2167: 2091: 1748: 790: 335: 122: 6733:

to another node, and then searches for a path from that other node to

481:, with more than one product or sum operation in a single expression. 7515: 6579: 6531:

represents the number of recursive calls at each level of recursion,

562:, while recursion that contains multiple self-references is known as 7694:

How To Design Programs: An Introduction to Computing and Programming

7264:

Python Algorithms: Mastering Basic Algorithms in the Python Language

5906:. They can (usually) then be simplified into a single Big-O term. 7448:"Depth First Search (DFS): Iterative and Recursive Implementation" 7171: 6685:

define a procedure, which can be used to search for a path from

3945: 2099: 1747:. Hybrid recursive algorithms can often be further refined, as in 578:

being able to be replaced by iteration without an explicit stack.

58: 554:

Recursion that contains only a single self-reference is known as

388:

A natural number is either 1 or n+1, where n is a natural number.

8840: 7642: 7228:

Programming Interviews Exposed: Secrets to Landing Your Next Job

2207: 295: 8730: 7889: 5259:

At most two recursive calls will be made for any given call to

1739:, which is often implemented by switching to the non-recursive 1255:

In terms of the standard steps, this moves the base case check

148:

Repeatedly calling a function from within itself may cause the

1274:

In C, the standard recursive algorithm may be implemented as:

891:, and handle exceptions and errors. In languages that support 7406:"Anatomy of a Stack Smashing Attack and How GCC Prevents It" 200:, meaning input(s) for which the function produces a result 7385:"Matching Wildcards: An Empirical Way to Tame an Algorithm" 4086: 3805:

Computing the recurrence relation for x = 111 and y = 259:

3513: 3370:; this is an example of iteration implemented recursively. 3341: 2780: 537:

is one that can be solved with a corecursive program (e.g.

7672:. Macdonald Computer Monographs (1 ed.). London, UK: 7062:

World Transactions on Engineering and Technology Education

6717:. Prolog executes the procedure by reasoning top-down (or 6570:

are treated as procedures, which reduce goals of the form

5092:// Test if tree_node contains i; return 1 if so, 0 if not. 294:

must process or generate an arbitrarily large quantity of

7197:

Advanced Functional Programming: 4th International School

7149:"Functional Programming | Clojure for the Brave and True" 6363:{\displaystyle f(n)=\Omega (n^{\log _{b}a+\varepsilon })} 674:

is indirectly recursing, while from the point of view of

7552:"Matching Wildcards: An Improved Algorithm for Big Data" 7055:"Teaching Recursive Thinking using Unplugged Activities" 3793:

Computing the recurrence relation for x = 27 and y = 9:

2231://INPUT: Integers x, y such that x >= y and y >= 0 823:) data structures can easily be shown to terminate, via 7024:

Graham, Ronald; Knuth, Donald; Patashnik, Oren (1990).

4372:

data is an array of integers SORTED in ASCENDING order,

2058:

In some programming languages, the maximum size of the

1805:

function recursive(n) if n == base return x

242:

terminate under normal circumstances—for example, some

7317:"The Anatomy of a Loop - A story of scope and control" 5920:

If the time-complexity of the function is in the form

4486:

data is a array of integers SORTED in ASCENDING order,

4068: 4013: 3495: 3437: 3323: 3247: 2762: 2713: 6793: 6477: 6402: 6376: 6306: 6231: 6167: 6101: 6075: 6005: 5926: 5685:* @param fd indicates the starting point of traversal 4171: 4115: 3980: 3752: 3725: 3663: 3632: 3602: 3401: 3362:

The definition above translates straightforwardly to

3105: 2918: 2868: 2680: 1818:

for i = base+1 to n x = f(i, x) return x

1443:

The short-circuited algorithm may be implemented as:

212:

function can be defined recursively by the equations

7564: 7185: 7183: 507:

of strings, given informally, might look like this:

8849: 8768: 8659: 8544: 8446: 8262: 8204: 8161: 8064: 8055: 7995: 7937: 7928: 7224:Mongan, John; Giguère, Eric; Kindler, Noah (2013). 6559: 6062:{\displaystyle f(n)=O(n^{\log _{b}a-\varepsilon })} 1751:, derived from a hybrid merge sort/insertion sort. 142: 138: 6907: 6516: 6452: 6388: 6362: 6291:{\displaystyle T(n)=\Theta (n^{\log _{b}a}\log n)} 6290: 6217: 6151: 6087: 6061: 5985: 5499:* Proceeds with the recursive filesystem traversal 4378:count is the total number of elements in the array 4366:Call binary_search with proper initial conditions. 4190: 4156: 4092: 3779: 3737: 3711: 3646: 3614: 3519: 3351: 2937: 2903: 2786: 1251:otherwise, on children, if not Null, then recurse. 1248:check value of current node, return true if match, 253:For some functions (such as one that computes the 34:. For recursion in computer science acronyms, see 7831:Structure and Interpretation of Computer Programs 7053:Kuhail, M. A.; Negreiros, J.; Seffah, A. (2021). 6709:, and then searching recursively for a path from 4501:position of the integer toFind within array data, 1990:. However, in practice this rewriting depends on 7085:(2nd ed.). PWS Publishing Company. p. 4780:Recursive data structures (structural recursion) 4690://Data is greater than toFind, search lower half 3753: 3685: 3664: 3456: 3402: 1237:base case: If current node is Null, return false 1222:A basic example of short-circuiting is given in 819:All structurally recursive functions on finite ( 586:. A more sophisticated example involves using a 196:A recursive function definition has one or more 7294:(4th ed.), Cengage Learning, p. 197, 5995:Then the Big O of the time-complexity is thus: 1743:when the data is sufficiently small, as in the 1233:The standard recursive algorithm for a DFS is: 756: 724: 93: 6927:, to derive conclusions from conditions. This 6729:, it backtracks and tries to find an arc from 5898:of recursive algorithms can be expressed in a 4358:Example implementation of binary search in C: 1175:Short-circuiting the base case, also known as 302:: the programmer can specify this data with a 8742: 7901: 6453:{\displaystyle a\cdot f(n/b)\leq c\cdot f(n)} 4732://Data is less than toFind, search upper half 4204:Computing the recurrence relation for n = 4: 3386:of two integers, can be written recursively. 2954:Computing the recurrence relation for n = 4: 2062:is much less than the space available in the 1986:are routinely rewritten in recursive form in 732:Felleisen, Findler, Flatt, and Krishnaurthi, 36:Recursive acronym § Computer-related examples 8: 6218:{\displaystyle f(n)=\Theta (n^{\log _{b}a})} 6152:{\displaystyle T(n)=\Theta (n^{\log _{b}a})} 2330://INPUT: n is an Integer such that n >= 0 1994:, which is not a feature of all languages. 1832:function may be implemented iteratively in 1230:section for standard recursive discussion. 8749: 8735: 8727: 8061: 7934: 7908: 7894: 7886: 7623:Artificial Intelligence: A Modern Approach 1203:factorial, short-circuiting provides only 1188:code to shortcut factorial cases 0 and 1. 908: 485:Coinductively defined data and corecursion 7972:Programming in the large and in the small 6959:Hierarchical and recursive queries in SQL 6792: 6476: 6418: 6401: 6375: 6337: 6332: 6305: 6262: 6257: 6230: 6198: 6193: 6166: 6132: 6127: 6100: 6074: 6036: 6031: 6004: 5957: 5925: 4976:// print integer data followed by a space 4289:An explicit formula for Towers of Hanoi: 4176: 4170: 4136: 4120: 4114: 4067: 4012: 3999: 3979: 3751: 3724: 3662: 3636: 3631: 3601: 3494: 3436: 3423: 3400: 3322: 3280: 3266: 3246: 3233: 3195: 3181: 3146: 3132: 3106: 3104: 2923: 2917: 2889: 2873: 2867: 2761: 2712: 2699: 2679: 1809:else return f(n, recursive(n-1)) 395:are often used to model the structure of 5679:* Recursively traverse a given directory 5367:// print the integer followed by a space 4285: 4223: 4200: 3833: 3789: 3529: 2989: 2950: 2796: 2213: 1448:// Wrapper function to handle empty tree 334:can be defined inductively (here, using 129:that these recursive-only languages are 46: 7116:Algorithms + Data Structures = Programs 7016: 5986:{\displaystyle T(n)=a\cdot T(n/b)+f(n)} 5916:Master theorem (analysis of algorithms) 5890:Time-efficiency of recursive algorithms 1767:, while iteration can be replaced with 550:Single recursion and multiple recursion 106:Algorithms + Data Structures = Programs 7579:, pp. 427–430: The Tower of Hanoi 7082:Discrete Mathematics with Applications 6693:, either by finding a direct arc from 3712:{\displaystyle \gcd(x,y)=\gcd(y,x\%y)} 2976:)) = 4 × (3 × (2 × (1 × b 2855:The function can also be written as a 1244:In short-circuiting, this is instead: 712:Structural versus generative recursion 7719:Introduction to Recursive Programming 7674:Macdonald & Co. (Publishers) Ltd. 7600: 7291:Data Structures and Algorithms in C++ 7192:"Developing Interactive Web Programs" 6937:Algorithm#Algorithm = Logic + Control 4346:algorithm is a method of searching a 3901:to the remainder of x/y 3. 1967:and simulating the call stack with a 1179:, consists of checking the base case 611:, in which a function calls itself. 503:A coinductive definition of infinite 204:(without recurring), and one or more 27:Use of functions that call themselves 7: 7664:(1968) . Written at Cambridge, UK. 6554:In the procedural interpretation of 4834:, effectively creating a list type. 4489:toFind is the integer to search for, 4375:toFind is the integer to search for, 2206:that treats tail-recursive calls as 137:based on control structures such as 7670:Recursive techniques in programming 7588: 7576: 3596:for greatest common divisor, where 2172:Krauss matching wildcards algorithm 1971:explicitly managed by the program. 635:then that is indirect recursion of 574:, such as in a depth-first search. 38:. For general use of the term, see 7627:(4th ed.). Hoboken: Pearson. 7565:Graham, Knuth & Patashnik 1990 7531:"Matching Wildcards: An Algorithm" 7463:"Replace Recursion with Iteration" 6794: 6517:{\displaystyle T(n)=\Theta (f(n))} 6493: 6322: 6247: 6183: 6117: 4997:// recursive call on the next node 3700: 3606: 3287: 3284: 3281: 3277: 3273: 3270: 3267: 3202: 3199: 3196: 3192: 3188: 3185: 3182: 3153: 3150: 3147: 3143: 3139: 3136: 3133: 2102:may not prevent the corresponding 2034:, a function call (particularly a 1782:Compare the templates to compute x 642:Indirect recursion is also called 164:Recursive functions and algorithms 25: 7856:(1960). "Recursive Programming". 7322:. Georgia Institute of Technology 6558:, clauses (or rules) of the form 6389:{\displaystyle \varepsilon >0} 6088:{\displaystyle \varepsilon >0} 5399:The above example illustrates an 4875:// pointer to another struct node 4492:start is the minimum array index, 1547:// Assumes tree_node != NULL 1227: 811:This distinction is important in 666:again, from the point of view of 623:that is direct recursion, but if 533:problem of computing the first n 264:= 1/0! + 1/1! + 1/2! + 1/3! + ... 8516:Partitioned global address space 5876:This code is both recursion and 4157:{\displaystyle h_{n}=2h_{n-1}+1} 3364:functional programming languages 2972:) = 4 × (3 × (2 × b 2628: 2528: 5415:Since the number of files in a 4435:// End = count - 1 (top index) 4432:// Start = 0 (beginning index) 3819:The recursive program above is 1959:of the function (often using a 1814:function iterative(n) x = x 804:Advanced Functional Programming 7810:Helman, Paul; Veroff, Robert. 7763:Thinking Recursively with Java 7716:Rubio-Sanchez, Manuel (2017). 7426:"StackOverflowException Class" 6899: 6896: 6884: 6869: 6866: 6854: 6836: 6824: 6812: 6550:Recursion in Logic Programming 6511: 6508: 6502: 6496: 6487: 6481: 6447: 6441: 6426: 6412: 6357: 6325: 6316: 6310: 6285: 6250: 6241: 6235: 6212: 6186: 6177: 6171: 6146: 6120: 6111: 6105: 6056: 6024: 6015: 6009: 5980: 5974: 5965: 5951: 5936: 5930: 5910:Shortcut rule (master theorem) 5496:* Obtains the filesystem roots 5061:// pointer to the left subtree 4495:end is the maximum array index 4056: 4044: 3993: 3987: 3768: 3756: 3706: 3688: 3679: 3667: 3489: 3486: 3474: 3459: 3417: 3405: 3317: 3296: 3223: 3211: 3174: 3162: 3122: 3116: 2904:{\displaystyle b_{n}=nb_{n-1}} 2756: 2744: 2693: 2687: 2432:Consider these two functions: 903:Short-circuiting the base case 1: 6995:Primitive recursive functions 5079:// point to the right subtree 4104:Recurrence relation for hanoi 2128:divide-and-conquer algorithms 2050:saved by choosing iteration. 373:Another example of inductive 8996:Theoretical computer science 8043:Uniform Function Call Syntax 7743:Practicing Recursion in Java 7430:.NET Framework Class Library 7261:Hetland, Magnus Lie (2010), 7190:Felleisen, Matthias (2002). 6701:, or by finding an arc from 4624://Stop condition (base case) 2134:, and functions such as the 1965:iterative control constructs 1226:(DFS) of a binary tree; see 8511:Parallel programming models 8485:Concurrent constraint logic 7745:. CreateSpace Independent. 7434:Microsoft Developer Network 7194:. In Jeuring, Johan (ed.). 7176:art V "Generative Recursion 6467:and all sufficiently large 4330:= 2 - 1, for all n >= 1 3780:{\displaystyle \gcd(x,0)=x} 2114:Multiply recursive problems 1955:keeps track of the various 835:not necessarily guaranteed. 244:system and server processes 9032: 8604:Metalinguistic abstraction 8471:Automatic mutual exclusion 7793:Cambridge University Press 7567:, §1.1: The Tower of Hanoi 7554:. Develop for Performance. 6776:then there is a path from 6760:, if there is an arc from 6746:representing the knowledge 5913: 5012: 4819: 4783: 3953: 1755:Recursion versus iteration 1541:// call auxiliary function 1012: 925: 715: 693: 597: 488: 323: 312: 29: 8965: 8476:Choreographic programming 7828:; Sussman, Julie (1996). 7785:Rohl, Jeffrey S. (1984). 7203:. Springer. p. 108. 4221:Example implementations: 860:Wrapper function (at top) 174:divide-and-conquer method 121:languages (for instance, 79:is a method of solving a 53:Logo programming language 8526:Relativistic programming 7550:Krauss, Kirk J. (2018). 7529:Krauss, Kirk J. (2008). 7404:Mueller, Oliver (2012). 7383:Krauss, Kirk J. (2014). 6584: 6574:to subgoals of the form 5433: 5265: 5089: 5022: 4898: 4836: 4830:is a pointer to another 4480:Binary Search Algorithm. 4360: 3837:Pseudocode (iterative): 2993:Pseudocode (iterative): 2539: 2439: 2327: 2228: 2186:Tail-recursive functions 1838: 1719:short-circuit evaluation 1445: 1276: 1013: 926: 921:Short-circuit recursion 409: 340: 320:Inductively defined data 67:through turtle graphics. 8970:List of data structures 7450:. Techie Delight. 2018. 7342:"The Anatomy of a Loop" 7026:"1: Recurrent Problems" 5403:of the binary tree. A 4384:result of binary_search 4191:{\displaystyle h_{1}=1} 3738:{\displaystyle y\neq 0} 3384:greatest common divisor 3374:Greatest common divisor 2938:{\displaystyle b_{0}=1} 2012:overflow the call stack 176:; when combined with a 63:Recursive drawing of a 51:Tree created using the 8536:Structured concurrency 7921:Comparison by language 7760:Roberts, Eric (2005). 7480:La, Woong Gyu (2015). 7288:Drozdek, Adam (2012), 7267:, Apress, p. 79, 6949:Functional programming 6929:separation of concerns 6909: 6518: 6454: 6390: 6364: 6292: 6219: 6153: 6089: 6063: 5987: 4813: 4804: 4192: 4158: 4094: 3951: 3781: 3739: 3713: 3648: 3616: 3521: 3353: 2939: 2905: 2788: 2223:Augmenting recursion: 2022:In languages (such as 1773:imperative programming 1177:arm's-length recursion 809: 765:How to Design Programs 741: 735:How to Design Programs 119:functional programming 111: 68: 56: 32:Mathematical induction 8501:Multitier programming 8317:Interface description 7917:Programming paradigms 7858:Numerische Mathematik 7741:Pevac, Irena (2016). 7662:Barron, David William 7495:Moertel, Tom (2013). 7344:. Lambda the Ultimate 7340:Lambda the Ultimate. 7172:Felleisen et al. 2001 7079:Epp, Susanna (1995). 6990:μ-recursive functions 6964:Kleene–Rosser paradox 6954:Computational problem 6910: 6519: 6455: 6391: 6365: 6293: 6220: 6154: 6090: 6064: 5988: 5268:// Inorder traversal: 4808: 4800: 4657://Found, return index 4193: 4159: 4095: 3949: 3886:loop 1. if 3782: 3740: 3714: 3649: 3617: 3522: 3382:, which computes the 3354: 3036:loop 1. if 2940: 2906: 2789: 2146:Refactoring recursion 1992:tail call elimination 1949:programming languages 1886:// empty product is 1 1735:important example is 1037:// assert(n >= 2); 851:Implementation issues 584:corecursion: examples 313:Further information: 115:programming languages 81:computational problem 62: 50: 9006:Computability theory 8867:Breadth-first search 7788:Recursion Via Pascal 7153:www.braveclojure.com 7030:Concrete Mathematics 6985:McCarthy 91 function 6791: 6784:. In symbolic form: 6475: 6400: 6374: 6304: 6229: 6165: 6099: 6073: 6003: 5924: 5411:Filesystem traversal 5043:// some integer data 4857:// some integer data 4169: 4113: 3978: 3905:x to y 4. 3877:new variable called 3750: 3723: 3661: 3630: 3615:{\displaystyle x\%y} 3600: 3399: 3103: 3026:new variable called 2916: 2866: 2840:1 2. otherwise, 2678: 2654:Recursive procedures 2032:functional languages 1988:functional languages 1777:functional languages 825:structural induction 802:Matthias Felleisen, 795:adaptive integration 754:is the alternative: 750:Generative recursion 718:Structural recursion 662:which in turn calls 588:threaded binary tree 391:Similarly recursive 286:Recursive data types 135:imperative languages 127:computability theory 8957:Topological sorting 8887:Dynamic programming 8641:Self-modifying code 8249:Probabilistic logic 8180:Functional reactive 8135:Expression-oriented 8089:Partial application 7854:Dijkstra, Edsger W. 7826:Sussman, Gerald Jay 7510:Salz, Rich (1991). 6578:. For example, the 5900:recurrence relation 4786:Recursive data type 4561://Get the midpoint. 3969:Function definition 3647:{\displaystyle x/y} 3594:Recurrence relation 3390:Function definition 3380:Euclidean algorithm 2857:recurrence relation 2642:Also note that the 2047:orders of magnitude 1976:Turing completeness 1953:runtime environment 1265:perfect binary tree 918:Ordinary recursion 914: 911:Factorial: ordinary 821:inductively defined 813:proving termination 706:anonymous recursion 702:anonymous functions 696:Anonymous recursion 690:Anonymous recursion 479:(5 * ((3 * 6) + 8)) 326:Recursive data type 315:Algebraic data type 182:dynamic programming 65:Sierpiński Triangle 9011:Programming idioms 8975:List of algorithms 8882:Divide and conquer 8877:Depth-first search 8872:Brute-force search 8786:Binary search tree 8554:Attribute-oriented 8327:List comprehension 8272:Algebraic modeling 8085:Anonymous function 7977:Design by contract 7947:Jackson structures 7870:10.1007/BF01386232 7614:Russell, Stuart J. 7536:Dr. Dobb's Journal 7411:Dr. Dobb's Journal 7390:Dr. Dobb's Journal 7032:. Addison-Wesley. 6905: 6514: 6460:for some constant 6450: 6386: 6370:for some constant 6360: 6288: 6215: 6149: 6085: 6069:for some constant 6059: 5983: 5429:preorder traversal 5405:Binary search tree 5401:in-order traversal 5263:as defined above. 4603://Integer division 4188: 4154: 4090: 4085: 4072: 4017: 3952: 3894:loop 2. 3777: 3735: 3709: 3644: 3612: 3517: 3512: 3499: 3441: 3349: 3347: 3340: 3327: 3251: 3044:loop 2. 3030:with a value of 1 2935: 2901: 2784: 2779: 2766: 2717: 2428:Order of execution 2160:matching wildcards 2136:Ackermann function 2124:depth-first search 2097:exception handling 2018:Performance issues 1224:depth-first search 1218:Depth-first search 913:vs. short-circuit 909: 704:, and is known as 594:Indirect recursion 566:multiple recursion 545:Types of recursion 282:th partial sum)". 85:recursive problems 69: 57: 18:Multiple recursion 8983: 8982: 8781:Associative array 8724: 8723: 8614:Program synthesis 8506:Organic computing 8442: 8441: 8347:Non-English-based 8322:Language-oriented 8100:Purely functional 8051: 8050: 7813:Walls and Mirrors 7802:978-0-521-26934-6 7752:978-1-5327-1227-2 7733:978-1-351-64717-5 7365:. Docs.python.org 7247:978-1-118-26136-1 7005:Logic programming 5431:of a filesystem. 4335: 4334: 4281: 4280: 4216: 4215: 4071: 4016: 3935: 3934: 3817: 3816: 3591: 3590: 3498: 3440: 3326: 3250: 3088: 3087: 2985: 2984: 2853: 2852: 2765: 2716: 2581:recursiveFunction 2545:recursiveFunction 2505:recursiveFunction 2445:recursiveFunction 2418: 2417: 1823: 1822: 1263:In the case of a 1173: 1172: 897:pass-by-reference 292:computer programs 16:(Redirected from 9023: 8952:String-searching 8751: 8744: 8737: 8728: 8626:by demonstration 8531:Service-oriented 8521:Process-oriented 8496:Macroprogramming 8481:Concurrent logic 8352:Page description 8342:Natural language 8312:Grammar-oriented 8239:Nondeterministic 8228:Constraint logic 8130:Point-free style 8125:Functional logic 8062: 8033:Immutable object 7952:Block-structured 7935: 7910: 7903: 7896: 7887: 7881: 7849: 7834:(2nd ed.). 7817: 7806: 7781: 7777:978-0-47170146-0 7756: 7737: 7712: 7686: 7647: 7646: 7610: 7604: 7598: 7592: 7586: 7580: 7574: 7568: 7562: 7556: 7555: 7547: 7541: 7540: 7526: 7520: 7519: 7507: 7501: 7500: 7492: 7486: 7485: 7477: 7471: 7470: 7461:Mitrovic, Ivan. 7458: 7452: 7451: 7444: 7438: 7437: 7422: 7416: 7415: 7401: 7395: 7394: 7380: 7374: 7373: 7371: 7370: 7359: 7353: 7352: 7350: 7349: 7337: 7331: 7330: 7328: 7327: 7321: 7312: 7306: 7304: 7285: 7279: 7277: 7258: 7252: 7251: 7232:(3rd ed.). 7231: 7221: 7215: 7214: 7202: 7187: 7178: 7169: 7163: 7162: 7160: 7159: 7145: 7139: 7138: 7134:978-0-13022418-7 7107: 7101: 7100: 7096:978-0-53494446-9 7076: 7070: 7069: 7059: 7050: 7044: 7043: 7021: 6980:Sierpiński curve 6914: 6912: 6911: 6906: 6768:and a path from 6748:that, for every 6681: 6678: 6675: 6672: 6669: 6666: 6663: 6660: 6657: 6654: 6651: 6648: 6645: 6642: 6639: 6636: 6633: 6630: 6627: 6624: 6621: 6618: 6615: 6612: 6609: 6606: 6603: 6600: 6597: 6594: 6591: 6588: 6577: 6573: 6569: 6568: 6565: 6562: 6545: 6534: 6530: 6523: 6521: 6520: 6515: 6470: 6466: 6459: 6457: 6456: 6451: 6422: 6395: 6393: 6392: 6387: 6369: 6367: 6366: 6361: 6356: 6355: 6342: 6341: 6297: 6295: 6294: 6289: 6275: 6274: 6267: 6266: 6224: 6222: 6221: 6216: 6211: 6210: 6203: 6202: 6158: 6156: 6155: 6150: 6145: 6144: 6137: 6136: 6094: 6092: 6091: 6086: 6068: 6066: 6065: 6060: 6055: 6054: 6041: 6040: 5992: 5990: 5989: 5984: 5961: 5872: 5869: 5866: 5863: 5860: 5857: 5854: 5851: 5848: 5845: 5842: 5839: 5836: 5833: 5830: 5827: 5824: 5821: 5818: 5815: 5812: 5809: 5806: 5803: 5800: 5797: 5794: 5791: 5788: 5785: 5782: 5779: 5776: 5773: 5770: 5767: 5764: 5761: 5758: 5755: 5752: 5749: 5746: 5743: 5740: 5737: 5734: 5731: 5728: 5725: 5722: 5719: 5716: 5713: 5710: 5707: 5704: 5701: 5698: 5695: 5692: 5689: 5686: 5683: 5680: 5677: 5674: 5671: 5668: 5665: 5662: 5659: 5656: 5653: 5650: 5647: 5644: 5641: 5638: 5635: 5632: 5629: 5626: 5623: 5620: 5617: 5614: 5611: 5608: 5605: 5602: 5599: 5596: 5593: 5590: 5587: 5584: 5581: 5578: 5575: 5572: 5569: 5566: 5563: 5560: 5557: 5554: 5551: 5548: 5545: 5542: 5539: 5536: 5533: 5530: 5527: 5524: 5521: 5518: 5515: 5512: 5509: 5506: 5503: 5500: 5497: 5494: 5491: 5488: 5485: 5482: 5479: 5476: 5473: 5470: 5467: 5464: 5461: 5458: 5455: 5452: 5449: 5446: 5443: 5440: 5437: 5395: 5392: 5389: 5386: 5383: 5380: 5377: 5374: 5371: 5368: 5365: 5362: 5359: 5356: 5353: 5350: 5347: 5344: 5341: 5338: 5335: 5332: 5329: 5326: 5323: 5320: 5317: 5314: 5311: 5308: 5305: 5302: 5299: 5296: 5293: 5290: 5287: 5284: 5281: 5278: 5275: 5272: 5269: 5255: 5252: 5249: 5246: 5243: 5240: 5237: 5234: 5231: 5228: 5225: 5222: 5219: 5216: 5213: 5210: 5207: 5204: 5201: 5198: 5195: 5192: 5189: 5186: 5183: 5180: 5177: 5174: 5171: 5168: 5165: 5162: 5159: 5156: 5153: 5150: 5147: 5144: 5141: 5138: 5135: 5132: 5129: 5126: 5123: 5120: 5117: 5114: 5111: 5108: 5105: 5102: 5099: 5096: 5093: 5083: 5080: 5077: 5074: 5071: 5068: 5065: 5062: 5059: 5056: 5053: 5050: 5047: 5044: 5041: 5038: 5035: 5032: 5029: 5026: 5004: 5001: 4998: 4995: 4992: 4989: 4986: 4983: 4980: 4977: 4974: 4971: 4968: 4965: 4962: 4959: 4956: 4953: 4950: 4947: 4944: 4941: 4938: 4935: 4932: 4929: 4926: 4923: 4920: 4917: 4914: 4911: 4908: 4905: 4902: 4879: 4876: 4873: 4870: 4867: 4864: 4861: 4858: 4855: 4852: 4849: 4846: 4843: 4840: 4775: 4772: 4769: 4766: 4763: 4760: 4757: 4754: 4751: 4748: 4745: 4742: 4739: 4736: 4733: 4730: 4727: 4724: 4721: 4718: 4715: 4712: 4709: 4706: 4703: 4700: 4697: 4694: 4691: 4688: 4685: 4682: 4679: 4676: 4673: 4670: 4667: 4664: 4661: 4658: 4655: 4652: 4649: 4646: 4643: 4640: 4637: 4634: 4631: 4628: 4625: 4622: 4619: 4616: 4613: 4610: 4607: 4604: 4601: 4598: 4595: 4592: 4589: 4586: 4583: 4580: 4577: 4574: 4571: 4568: 4565: 4562: 4559: 4556: 4553: 4550: 4547: 4544: 4541: 4538: 4535: 4532: 4529: 4526: 4523: 4520: 4517: 4514: 4511: 4508: 4505: 4502: 4499: 4496: 4493: 4490: 4487: 4484: 4481: 4478: 4475: 4472: 4469: 4466: 4463: 4460: 4457: 4454: 4451: 4448: 4445: 4442: 4439: 4436: 4433: 4430: 4427: 4424: 4421: 4418: 4415: 4412: 4409: 4406: 4403: 4400: 4397: 4394: 4391: 4388: 4385: 4382: 4379: 4376: 4373: 4370: 4367: 4364: 4286: 4224: 4201: 4197: 4195: 4194: 4189: 4181: 4180: 4163: 4161: 4160: 4155: 4147: 4146: 4125: 4124: 4099: 4097: 4096: 4091: 4089: 4088: 4073: 4069: 4018: 4014: 3834: 3790: 3786: 3784: 3783: 3778: 3744: 3742: 3741: 3736: 3718: 3716: 3715: 3710: 3653: 3651: 3650: 3645: 3640: 3621: 3619: 3618: 3613: 3530: 3526: 3524: 3523: 3518: 3516: 3515: 3500: 3496: 3442: 3438: 3358: 3356: 3355: 3350: 3348: 3344: 3343: 3328: 3324: 3292: 3291: 3290: 3252: 3248: 3207: 3206: 3205: 3158: 3157: 3156: 3095: 2990: 2951: 2944: 2942: 2941: 2936: 2928: 2927: 2910: 2908: 2907: 2902: 2900: 2899: 2878: 2877: 2797: 2793: 2791: 2790: 2785: 2783: 2782: 2767: 2763: 2718: 2714: 2632: 2624: 2621: 2618: 2615: 2612: 2609: 2606: 2603: 2600: 2597: 2594: 2591: 2588: 2585: 2582: 2579: 2576: 2573: 2570: 2567: 2564: 2561: 2558: 2555: 2552: 2549: 2546: 2543: 2532: 2524: 2521: 2518: 2515: 2512: 2509: 2506: 2503: 2500: 2497: 2494: 2491: 2488: 2485: 2482: 2479: 2476: 2473: 2470: 2467: 2464: 2461: 2458: 2455: 2452: 2449: 2446: 2443: 2412: 2409: 2406: 2403: 2400: 2397: 2394: 2391: 2388: 2385: 2382: 2379: 2376: 2373: 2370: 2367: 2364: 2361: 2358: 2355: 2352: 2349: 2346: 2343: 2340: 2337: 2334: 2331: 2322: 2319: 2316: 2313: 2310: 2307: 2304: 2301: 2298: 2295: 2292: 2289: 2286: 2283: 2280: 2277: 2274: 2271: 2268: 2265: 2262: 2259: 2256: 2253: 2250: 2247: 2244: 2241: 2238: 2235: 2232: 2214: 1943:Expressive power 1938: 1935: 1932: 1929: 1926: 1923: 1920: 1917: 1914: 1911: 1908: 1905: 1902: 1899: 1896: 1893: 1890: 1887: 1884: 1881: 1878: 1875: 1872: 1869: 1866: 1863: 1860: 1857: 1854: 1851: 1848: 1845: 1842: 1801: 1800: 1745:tiled merge sort 1730:Hybrid algorithm 1717:Note the use of 1713: 1710: 1707: 1704: 1701: 1698: 1695: 1692: 1689: 1688:tree_contains_do 1686: 1683: 1680: 1677: 1674: 1671: 1668: 1665: 1662: 1659: 1656: 1653: 1650: 1647: 1646:tree_contains_do 1644: 1641: 1638: 1635: 1632: 1629: 1626: 1623: 1620: 1617: 1614: 1611: 1608: 1605: 1602: 1599: 1596: 1593: 1590: 1587: 1584: 1581: 1578: 1575: 1572: 1569: 1566: 1563: 1560: 1557: 1554: 1553:tree_contains_do 1551: 1548: 1545: 1542: 1539: 1536: 1533: 1530: 1527: 1524: 1523:tree_contains_do 1521: 1518: 1515: 1512: 1509: 1506: 1503: 1500: 1497: 1494: 1491: 1488: 1485: 1482: 1479: 1476: 1473: 1470: 1467: 1464: 1461: 1458: 1455: 1452: 1449: 1439: 1436: 1433: 1430: 1427: 1424: 1421: 1418: 1415: 1412: 1409: 1406: 1403: 1400: 1397: 1394: 1391: 1388: 1385: 1382: 1379: 1376: 1373: 1370: 1367: 1364: 1361: 1358: 1355: 1352: 1349: 1346: 1343: 1340: 1337: 1334: 1331: 1328: 1325: 1322: 1319: 1316: 1313: 1310: 1307: 1304: 1301: 1298: 1295: 1292: 1289: 1286: 1283: 1280: 1209: 1201: 1167: 1164: 1161: 1158: 1155: 1152: 1149: 1146: 1143: 1140: 1137: 1134: 1131: 1128: 1125: 1122: 1119: 1116: 1113: 1110: 1107: 1104: 1101: 1098: 1095: 1092: 1089: 1086: 1083: 1080: 1077: 1074: 1071: 1068: 1065: 1062: 1059: 1056: 1053: 1050: 1047: 1044: 1041: 1038: 1035: 1032: 1029: 1026: 1023: 1020: 1017: 1008: 1005: 1002: 999: 996: 993: 990: 987: 984: 981: 978: 975: 972: 969: 966: 963: 960: 957: 954: 951: 948: 945: 942: 939: 936: 933: 930: 915: 912: 893:nested functions 881:wrapper function 875:Wrapper function 807: 752: 751: 739: 644:mutual recursion 600:Mutual recursion 568: 567: 560: 559: 558:single recursion 524: 520: 480: 471: 468: 465: 461: 458: 455: 451: 448: 445: 441: 438: 435: 431: 428: 425: 422: 419: 416: 413: 405:Backus–Naur form 365: 362: 359: 356: 353: 350: 347: 344: 304:self-referential 265: 237: 222: 215: 170:algorithm design 144: 140: 109: 73:computer science 21: 9031: 9030: 9026: 9025: 9024: 9022: 9021: 9020: 8986: 8985: 8984: 8979: 8961: 8892:Graph traversal 8845: 8769:Data structures 8764: 8758:Data structures 8755: 8725: 8720: 8662: 8655: 8546:Metaprogramming 8540: 8456: 8451: 8438: 8420:Graph rewriting 8258: 8234:Inductive logic 8214:Abductive logic 8200: 8157: 8120:Dependent types 8068: 8047: 8019:Prototype-based 7999: 7997:Object-oriented 7991: 7987:Nested function 7982:Invariant-based 7924: 7914: 7884: 7852: 7846: 7822:Abelson, Harold 7820: 7809: 7803: 7784: 7778: 7759: 7753: 7740: 7734: 7715: 7709: 7690: 7687:(viii+64 pages) 7683: 7660: 7656: 7651: 7650: 7635: 7612: 7611: 7607: 7599: 7595: 7587: 7583: 7575: 7571: 7563: 7559: 7549: 7548: 7544: 7528: 7527: 7523: 7509: 7508: 7504: 7494: 7493: 7489: 7479: 7478: 7474: 7460: 7459: 7455: 7446: 7445: 7441: 7424: 7423: 7419: 7403: 7402: 7398: 7382: 7381: 7377: 7368: 7366: 7361: 7360: 7356: 7347: 7345: 7339: 7338: 7334: 7325: 7323: 7319: 7315:Shivers, Olin. 7314: 7313: 7309: 7302: 7287: 7286: 7282: 7275: 7260: 7259: 7255: 7248: 7223: 7222: 7218: 7211: 7200: 7189: 7188: 7181: 7170: 7166: 7157: 7155: 7147: 7146: 7142: 7135: 7109: 7108: 7104: 7097: 7078: 7077: 7073: 7057: 7052: 7051: 7047: 7040: 7023: 7022: 7018: 7013: 6945: 6789: 6788: 6683: 6682: 6679: 6676: 6673: 6670: 6667: 6664: 6661: 6658: 6655: 6652: 6649: 6646: 6643: 6640: 6637: 6634: 6631: 6628: 6625: 6622: 6619: 6616: 6613: 6610: 6607: 6604: 6601: 6598: 6595: 6592: 6589: 6586: 6575: 6571: 6566: 6563: 6560: 6552: 6536: 6532: 6528: 6473: 6472: 6468: 6461: 6398: 6397: 6372: 6371: 6333: 6328: 6302: 6301: 6258: 6253: 6227: 6226: 6194: 6189: 6163: 6162: 6128: 6123: 6097: 6096: 6071: 6070: 6032: 6027: 6001: 6000: 5922: 5921: 5918: 5912: 5896:time efficiency 5892: 5874: 5873: 5870: 5867: 5864: 5861: 5858: 5855: 5852: 5849: 5846: 5843: 5840: 5837: 5834: 5831: 5828: 5825: 5822: 5819: 5816: 5813: 5810: 5807: 5804: 5801: 5798: 5795: 5792: 5789: 5786: 5783: 5780: 5777: 5774: 5771: 5768: 5765: 5762: 5759: 5756: 5753: 5750: 5747: 5744: 5741: 5738: 5735: 5732: 5729: 5726: 5723: 5720: 5717: 5714: 5711: 5708: 5705: 5702: 5699: 5696: 5693: 5690: 5687: 5684: 5681: 5678: 5675: 5672: 5669: 5666: 5663: 5660: 5657: 5654: 5651: 5648: 5645: 5642: 5639: 5636: 5633: 5630: 5627: 5624: 5621: 5618: 5615: 5612: 5609: 5606: 5603: 5600: 5597: 5594: 5591: 5588: 5585: 5582: 5579: 5576: 5573: 5570: 5567: 5564: 5561: 5558: 5555: 5552: 5549: 5546: 5543: 5540: 5537: 5534: 5531: 5528: 5525: 5522: 5519: 5516: 5513: 5510: 5507: 5504: 5501: 5498: 5495: 5492: 5489: 5486: 5483: 5480: 5477: 5474: 5471: 5468: 5465: 5462: 5459: 5456: 5453: 5450: 5447: 5444: 5441: 5438: 5435: 5413: 5397: 5396: 5393: 5390: 5387: 5384: 5381: 5378: 5375: 5372: 5369: 5366: 5363: 5360: 5357: 5354: 5351: 5349:"%d " 5348: 5345: 5342: 5339: 5336: 5333: 5330: 5327: 5324: 5321: 5318: 5315: 5312: 5309: 5306: 5303: 5300: 5297: 5294: 5291: 5288: 5285: 5282: 5279: 5276: 5273: 5270: 5267: 5257: 5256: 5253: 5250: 5247: 5244: 5241: 5238: 5235: 5232: 5229: 5226: 5223: 5220: 5217: 5214: 5211: 5208: 5205: 5202: 5199: 5196: 5193: 5190: 5187: 5184: 5181: 5178: 5175: 5172: 5169: 5166: 5163: 5160: 5157: 5154: 5151: 5148: 5145: 5142: 5139: 5136: 5133: 5130: 5127: 5124: 5121: 5118: 5115: 5112: 5109: 5106: 5103: 5100: 5097: 5094: 5091: 5085: 5084: 5081: 5078: 5075: 5072: 5069: 5066: 5063: 5060: 5057: 5054: 5051: 5048: 5045: 5042: 5039: 5036: 5033: 5030: 5027: 5024: 5017: 5011: 5006: 5005: 5002: 4999: 4996: 4993: 4990: 4987: 4984: 4981: 4978: 4975: 4972: 4969: 4966: 4963: 4960: 4958:"%d " 4957: 4954: 4951: 4948: 4945: 4942: 4939: 4936: 4933: 4930: 4927: 4924: 4921: 4918: 4915: 4912: 4909: 4906: 4903: 4900: 4881: 4880: 4877: 4874: 4871: 4868: 4865: 4862: 4859: 4856: 4853: 4850: 4847: 4844: 4841: 4838: 4824: 4818: 4788: 4782: 4777: 4776: 4773: 4770: 4767: 4764: 4761: 4758: 4755: 4752: 4749: 4746: 4743: 4740: 4737: 4734: 4731: 4728: 4725: 4722: 4719: 4716: 4713: 4710: 4707: 4704: 4701: 4698: 4695: 4692: 4689: 4686: 4683: 4680: 4677: 4674: 4671: 4668: 4665: 4662: 4659: 4656: 4653: 4650: 4647: 4644: 4641: 4638: 4635: 4632: 4629: 4626: 4623: 4620: 4617: 4614: 4611: 4608: 4605: 4602: 4599: 4596: 4593: 4590: 4587: 4584: 4581: 4578: 4575: 4572: 4569: 4566: 4563: 4560: 4557: 4554: 4551: 4548: 4545: 4542: 4539: 4536: 4533: 4530: 4527: 4524: 4521: 4518: 4515: 4512: 4509: 4506: 4504:-1 if not found 4503: 4500: 4497: 4494: 4491: 4488: 4485: 4482: 4479: 4476: 4473: 4470: 4467: 4464: 4461: 4458: 4455: 4452: 4449: 4446: 4443: 4440: 4437: 4434: 4431: 4428: 4425: 4422: 4419: 4416: 4413: 4410: 4407: 4404: 4401: 4398: 4395: 4392: 4389: 4386: 4383: 4380: 4377: 4374: 4371: 4368: 4365: 4362: 4340: 4331: 4329: 4324: 4322: 4319:= 63 = 2 - 1 h 4318: 4315:= 31 = 2 - 1 h 4314: 4311:= 15 = 2 - 1 h 4310: 4307:= 7 = 2 - 1 h 4306: 4303:= 3 = 2 - 1 h 4302: 4299:= 1 = 2 - 1 h 4298: 4277: 4272: 4266: 4256: 4240: 4218: 4212: 4172: 4167: 4166: 4132: 4116: 4111: 4110: 4084: 4083: 4065: 4029: 4028: 4010: 4000: 3976: 3975: 3958: 3956:Towers of Hanoi 3950:Towers of Hanoi 3944: 3942:Towers of Hanoi 3931: 3926: 3918: 3881: 3872: 3847: 3813: 3800: 3748: 3747: 3721: 3720: 3659: 3658: 3628: 3627: 3598: 3597: 3587: 3582: 3566: 3511: 3510: 3492: 3453: 3452: 3434: 3424: 3397: 3396: 3376: 3346: 3345: 3339: 3338: 3320: 3276: 3263: 3262: 3244: 3234: 3226: 3191: 3178: 3177: 3142: 3125: 3101: 3100: 3094: 3091: 3084: 3079: 3071: 3059:) 3. 3031: 3021: 3016: 3003: 2981: 2979: 2975: 2971: 2967: 2963: 2919: 2914: 2913: 2885: 2869: 2864: 2863: 2849: 2844: 2831: 2826: 2813: 2778: 2777: 2759: 2729: 2728: 2710: 2700: 2676: 2675: 2661: 2656: 2626: 2625: 2622: 2619: 2616: 2613: 2610: 2607: 2604: 2601: 2598: 2595: 2592: 2589: 2586: 2583: 2580: 2577: 2574: 2571: 2568: 2565: 2562: 2559: 2556: 2553: 2550: 2547: 2544: 2541: 2538: 2526: 2525: 2522: 2519: 2516: 2513: 2510: 2507: 2504: 2501: 2498: 2495: 2492: 2489: 2486: 2483: 2480: 2477: 2474: 2471: 2468: 2465: 2462: 2459: 2456: 2453: 2450: 2447: 2444: 2441: 2438: 2430: 2414: 2413: 2410: 2407: 2404: 2401: 2398: 2395: 2392: 2389: 2386: 2383: 2380: 2377: 2374: 2371: 2368: 2365: 2362: 2359: 2356: 2353: 2350: 2347: 2344: 2341: 2338: 2335: 2332: 2329: 2324: 2323: 2320: 2317: 2314: 2311: 2308: 2305: 2302: 2299: 2296: 2293: 2290: 2287: 2284: 2281: 2278: 2275: 2272: 2269: 2266: 2263: 2260: 2257: 2254: 2251: 2248: 2245: 2242: 2239: 2236: 2233: 2230: 2188: 2148: 2116: 2084: 2068:stack overflows 2056: 2020: 1945: 1940: 1939: 1936: 1933: 1930: 1927: 1924: 1921: 1918: 1915: 1912: 1909: 1906: 1903: 1900: 1897: 1894: 1891: 1888: 1885: 1882: 1879: 1876: 1873: 1870: 1867: 1864: 1861: 1858: 1855: 1852: 1849: 1846: 1843: 1840: 1828:For example, a 1819: 1817: 1810: 1808: 1797: 1793: 1789: 1785: 1757: 1732: 1715: 1714: 1711: 1708: 1705: 1702: 1699: 1696: 1693: 1690: 1687: 1684: 1681: 1678: 1675: 1672: 1669: 1666: 1663: 1660: 1657: 1654: 1651: 1648: 1645: 1642: 1639: 1636: 1633: 1630: 1627: 1624: 1621: 1618: 1615: 1612: 1609: 1606: 1603: 1600: 1597: 1594: 1591: 1588: 1585: 1582: 1579: 1576: 1573: 1570: 1567: 1564: 1561: 1558: 1555: 1552: 1549: 1546: 1543: 1540: 1537: 1534: 1531: 1528: 1525: 1522: 1519: 1516: 1513: 1510: 1507: 1504: 1501: 1498: 1495: 1492: 1489: 1486: 1483: 1480: 1477: 1474: 1471: 1468: 1465: 1462: 1459: 1456: 1453: 1450: 1447: 1441: 1440: 1437: 1434: 1431: 1428: 1425: 1422: 1419: 1416: 1413: 1410: 1407: 1404: 1401: 1398: 1395: 1392: 1389: 1386: 1383: 1380: 1377: 1374: 1371: 1368: 1365: 1362: 1359: 1356: 1353: 1350: 1347: 1344: 1341: 1338: 1335: 1332: 1329: 1326: 1323: 1320: 1317: 1314: 1311: 1308: 1305: 1302: 1299: 1296: 1293: 1290: 1287: 1284: 1281: 1278: 1220: 1204: 1192: 1169: 1168: 1165: 1162: 1159: 1156: 1153: 1150: 1147: 1144: 1141: 1138: 1135: 1132: 1129: 1126: 1123: 1120: 1117: 1114: 1111: 1108: 1105: 1102: 1099: 1096: 1093: 1090: 1087: 1084: 1081: 1078: 1075: 1072: 1069: 1066: 1063: 1060: 1057: 1054: 1051: 1048: 1045: 1042: 1039: 1036: 1033: 1030: 1027: 1024: 1021: 1018: 1015: 1010: 1009: 1006: 1003: 1000: 997: 994: 991: 988: 985: 982: 979: 976: 973: 970: 967: 964: 961: 958: 955: 952: 949: 946: 943: 940: 937: 934: 931: 928: 910: 905: 877: 853: 815:of a function. 808: 801: 787:Newton's method 749: 748: 740: 731: 720: 714: 698: 692: 602: 596: 565: 564: 557: 556: 552: 547: 522: 518: 511: 497: 489:Main articles: 487: 478: 474: 473: 469: 466: 463: 459: 456: 453: 452:) | ( 449: 446: 443: 439: 436: 433: 429: 426: 423: 420: 417: 414: 411: 389: 379:natural numbers 367: 366: 363: 360: 357: 354: 351: 348: 345: 342: 328: 322: 317: 288: 258: 224: 217: 213: 206:recursive cases 194: 166: 131:Turing complete 110: 100: 43: 28: 23: 22: 15: 12: 11: 5: 9029: 9027: 9019: 9018: 9013: 9008: 9003: 8998: 8988: 8987: 8981: 8980: 8978: 8977: 8972: 8966: 8963: 8962: 8960: 8959: 8954: 8949: 8944: 8939: 8934: 8929: 8924: 8919: 8914: 8909: 8904: 8899: 8894: 8889: 8884: 8879: 8874: 8869: 8864: 8859: 8853: 8851: 8847: 8846: 8844: 8843: 8838: 8833: 8828: 8823: 8818: 8813: 8808: 8803: 8798: 8793: 8788: 8783: 8778: 8772: 8770: 8766: 8765: 8756: 8754: 8753: 8746: 8739: 8731: 8722: 8721: 8719: 8718: 8713: 8708: 8703: 8698: 8693: 8688: 8683: 8678: 8673: 8667: 8665: 8657: 8656: 8654: 8653: 8648: 8643: 8638: 8633: 8611: 8606: 8601: 8591: 8586: 8581: 8576: 8571: 8566: 8556: 8550: 8548: 8542: 8541: 8539: 8538: 8533: 8528: 8523: 8518: 8513: 8508: 8503: 8498: 8493: 8488: 8478: 8473: 8468: 8462: 8460: 8444: 8443: 8440: 8439: 8437: 8436: 8431: 8416:Transformation 8413: 8408: 8403: 8398: 8393: 8388: 8383: 8378: 8373: 8368: 8363: 8354: 8349: 8344: 8339: 8334: 8329: 8324: 8319: 8314: 8309: 8304: 8302:Differentiable 8299: 8289: 8282:Automata-based 8279: 8274: 8268: 8266: 8260: 8259: 8257: 8256: 8251: 8246: 8241: 8236: 8231: 8221: 8216: 8210: 8208: 8202: 8201: 8199: 8198: 8193: 8188: 8183: 8173: 8167: 8165: 8159: 8158: 8156: 8155: 8149:Function-level 8146: 8137: 8132: 8127: 8122: 8117: 8112: 8107: 8102: 8097: 8092: 8082: 8076: 8074: 8059: 8053: 8052: 8049: 8048: 8046: 8045: 8040: 8035: 8030: 8025: 8011: 8009: 7993: 7992: 7990: 7989: 7984: 7979: 7974: 7969: 7964: 7962:Non-structured 7959: 7954: 7949: 7943: 7941: 7932: 7926: 7925: 7915: 7913: 7912: 7905: 7898: 7890: 7883: 7882: 7864:(1): 312–318. 7850: 7844: 7818: 7807: 7801: 7782: 7776: 7757: 7751: 7738: 7732: 7713: 7707: 7688: 7681: 7657: 7655: 7652: 7649: 7648: 7634:978-0134610993 7633: 7618:Norvig, Peter. 7605: 7593: 7581: 7569: 7557: 7542: 7521: 7502: 7487: 7484:. CodeProject. 7472: 7453: 7439: 7417: 7396: 7375: 7354: 7332: 7307: 7300: 7280: 7273: 7253: 7246: 7216: 7209: 7179: 7164: 7140: 7133: 7111:Wirth, Niklaus 7102: 7095: 7071: 7045: 7038: 7015: 7014: 7012: 7009: 7008: 7007: 7002: 7000:Tak (function) 6997: 6992: 6987: 6982: 6977: 6971: 6969:Open recursion 6966: 6961: 6956: 6951: 6944: 6941: 6916: 6915: 6904: 6901: 6898: 6895: 6892: 6889: 6886: 6883: 6880: 6877: 6874: 6871: 6868: 6865: 6862: 6859: 6856: 6853: 6850: 6847: 6844: 6841: 6838: 6835: 6832: 6829: 6826: 6823: 6820: 6817: 6814: 6811: 6808: 6805: 6802: 6799: 6796: 6585: 6556:logic programs 6551: 6548: 6525: 6524: 6513: 6510: 6507: 6504: 6501: 6498: 6495: 6492: 6489: 6486: 6483: 6480: 6449: 6446: 6443: 6440: 6437: 6434: 6431: 6428: 6425: 6421: 6417: 6414: 6411: 6408: 6405: 6385: 6382: 6379: 6359: 6354: 6351: 6348: 6345: 6340: 6336: 6331: 6327: 6324: 6321: 6318: 6315: 6312: 6309: 6298: 6287: 6284: 6281: 6278: 6273: 6270: 6265: 6261: 6256: 6252: 6249: 6246: 6243: 6240: 6237: 6234: 6214: 6209: 6206: 6201: 6197: 6192: 6188: 6185: 6182: 6179: 6176: 6173: 6170: 6159: 6148: 6143: 6140: 6135: 6131: 6126: 6122: 6119: 6116: 6113: 6110: 6107: 6104: 6084: 6081: 6078: 6058: 6053: 6050: 6047: 6044: 6039: 6035: 6030: 6026: 6023: 6020: 6017: 6014: 6011: 6008: 5982: 5979: 5976: 5973: 5970: 5967: 5964: 5960: 5956: 5953: 5950: 5947: 5944: 5941: 5938: 5935: 5932: 5929: 5914:Main article: 5911: 5908: 5904:Big O notation 5891: 5888: 5434: 5425:tree traversal 5412: 5409: 5266: 5090: 5023: 5013:Main article: 5010: 5007: 4899: 4837: 4820:Main article: 4817: 4814: 4784:Main article: 4781: 4778: 4361: 4339: 4336: 4333: 4332: 4327: 4325: 4323:= 127 = 2 - 1 4320: 4316: 4312: 4308: 4304: 4300: 4296: 4294: 4291: 4290: 4279: 4278: 4235: 4232: 4231: 4214: 4213: 4209: 4206: 4205: 4199: 4198: 4187: 4184: 4179: 4175: 4164: 4153: 4150: 4145: 4142: 4139: 4135: 4131: 4128: 4123: 4119: 4101: 4100: 4087: 4082: 4079: 4076: 4066: 4064: 4061: 4058: 4055: 4052: 4049: 4046: 4043: 4040: 4037: 4034: 4031: 4030: 4027: 4024: 4021: 4011: 4009: 4006: 4005: 4003: 3998: 3995: 3992: 3989: 3986: 3983: 3954:Main article: 3943: 3940: 3933: 3932: 3842: 3839: 3838: 3821:tail-recursive 3815: 3814: 3810: 3807: 3806: 3802: 3801: 3798: 3795: 3794: 3788: 3787: 3776: 3773: 3770: 3767: 3764: 3761: 3758: 3755: 3745: 3734: 3731: 3728: 3708: 3705: 3702: 3699: 3696: 3693: 3690: 3687: 3684: 3681: 3678: 3675: 3672: 3669: 3666: 3643: 3639: 3635: 3622:expresses the 3611: 3608: 3605: 3589: 3588: 3578:2. otherwise, 3541: 3538: 3537: 3528: 3527: 3514: 3509: 3506: 3503: 3493: 3491: 3488: 3485: 3482: 3479: 3476: 3473: 3470: 3467: 3464: 3461: 3458: 3455: 3454: 3451: 3448: 3445: 3435: 3433: 3430: 3429: 3427: 3422: 3419: 3416: 3413: 3410: 3407: 3404: 3375: 3372: 3360: 3359: 3342: 3337: 3334: 3331: 3321: 3319: 3316: 3313: 3310: 3307: 3304: 3301: 3298: 3295: 3289: 3286: 3283: 3279: 3275: 3272: 3269: 3265: 3264: 3261: 3258: 3255: 3245: 3243: 3240: 3239: 3237: 3232: 3229: 3227: 3225: 3222: 3219: 3216: 3213: 3210: 3204: 3201: 3198: 3194: 3190: 3187: 3184: 3180: 3179: 3176: 3173: 3170: 3167: 3164: 3161: 3155: 3152: 3149: 3145: 3141: 3138: 3135: 3131: 3128: 3126: 3124: 3121: 3118: 3115: 3112: 3109: 3108: 3092: 3086: 3085: 2998: 2995: 2994: 2983: 2982: 2977: 2973: 2969: 2965: 2961: 2959: 2956: 2955: 2946: 2945: 2934: 2931: 2926: 2922: 2911: 2898: 2895: 2892: 2888: 2884: 2881: 2876: 2872: 2851: 2850: 2808: 2805: 2804: 2795: 2794: 2781: 2776: 2773: 2770: 2760: 2758: 2755: 2752: 2749: 2746: 2743: 2740: 2737: 2734: 2731: 2730: 2727: 2724: 2721: 2711: 2709: 2706: 2705: 2703: 2698: 2695: 2692: 2689: 2686: 2683: 2669:natural number 2660: 2657: 2655: 2652: 2540: 2537: 2534: 2440: 2437: 2434: 2429: 2426: 2416: 2415: 2328: 2325: 2229: 2225: 2224: 2221: 2218:Tail recursion 2187: 2184: 2147: 2144: 2120:tree traversal 2115: 2112: 2083: 2080: 2076:tail recursion 2055: 2052: 2019: 2016: 1944: 1941: 1839: 1821: 1820: 1815: 1813: 1811: 1806: 1804: 1795: 1791: 1787: 1783: 1769:tail recursion 1759:Recursion and 1756: 1753: 1741:insertion sort 1731: 1728: 1446: 1277: 1253: 1252: 1249: 1242: 1241: 1238: 1219: 1216: 1171: 1170: 1014: 1011: 927: 923: 922: 919: 904: 901: 876: 873: 868: 867: 864: 861: 852: 849: 848: 847: 843: 836: 832:infinite loops 828: 799: 729: 713: 710: 694:Main article: 691: 688: 598:Main article: 595: 592: 572:tree traversal 551: 548: 546: 543: 509: 486: 483: 410: 387: 341: 324:Main article: 321: 318: 287: 284: 193: 190: 165: 162: 113:Most computer 98: 26: 24: 14: 13: 10: 9: 6: 4: 3: 2: 9028: 9017: 9014: 9012: 9009: 9007: 9004: 9002: 8999: 8997: 8994: 8993: 8991: 8976: 8973: 8971: 8968: 8967: 8964: 8958: 8955: 8953: 8950: 8948: 8945: 8943: 8940: 8938: 8935: 8933: 8930: 8928: 8925: 8923: 8920: 8918: 8915: 8913: 8910: 8908: 8907:Hash function 8905: 8903: 8900: 8898: 8895: 8893: 8890: 8888: 8885: 8883: 8880: 8878: 8875: 8873: 8870: 8868: 8865: 8863: 8862:Binary search 8860: 8858: 8855: 8854: 8852: 8848: 8842: 8839: 8837: 8834: 8832: 8829: 8827: 8824: 8822: 8819: 8817: 8814: 8812: 8809: 8807: 8804: 8802: 8799: 8797: 8794: 8792: 8789: 8787: 8784: 8782: 8779: 8777: 8774: 8773: 8771: 8767: 8763: 8759: 8752: 8747: 8745: 8740: 8738: 8733: 8732: 8729: 8717: 8714: 8712: 8709: 8707: 8704: 8702: 8699: 8697: 8694: 8692: 8689: 8687: 8686:Data-oriented 8684: 8682: 8679: 8677: 8674: 8672: 8669: 8668: 8666: 8664: 8658: 8652: 8649: 8647: 8644: 8642: 8639: 8637: 8634: 8631: 8627: 8623: 8619: 8615: 8612: 8610: 8607: 8605: 8602: 8599: 8595: 8592: 8590: 8587: 8585: 8584:Homoiconicity 8582: 8580: 8577: 8575: 8572: 8570: 8567: 8564: 8560: 8557: 8555: 8552: 8551: 8549: 8547: 8543: 8537: 8534: 8532: 8529: 8527: 8524: 8522: 8519: 8517: 8514: 8512: 8509: 8507: 8504: 8502: 8499: 8497: 8494: 8492: 8491:Concurrent OO 8489: 8486: 8482: 8479: 8477: 8474: 8472: 8469: 8467: 8464: 8463: 8461: 8459: 8454: 8449: 8445: 8435: 8432: 8429: 8425: 8421: 8417: 8414: 8412: 8409: 8407: 8404: 8402: 8399: 8397: 8394: 8392: 8389: 8387: 8386:Set-theoretic 8384: 8382: 8379: 8377: 8374: 8372: 8369: 8367: 8366:Probabilistic 8364: 8362: 8358: 8355: 8353: 8350: 8348: 8345: 8343: 8340: 8338: 8335: 8333: 8330: 8328: 8325: 8323: 8320: 8318: 8315: 8313: 8310: 8308: 8305: 8303: 8300: 8297: 8293: 8290: 8287: 8283: 8280: 8278: 8275: 8273: 8270: 8269: 8267: 8265: 8261: 8255: 8252: 8250: 8247: 8245: 8242: 8240: 8237: 8235: 8232: 8229: 8225: 8222: 8220: 8217: 8215: 8212: 8211: 8209: 8207: 8203: 8197: 8194: 8192: 8189: 8187: 8184: 8181: 8177: 8174: 8172: 8169: 8168: 8166: 8164: 8160: 8154: 8150: 8147: 8145: 8144:Concatenative 8141: 8138: 8136: 8133: 8131: 8128: 8126: 8123: 8121: 8118: 8116: 8113: 8111: 8108: 8106: 8103: 8101: 8098: 8096: 8093: 8090: 8086: 8083: 8081: 8078: 8077: 8075: 8072: 8067: 8063: 8060: 8058: 8054: 8044: 8041: 8039: 8036: 8034: 8031: 8029: 8026: 8024: 8020: 8016: 8013: 8012: 8010: 8007: 8003: 7998: 7994: 7988: 7985: 7983: 7980: 7978: 7975: 7973: 7970: 7968: 7965: 7963: 7960: 7958: 7955: 7953: 7950: 7948: 7945: 7944: 7942: 7940: 7936: 7933: 7931: 7927: 7922: 7918: 7911: 7906: 7904: 7899: 7897: 7892: 7891: 7888: 7879: 7875: 7871: 7867: 7863: 7859: 7855: 7851: 7847: 7845:0-262-51087-1 7841: 7837: 7833: 7832: 7827: 7823: 7819: 7815: 7814: 7808: 7804: 7798: 7794: 7790: 7789: 7783: 7779: 7773: 7769: 7765: 7764: 7758: 7754: 7748: 7744: 7739: 7735: 7729: 7725: 7721: 7720: 7714: 7710: 7704: 7700: 7696: 7695: 7689: 7684: 7678: 7675: 7671: 7667: 7666:Gill, Stanley 7663: 7659: 7658: 7653: 7644: 7640: 7636: 7630: 7626: 7624: 7619: 7615: 7609: 7606: 7603:, p. 127 7602: 7597: 7594: 7590: 7585: 7582: 7578: 7573: 7570: 7566: 7561: 7558: 7553: 7546: 7543: 7538: 7537: 7532: 7525: 7522: 7517: 7513: 7506: 7503: 7498: 7491: 7488: 7483: 7476: 7473: 7468: 7464: 7457: 7454: 7449: 7443: 7440: 7435: 7431: 7427: 7421: 7418: 7413: 7412: 7407: 7400: 7397: 7392: 7391: 7386: 7379: 7376: 7364: 7358: 7355: 7343: 7336: 7333: 7318: 7311: 7308: 7303: 7301:9781285415017 7297: 7293: 7292: 7284: 7281: 7276: 7274:9781430232384 7270: 7266: 7265: 7257: 7254: 7249: 7243: 7239: 7235: 7230: 7229: 7220: 7217: 7212: 7210:9783540448334 7206: 7199: 7198: 7193: 7186: 7184: 7180: 7177: 7173: 7168: 7165: 7154: 7150: 7144: 7141: 7136: 7130: 7126: 7122: 7121:Prentice-Hall 7118: 7117: 7112: 7106: 7103: 7098: 7092: 7088: 7084: 7083: 7075: 7072: 7067: 7063: 7056: 7049: 7046: 7041: 7039:0-201-55802-5 7035: 7031: 7027: 7020: 7017: 7010: 7006: 7003: 7001: 6998: 6996: 6993: 6991: 6988: 6986: 6983: 6981: 6978: 6975: 6972: 6970: 6967: 6965: 6962: 6960: 6957: 6955: 6952: 6950: 6947: 6946: 6942: 6940: 6938: 6934: 6931:is a form of 6930: 6926: 6922: 6902: 6893: 6890: 6887: 6881: 6878: 6875: 6872: 6863: 6860: 6857: 6851: 6848: 6845: 6842: 6839: 6833: 6830: 6827: 6821: 6818: 6815: 6809: 6806: 6803: 6800: 6797: 6787: 6786: 6785: 6783: 6779: 6775: 6771: 6767: 6763: 6759: 6755: 6751: 6747: 6743: 6742:declaratively 6738: 6736: 6732: 6728: 6724: 6720: 6716: 6712: 6708: 6704: 6700: 6696: 6692: 6688: 6583: 6581: 6557: 6549: 6547: 6543: 6539: 6505: 6499: 6490: 6484: 6478: 6464: 6444: 6438: 6435: 6432: 6429: 6423: 6419: 6415: 6409: 6406: 6403: 6383: 6380: 6377: 6352: 6349: 6346: 6343: 6338: 6334: 6329: 6319: 6313: 6307: 6299: 6282: 6279: 6276: 6271: 6268: 6263: 6259: 6254: 6244: 6238: 6232: 6207: 6204: 6199: 6195: 6190: 6180: 6174: 6168: 6160: 6141: 6138: 6133: 6129: 6124: 6114: 6108: 6102: 6082: 6079: 6076: 6051: 6048: 6045: 6042: 6037: 6033: 6028: 6021: 6018: 6012: 6006: 5998: 5997: 5996: 5993: 5977: 5971: 5968: 5962: 5958: 5954: 5948: 5945: 5942: 5939: 5933: 5927: 5917: 5909: 5907: 5905: 5901: 5897: 5889: 5887: 5884: 5881: 5879: 5432: 5430: 5426: 5422: 5418: 5410: 5408: 5406: 5402: 5264: 5262: 5261:tree_contains 5230:tree_contains 5203:tree_contains 5098:tree_contains 5088: 5021: 5016: 5008: 4897: 4895: 4890: 4886: 4835: 4833: 4829: 4823: 4815: 4812: 4807: 4803: 4799: 4797: 4793: 4787: 4779: 4738:binary_search 4696:binary_search 4513:binary_search 4441:binary_search 4359: 4356: 4352: 4349: 4345: 4344:binary search 4338:Binary search 4337: 4326:In general: h 4293: 4292: 4288: 4287: 4284: 4275: 4270: 4264: 4260: 4255: 4251: 4247: 4243: 4238: 4234: 4233: 4230:(recursive): 4229: 4226: 4225: 4222: 4219: 4208: 4207: 4203: 4202: 4185: 4182: 4177: 4173: 4165: 4151: 4148: 4143: 4140: 4137: 4133: 4129: 4126: 4121: 4117: 4109: 4108: 4107: 4105: 4080: 4077: 4074: 4062: 4059: 4053: 4050: 4047: 4041: 4038: 4035: 4032: 4025: 4022: 4019: 4007: 4001: 3996: 3990: 3984: 3981: 3974: 3973: 3972: 3970: 3966: 3964: 3957: 3948: 3941: 3939: 3929: 3925: 3922: 3916: 3912: 3908: 3904: 3900: 3897: 3893: 3889: 3885: 3880: 3876: 3870: 3866: 3862: 3858: 3854: 3850: 3845: 3841: 3840: 3836: 3835: 3832: 3830: 3826: 3822: 3809: 3808: 3804: 3803: 3797: 3796: 3792: 3791: 3774: 3771: 3765: 3762: 3759: 3746: 3732: 3729: 3726: 3703: 3697: 3694: 3691: 3682: 3676: 3673: 3670: 3657: 3656: 3655: 3641: 3637: 3633: 3625: 3609: 3603: 3595: 3585: 3581: 3577: 3574: 3570: 3564: 3560: 3556: 3552: 3548: 3544: 3540: 3539: 3536:(recursive): 3535: 3532: 3531: 3507: 3504: 3501: 3483: 3480: 3477: 3471: 3468: 3465: 3462: 3449: 3446: 3443: 3431: 3425: 3420: 3414: 3411: 3408: 3395: 3394: 3393: 3391: 3387: 3385: 3381: 3373: 3371: 3369: 3365: 3335: 3332: 3329: 3314: 3311: 3308: 3305: 3302: 3299: 3293: 3259: 3256: 3253: 3241: 3235: 3230: 3228: 3220: 3217: 3214: 3208: 3171: 3168: 3165: 3159: 3129: 3127: 3119: 3113: 3110: 3099: 3098: 3097: 3082: 3078: 3077:running_total 3075: 3069: 3065: 3062: 3058: 3054: 3053:running_total 3050: 3049:running_total 3047: 3043: 3039: 3035: 3029: 3028:running_total 3025: 3019: 3014: 3010: 3006: 3002:factorial is: 3001: 2997: 2996: 2992: 2991: 2988: 2958: 2957: 2953: 2952: 2949: 2932: 2929: 2924: 2920: 2912: 2896: 2893: 2890: 2886: 2882: 2879: 2874: 2870: 2862: 2861: 2860: 2858: 2847: 2843: 2839: 2835: 2829: 2824: 2820: 2816: 2812:factorial is: 2811: 2807: 2806: 2803:(recursive): 2802: 2799: 2798: 2774: 2771: 2768: 2753: 2750: 2747: 2741: 2738: 2735: 2732: 2725: 2722: 2719: 2707: 2701: 2696: 2690: 2684: 2681: 2674: 2673: 2672: 2670: 2666: 2658: 2653: 2651: 2649: 2645: 2640: 2636: 2633: 2631: 2535: 2533: 2531: 2435: 2433: 2427: 2425: 2423: 2326: 2227: 2226: 2222: 2219: 2216: 2215: 2212: 2209: 2205: 2201: 2197: 2193: 2185: 2183: 2182:performance. 2181: 2177: 2173: 2169: 2165: 2161: 2157: 2153: 2145: 2143: 2141: 2137: 2133: 2129: 2125: 2121: 2113: 2111: 2109: 2105: 2101: 2098: 2093: 2089: 2082:Vulnerability 2081: 2079: 2077: 2073: 2069: 2065: 2061: 2053: 2051: 2048: 2044: 2039: 2037: 2033: 2029: 2025: 2017: 2015: 2013: 2009: 2005: 2001: 1997: 1993: 1989: 1985: 1981: 1977: 1972: 1970: 1966: 1962: 1958: 1954: 1950: 1942: 1837: 1835: 1831: 1826: 1812: 1803: 1802: 1799: 1780: 1778: 1774: 1770: 1766: 1762: 1754: 1752: 1750: 1746: 1742: 1738: 1729: 1727: 1725: 1720: 1514:// empty tree 1454:tree_contains 1444: 1414:tree_contains 1387:tree_contains 1282:tree_contains 1275: 1272: 1270: 1266: 1261: 1258: 1250: 1247: 1246: 1245: 1239: 1236: 1235: 1234: 1231: 1229: 1225: 1217: 1215: 1211: 1207: 1199: 1195: 1189: 1187: 1182: 1178: 924: 920: 917: 916: 907: 902: 900: 898: 894: 890: 884: 882: 874: 872: 865: 862: 859: 858: 857: 850: 844: 841: 840:loop variants 837: 833: 829: 826: 822: 818: 817: 816: 814: 805: 798: 796: 792: 788: 784: 780: 779:binary search 776: 772: 768: 766: 762: 755: 753: 745: 737: 736: 728: 723: 719: 711: 709: 707: 703: 697: 689: 687: 685: 681: 677: 673: 669: 665: 661: 657: 653: 649: 645: 640: 638: 634: 630: 626: 622: 618: 614: 610: 608: 601: 593: 591: 589: 585: 579: 575: 573: 569: 561: 549: 544: 542: 540: 536: 535:prime numbers 531: 526: 516: 508: 506: 501: 496: 492: 484: 482: 408: 406: 402: 398: 394: 386: 384: 381:(or positive 380: 376: 371: 364:ListOfStrings 346:ListOfStrings 339: 337: 333: 327: 319: 316: 311: 310:definitions. 309: 305: 301: 297: 293: 285: 283: 281: 277: 273: 269: 263: 262: 256: 251: 249: 248:infinite loop 245: 239: 235: 231: 227: 220: 216:and, for all 211: 207: 203: 199: 191: 189: 187: 183: 179: 175: 171: 163: 161: 159: 155: 151: 146: 136: 132: 128: 124: 120: 116: 107: 103: 102:Niklaus Wirth 97: 92: 90: 86: 82: 78: 74: 66: 61: 54: 49: 45: 41: 37: 33: 19: 8932:Root-finding 8926: 8857:Backtracking 8821:Segment tree 8791:Fenwick tree 8691:Event-driven 8095:Higher-order 8079: 8023:Object-based 7861: 7857: 7830: 7812: 7787: 7762: 7742: 7718: 7693: 7669: 7621: 7608: 7596: 7584: 7572: 7560: 7545: 7534: 7524: 7505: 7490: 7475: 7467:ThoughtWorks 7456: 7442: 7429: 7420: 7409: 7399: 7388: 7378: 7367:. Retrieved 7357: 7346:. Retrieved 7335: 7324:. Retrieved 7310: 7290: 7283: 7263: 7256: 7227: 7219: 7196: 7167: 7156:. Retrieved 7152: 7143: 7115: 7105: 7081: 7074: 7065: 7061: 7048: 7029: 7019: 6976:(in general) 6917: 6781: 6777: 6773: 6769: 6765: 6761: 6757: 6753: 6749: 6739: 6734: 6730: 6726: 6722: 6714: 6710: 6706: 6702: 6698: 6694: 6690: 6686: 6684: 6553: 6541: 6537: 6526: 6462: 5994: 5919: 5893: 5885: 5882: 5875: 5439:java.io.File 5414: 5398: 5319:// base case 5260: 5258: 5158:// base case 5086: 5018: 5009:Binary trees 4946:// base case 4893: 4888: 4884: 4883:Because the 4882: 4831: 4827: 4825: 4816:Linked lists 4809: 4805: 4801: 4789: 4357: 4353: 4348:sorted array 4341: 4282: 4273: 4268: 4262: 4258: 4253: 4249: 4248:, such that 4245: 4241: 4236: 4220: 4217: 4103: 4102: 3968: 3967: 3962: 3959: 3936: 3927: 3923: 3920: 3914: 3910: 3906: 3902: 3898: 3895: 3891: 3887: 3883: 3878: 3874: 3868: 3864: 3860: 3856: 3852: 3848: 3843: 3828: 3824: 3818: 3592: 3583: 3579: 3575: 3572: 3568: 3562: 3558: 3554: 3550: 3546: 3542: 3389: 3388: 3377: 3361: 3089: 3080: 3076: 3073: 3067: 3063: 3060: 3056: 3052: 3048: 3045: 3041: 3037: 3033: 3027: 3023: 3017: 3012: 3008: 3004: 2999: 2986: 2968:= 4 × (3 × b 2947: 2854: 2845: 2841: 2837: 2833: 2827: 2822: 2818: 2814: 2809: 2662: 2643: 2641: 2637: 2634: 2627: 2527: 2431: 2419: 2195: 2189: 2156:stack memory 2154:in place of 2149: 2117: 2088:pathological 2085: 2057: 2040: 2021: 1973: 1946: 1827: 1824: 1786:defined by x 1781: 1758: 1733: 1724:control flow 1716: 1442: 1342:// base case 1273: 1268: 1262: 1256: 1254: 1243: 1232: 1228:binary trees 1221: 1212: 1205: 1197: 1193: 1190: 1180: 1176: 1174: 906: 885: 878: 869: 854: 838:In terms of 810: 803: 764: 760: 757: 747: 746: 742: 733: 725: 721: 699: 683: 679: 675: 671: 667: 663: 659: 655: 651: 647: 641: 636: 632: 631:which calls 628: 624: 620: 616: 612: 606: 605: 603: 580: 576: 563: 555: 553: 527: 512: 502: 498: 475: 390: 372: 368: 332:linked lists 329: 289: 279: 275: 259: 252: 240: 233: 229: 225: 218: 205: 197: 195: 178:lookup table 167: 147: 112: 105: 96:repetitions. 94: 76: 70: 44: 9016:Subroutines 8811:Linked list 8701:Intentional 8681:Data-driven 8663:of concerns 8622:Inferential 8609:Multi-stage 8589:Interactive 8466:Actor-based 8453:distributed 8396:Stack-based 8196:Synchronous 8153:Value-level 8140:Applicative 8057:Declarative 8015:Class-based 7682:356-02201-3 7512:"wildmat.c" 6933:abstraction 5826:isDirectory 5631:isDirectory 5388:// go right 5015:Binary tree 4896:procedure. 4885:struct node 4832:struct node 4828:struct node 4822:Linked list 4263:then return 3561:> 0 and 2204:interpreter 2152:heap memory 2106:from being 2054:Stack space 1980:while loops 1103:fac2wrapper 889:memoization 495:Corecursion 491:Coinduction 397:expressions 393:definitions 308:coinductive 272:corecursion 186:memoization 8990:Categories 8947:Sweep line 8922:Randomized 8850:Algorithms 8801:Hash table 8762:algorithms 8676:Components 8661:Separation 8636:Reflective 8630:by example 8574:Extensible 8448:Concurrent 8424:Production 8411:Templating 8391:Simulation 8376:Scientific 8296:Spacecraft 8224:Constraint 8219:Answer set 8171:Flow-based 8071:comparison 8066:Functional 8038:Persistent 8002:comparison 7967:Procedural 7939:Structured 7930:Imperative 7708:0262062186 7654:References 7625:§9.3, §9.4 7601:Wirth 1976 7369:2012-09-03 7348:2012-09-03 7326:2012-09-03 7236:. p. 7158:2020-10-21 7123:. p. 7068:: 169–175. 5832:&& 5637:&& 5451:FileSystem 5419:may vary, 5417:filesystem 5370:tree_print 5340:// go left 5322:tree_print 5274:tree_print 4979:list_print 4904:list_print 4894:list_print 4889:list_print 4244:: integer 4228:Pseudocode 3859:such that 3855:, integer 3851:: integer 3557:such that 3553:, integer 3549:: integer 3534:Pseudocode 3083:factorial 3011:such that 3007:: integer 2848:factorial 2821:such that 2817:: integer 2801:Pseudocode 2648:call stack 2536:Function 2 2436:Function 1 2422:call stack 2192:tail calls 2162:, such as 2108:terminated 2060:call stack 2008:tail calls 1961:call stack 1765:call stack 1737:merge sort 1685:&& 1643:&& 1625:// recurse 1267:of height 727:FUNCTIONS. 716:See also: 517:functions 401:statements 375:definition 300:programmer 198:base cases 150:call stack 9001:Recursion 8942:Streaming 8927:Recursion 8563:Inductive 8559:Automatic 8381:Scripting 8080:Recursive 7878:127891023 7836:MIT Press 7724:CRC Press 7699:MIT Press 6974:Recursion 6923:), as in 6870:→ 6840:∧ 6795:∀ 6719:backwards 6582:clauses: 6494:Θ 6436:⋅ 6430:≤ 6407:⋅ 6396:, and if 6378:ε 6353:ε 6344:⁡ 6323:Ω 6280:⁡ 6269:⁡ 6248:Θ 6205:⁡ 6184:Θ 6139:⁡ 6118:Θ 6077:ε 6052:ε 6049:− 6043:⁡ 5946:⋅ 5878:iteration 5850:rtraverse 5733:listFiles 5700:rtraverse 5655:rtraverse 5538:listRoots 5421:recursion 5376:tree_node 5355:tree_node 5328:tree_node 5304:tree_node 5289:tree_node 5236:tree_node 5209:tree_node 5170:tree_node 5137:tree_node 5113:tree_node 4239:hanoi is: 4141:− 4051:− 4042:⁡ 4036:⋅ 3985:⁡ 3911:remainder 3899:remainder 3890:is zero, 3879:remainder 3730:≠ 3701:% 3624:remainder 3607:% 3472:⁡ 3469:remainder 3303:− 3294:⁡ 3209:⁡ 3160:⁡ 3114:⁡ 3061:decrement 2894:− 2751:− 2742:⁡ 2736:⋅ 2685:⁡ 2665:factorial 2659:Factorial 2180:profiling 2164:Rich Salz 2132:Quicksort 2092:malicious 2036:tail call 1984:for loops 1957:instances 1847:factorial 1830:factorial 1761:iteration 1694:tree_node 1676:tree_node 1652:tree_node 1634:tree_node 1592:tree_node 1568:tree_node 1529:tree_node 1493:tree_node 1469:tree_node 1420:tree_node 1393:tree_node 1354:tree_node 1321:tree_node 1297:tree_node 1210:savings. 846:analysis. 783:mergesort 775:quicksort 654:and then 609:recursion 352:EmptyList 338:syntax): 278:th term ( 268:parameter 210:factorial 202:trivially 192:Base case 168:A common 158:tail call 154:efficient 89:functions 87:by using 77:recursion 40:Recursion 8716:Subjects 8706:Literate 8696:Features 8651:Template 8646:Symbolic 8618:Bayesian 8598:Hygienic 8458:parallel 8337:Modeling 8332:Low-code 8307:End-user 8244:Ontology 8176:Reactive 8163:Dataflow 7643:20190474 7620:(2021). 7589:Epp 1995 7577:Epp 1995 7113:(1976). 6943:See also 6921:forwards 5514:traverse 5484:traverse 4237:function 4070:if 4015:if 3871:>= 0 3844:function 3565:>= 0 3545:gcd is: 3543:function 3497:if 3439:if 3366:such as 3325:if 3249:if 3000:function 2810:function 2764:if 2715:if 2605:"%d 2469:"%d 2200:compiler 2130:such as 2043:compiler 1868:unsigned 1853:unsigned 1841:unsigned 1794:) from x 1790:= f(n, x 1619:// found 800:— 791:fractals 730:— 613:Indirect 515:accessor 383:integers 99:— 8937:Sorting 8912:Minimax 8671:Aspects 8579:Generic 8569:Dynamic 8428:Pattern 8406:Tactile 8371:Quantum 8361:filters 8292:Command 8191:Streams 8186:Signals 7957:Modular 7668:(ed.). 7436:. 2018. 6925:Datalog 6471:, then 6225:, then 6095:, then 5841:canRead 5802:println 5691:private 5646:canRead 5607:println 5505:private 4498:OUTPUT: 4381:OUTPUT: 4261:n is 1 3846:gcd is: 3015:>= 0 2964:= 4 × b 2825:>= 0 2168:wildmat 2104:process 1931:product 1904:product 1874:product 1749:Timsort 670:alone, 505:streams 377:is the 336:Haskell 123:Clojure 8917:Online 8902:Greedy 8831:String 8434:Visual 8401:System 8286:Action 8110:Strict 7876: 7842: 7799: 7774: 7749: 7730: 7705: 7679: 7641: 7631: 7516:GitHub 7298: 7271: 7244: 7207: 7131: 7093: 7036: 6580:Prolog 6527:where 6465:< 1 5790:System 5772:length 5694:static 5595:System 5577:length 5508:static 5472:String 5460:static 5457:public 5445:public 5436:import 5343:printf 5280:struct 5200:return 5188:return 5149:return 5104:struct 5064:struct 5046:struct 5025:struct 4952:printf 4910:struct 4860:struct 4839:struct 4750:toFind 4735:return 4708:toFind 4693:return 4684:toFind 4660:return 4651:toFind 4627:return 4534:toFind 4483:INPUT: 4453:toFind 4438:return 4414:toFind 4393:search 4369:INPUT: 4276:hanoi 4269:return 4252:>= 3921:return 3915:repeat 3875:create 3863:>= 3580:return 3573:return 3571:is 0, 3567:1. if 3368:Scheme 3074:return 3068:repeat 3040:is 0, 3024:create 3018:output 2842:return 2838:return 2836:is 0, 2832:1. if 2828:output 2611:" 2599:printf 2475:" 2463:printf 2384:return 2372:return 2294:return 2282:return 2122:as in 2072:Python 2004:Python 2002:, and 1928:return 1628:return 1610:return 1559:struct 1520:return 1505:return 1460:struct 1384:return 1372:return 1333:return 1288:struct 1257:before 1181:before 1151:return 1139:return 1070:return 1058:return 980:return 968:return 871:this. 806:, 2002 793:, and 738:, 2001 658:calls 650:calls 627:calls 619:calls 607:direct 427:number 361:String 255:series 221:> 0 214:0! = 1 108:, 1976 8826:Stack 8816:Queue 8796:Graph 8776:Array 8711:Roles 8594:Macro 8357:Pipes 8277:Array 8254:Query 8206:Logic 8115:GADTs 8105:Total 8028:Agent 7874:S2CID 7768:Wiley 7320:(PDF) 7234:Wiley 7201:(PDF) 7058:(PDF) 7011:Notes 5448:class 5382:right 5379:-> 5358:-> 5331:-> 5242:right 5239:-> 5212:-> 5173:-> 5073:right 4988:-> 4967:-> 4796:trees 4792:lists 4714:start 4612:start 4588:start 4573:start 4543:start 4465:count 4423:count 4271:+ 1] 4242:input 4039:hanoi 3982:hanoi 3917:loop 3909:y to 3884:begin 3849:input 3547:input 3070:loop 3034:begin 3005:input 2815:input 2667:of a 2644:order 2208:jumps 2176:tests 2140:stack 2100:logic 1969:stack 1947:Most 1889:while 1700:right 1697:-> 1682:right 1679:-> 1655:-> 1637:-> 1595:-> 1508:false 1426:right 1423:-> 1396:-> 1357:-> 1336:false 1130:<= 959:<= 290:Many 236:− 1)! 139:while 8897:Fold 8841:Trie 8836:Tree 8806:Heap 8760:and 8359:and 8006:list 7840:ISBN 7797:ISBN 7772:ISBN 7747:ISBN 7728:ISBN 7703:ISBN 7639:LCCN 7629:ISBN 7296:ISBN 7269:ISBN 7242:ISBN 7205:ISBN 7129:ISBN 7091:ISBN 7034:ISBN 6756:and 6689:to 6665:path 6626:path 6587:path 6381:> 6080:> 5894:The 5763:< 5718:File 5706:File 5697:void 5568:< 5532:File 5523:File 5511:void 5475:args 5466:main 5463:void 5361:data 5334:left 5310:NULL 5283:node 5271:void 5215:left 5197:else 5176:data 5161:else 5143:NULL 5107:node 5067:node 5055:left 5049:node 5037:data 5028:node 4991:next 4985:list 4970:data 4964:list 4940:NULL 4934:list 4919:list 4913:node 4901:void 4869:next 4863:node 4851:data 4842:node 4794:and 4744:data 4729:else 4702:data 4681:> 4678:data 4669:else 4645:data 4636:else 4615:> 4525:data 4447:data 4405:data 4342:The 4078:> 3930:gcd 3892:exit 3867:and 3827:and 3586:gcd 3505:> 3378:The 3333:> 3111:fact 3051:to ( 3042:exit 2772:> 2739:fact 2682:fact 2572:< 2542:void 2496:< 2442:void 2393:fact 2381:else 2336:fact 2291:else 2178:and 2064:heap 2028:Java 2026:and 2000:Java 1982:and 1816:base 1807:base 1796:base 1658:left 1640:left 1622:else 1613:true 1598:data 1562:node 1550:bool 1517:else 1499:NULL 1463:node 1451:bool 1399:left 1381:else 1375:true 1360:data 1345:else 1327:NULL 1291:node 1279:bool 1154:fac2 1148:else 1073:fac2 1067:else 1019:fac2 983:fac1 977:else 932:fac1 761:HtDP 682:and 539:here 530:lazy 523:tail 521:and 519:head 493:and 470:> 467:expr 464:< 460:> 457:expr 454:< 450:> 447:expr 444:< 440:> 437:expr 434:< 430:> 424:< 418:> 415:expr 412:< 399:and 358:Cons 343:data 296:data 257:for 228:! = 141:and 8264:DSL 7866:doi 7677:SBN 7238:115 7125:126 7087:427 6939:). 6780:to 6772:to 6764:to 6725:to 6713:to 6705:to 6697:to 6647:arc 6608:arc 6335:log 6300:If 6277:log 6260:log 6196:log 6161:If 6130:log 6034:log 5999:If 5902:of 5856:fss 5844:()) 5835:fss 5820:fss 5808:fss 5796:out 5766:fss 5745:int 5739:for 5736:(); 5721:fss 5676:/** 5649:()) 5601:out 5550:int 5544:for 5541:(); 5493:/** 5487:(); 5119:int 5095:int 5034:int 4848:int 4768:end 4756:mid 4720:mid 4663:mid 4618:end 4582:end 4567:mid 4564:int 4552:end 4549:int 4540:int 4531:int 4519:int 4510:int 4420:int 4411:int 4399:int 4390:int 4274:end 4267:2. 4257:1. 3928:end 3919:3. 3913:5. 3907:set 3903:set 3896:set 3882:2. 3873:1. 3754:gcd 3719:if 3686:gcd 3665:gcd 3626:of 3584:end 3457:gcd 3403:gcd 3081:end 3072:3. 3066:4. 3046:set 3032:2. 3022:1. 3020:: 2846:end 2830:: 2617:num 2587:num 2569:num 2554:num 2551:int 2511:num 2493:num 2481:num 2454:num 2451:int 2342:int 2333:int 2297:gcd 2252:int 2243:int 2237:gcd 2234:int 2202:or 2196:not 2090:or 1871:int 1856:int 1844:int 1792:n-1 1709:)); 1574:int 1475:int 1303:int 1208:(1) 1109:int 1100:int 1025:int 1016:int 938:int 929:int 771:gcd 541:). 432:| ( 421:::= 385:): 184:or 143:for 71:In 8992:: 8628:, 8624:, 8620:, 8426:, 8422:, 8151:, 8142:, 8021:, 8017:, 8004:, 7872:. 7860:. 7838:. 7824:; 7795:. 7791:. 7770:. 7766:. 7726:. 7722:. 7701:. 7697:. 7637:. 7616:; 7533:. 7514:. 7465:. 7432:. 7428:. 7408:. 7387:. 7240:. 7182:^ 7174:, 7151:. 7127:. 7119:. 7089:. 7066:19 7064:. 7060:. 7028:. 6752:, 6737:. 6680:). 6662:), 6644::- 6623:). 6605::- 6564::- 5859:); 5829:() 5814:if 5811:); 5781:++ 5727:fd 5709:fd 5688:*/ 5664:); 5661:fs 5640:fs 5634:() 5625:fs 5619:if 5616:); 5613:fs 5586:++ 5571:fs 5526:fs 5517:() 5502:*/ 5385:); 5364:); 5337:); 5307:!= 5298:if 5251:); 5227:|| 5179:== 5164:if 5140:== 5131:if 5082:}; 4994:); 4973:); 4937:!= 4928:if 4878:}; 4771:); 4726:); 4723:-1 4672:if 4648:== 4639:if 4630:-1 4606:if 4507:*/ 4477:/* 4471:); 4468:-1 4387:*/ 4363:/* 4265:1 4259:if 4106:: 3971:: 3654:: 3392:: 3096:: 3055:× 2859:: 2671:: 2650:. 2620:); 2608:\n 2596:); 2563:if 2520:); 2487:if 2484:); 2472:\n 2408:); 2363:== 2354:if 2318:); 2273:== 2264:if 2220:: 2166:' 2110:. 2078:. 2070:; 1998:, 1916:-- 1907:*= 1798:: 1670:|| 1667:)) 1601:== 1586:if 1538:); 1496:== 1487:if 1435:); 1411:|| 1363:== 1348:if 1324:== 1315:if 1269:h, 1163:); 1121:if 1082:-1 1049:== 1040:if 992:-1 950:if 899:. 879:A 789:, 785:, 781:, 777:, 773:, 708:. 660:f, 637:f. 633:f, 621:f, 472:) 462:+ 442:* 250:. 223:, 188:. 145:. 104:, 75:, 8750:e 8743:t 8736:v 8632:) 8616:( 8600:) 8596:( 8565:) 8561:( 8487:) 8483:( 8455:, 8450:, 8430:) 8418:( 8298:) 8294:( 8288:) 8284:( 8230:) 8226:( 8182:) 8178:( 8091:) 8087:( 8073:) 8069:( 8008:) 8000:( 7923:) 7919:( 7909:e 7902:t 7895:v 7880:. 7868:: 7862:2 7848:. 7816:. 7805:. 7780:. 7755:. 7736:. 7711:. 7685:. 7645:. 7539:. 7518:. 7499:. 7469:. 7414:. 7393:. 7372:. 7351:. 7329:. 7305:. 7278:. 7250:. 7213:. 7161:. 7137:. 7099:. 7042:. 6903:. 6900:) 6897:) 6894:Y 6891:, 6888:X 6885:( 6882:h 6879:t 6876:a 6873:p 6867:) 6864:Y 6861:, 6858:Z 6855:( 6852:h 6849:t 6846:a 6843:p 6837:) 6834:Z 6831:, 6828:X 6825:( 6822:c 6819:r 6816:a 6813:( 6810:Z 6807:, 6804:Y 6801:, 6798:X 6782:Y 6778:X 6774:Y 6770:Z 6766:Z 6762:X 6758:Z 6754:Y 6750:X 6735:Y 6731:X 6727:Y 6723:Z 6715:Y 6711:Z 6707:Z 6703:X 6699:Y 6695:X 6691:Y 6687:X 6677:Y 6674:, 6671:Z 6668:( 6659:Z 6656:, 6653:X 6650:( 6641:) 6638:Y 6635:, 6632:X 6629:( 6620:Y 6617:, 6614:X 6611:( 6602:) 6599:Y 6596:, 6593:X 6590:( 6576:B 6572:A 6567:B 6561:A 6544:) 6542:n 6540:( 6538:f 6533:b 6529:a 6512:) 6509:) 6506:n 6503:( 6500:f 6497:( 6491:= 6488:) 6485:n 6482:( 6479:T 6469:n 6463:c 6448:) 6445:n 6442:( 6439:f 6433:c 6427:) 6424:b 6420:/ 6416:n 6413:( 6410:f 6404:a 6384:0 6358:) 6350:+ 6347:a 6339:b 6330:n 6326:( 6320:= 6317:) 6314:n 6311:( 6308:f 6286:) 6283:n 6272:a 6264:b 6255:n 6251:( 6245:= 6242:) 6239:n 6236:( 6233:T 6213:) 6208:a 6200:b 6191:n 6187:( 6181:= 6178:) 6175:n 6172:( 6169:f 6147:) 6142:a 6134:b 6125:n 6121:( 6115:= 6112:) 6109:n 6106:( 6103:T 6083:0 6057:) 6046:a 6038:b 6029:n 6025:( 6022:O 6019:= 6016:) 6013:n 6010:( 6007:f 5981:) 5978:n 5975:( 5972:f 5969:+ 5966:) 5963:b 5959:/ 5955:n 5952:( 5949:T 5943:a 5940:= 5937:) 5934:n 5931:( 5928:T 5871:} 5868:} 5865:} 5862:} 5853:( 5847:{ 5838:. 5823:. 5817:( 5805:( 5799:. 5793:. 5787:{ 5784:) 5778:i 5775:; 5769:. 5760:i 5757:; 5754:0 5751:= 5748:i 5742:( 5730:. 5724:= 5715:{ 5712:) 5703:( 5682:* 5673:} 5670:} 5667:} 5658:( 5652:{ 5643:. 5628:. 5622:( 5610:( 5604:. 5598:. 5592:{ 5589:) 5583:i 5580:; 5574:. 5565:i 5562:; 5559:0 5556:= 5553:i 5547:( 5535:. 5529:= 5520:{ 5490:} 5481:{ 5478:) 5469:( 5454:{ 5442:; 5394:} 5391:} 5373:( 5352:, 5346:( 5325:( 5316:{ 5313:) 5301:( 5295:{ 5292:) 5286:* 5277:( 5254:} 5248:i 5245:, 5233:( 5224:) 5221:i 5218:, 5206:( 5194:; 5191:1 5185:) 5182:i 5167:( 5155:; 5152:0 5146:) 5134:( 5128:{ 5125:) 5122:i 5116:, 5110:* 5101:( 5076:; 5070:* 5058:; 5052:* 5040:; 5031:{ 5003:} 5000:} 4982:( 4961:, 4955:( 4949:{ 4943:) 4931:( 4925:{ 4922:) 4916:* 4907:( 4872:; 4866:* 4854:; 4845:{ 4774:} 4765:, 4762:1 4759:+ 4753:, 4747:, 4741:( 4717:, 4711:, 4705:, 4699:( 4687:) 4675:( 4666:; 4654:) 4642:( 4633:; 4621:) 4609:( 4600:; 4597:2 4594:/ 4591:) 4585:- 4579:( 4576:+ 4570:= 4558:{ 4555:) 4546:, 4537:, 4528:, 4522:* 4516:( 4474:} 4462:, 4459:0 4456:, 4450:, 4444:( 4429:{ 4426:) 4417:, 4408:, 4402:* 4396:( 4328:n 4321:7 4317:6 4313:5 4309:4 4305:3 4301:2 4297:1 4295:h 4254:1 4250:n 4246:n 4186:1 4183:= 4178:1 4174:h 4152:1 4149:+ 4144:1 4138:n 4134:h 4130:2 4127:= 4122:n 4118:h 4081:1 4075:n 4063:1 4060:+ 4057:) 4054:1 4048:n 4045:( 4033:2 4026:1 4023:= 4020:n 4008:1 4002:{ 3997:= 3994:) 3991:n 3988:( 3963:n 3924:x 3888:y 3869:y 3865:y 3861:x 3857:y 3853:x 3829:y 3825:x 3775:x 3772:= 3769:) 3766:0 3763:, 3760:x 3757:( 3733:0 3727:y 3707:) 3704:y 3698:x 3695:, 3692:y 3689:( 3683:= 3680:) 3677:y 3674:, 3671:x 3668:( 3642:y 3638:/ 3634:x 3610:y 3604:x 3576:x 3569:y 3563:y 3559:x 3555:y 3551:x 3508:0 3502:y 3490:) 3487:) 3484:y 3481:, 3478:x 3475:( 3466:, 3463:y 3460:( 3450:0 3447:= 3444:y 3432:x 3426:{ 3421:= 3418:) 3415:y 3412:, 3409:x 3406:( 3336:0 3330:n 3318:) 3315:t 3312:n 3309:, 3306:1 3300:n 3297:( 3288:c 3285:c 3282:a 3278:t 3274:c 3271:a 3268:f 3260:0 3257:= 3254:n 3242:t 3236:{ 3231:= 3224:) 3221:t 3218:, 3215:n 3212:( 3203:c 3200:c 3197:a 3193:t 3189:c 3186:a 3183:f 3175:) 3172:1 3169:, 3166:n 3163:( 3154:c 3151:c 3148:a 3144:t 3140:c 3137:a 3134:f 3130:= 3123:) 3120:n 3117:( 3093:t 3064:n 3057:n 3038:n 3013:n 3009:n 2978:0 2974:1 2970:2 2966:3 2962:4 2960:b 2933:1 2930:= 2925:0 2921:b 2897:1 2891:n 2887:b 2883:n 2880:= 2875:n 2871:b 2834:n 2823:n 2819:n 2775:0 2769:n 2757:) 2754:1 2748:n 2745:( 2733:n 2726:0 2723:= 2720:n 2708:1 2702:{ 2697:= 2694:) 2691:n 2688:( 2623:} 2614:, 2602:( 2593:1 2590:+ 2584:( 2578:) 2575:4 2566:( 2560:{ 2557:) 2548:( 2523:} 2517:1 2514:+ 2508:( 2502:) 2499:4 2490:( 2478:, 2466:( 2460:{ 2457:) 2448:( 2411:} 2405:1 2402:- 2399:n 2396:( 2390:* 2387:n 2378:; 2375:1 2369:) 2366:0 2360:n 2357:( 2351:{ 2348:) 2345:n 2339:( 2321:} 2315:y 2312:% 2309:x 2306:, 2303:y 2300:( 2288:; 2285:x 2279:) 2276:0 2270:y 2267:( 2261:{ 2258:) 2255:y 2249:, 2246:x 2240:( 2024:C 1996:C 1937:} 1934:; 1925:} 1922:; 1919:n 1913:; 1910:n 1901:{ 1898:) 1895:n 1892:( 1883:; 1880:1 1877:= 1865:{ 1862:) 1859:n 1850:( 1834:C 1788:n 1784:n 1712:} 1706:i 1703:, 1691:( 1673:( 1664:i 1661:, 1649:( 1631:( 1616:; 1607:) 1604:i 1589:( 1583:{ 1580:) 1577:i 1571:, 1565:* 1556:( 1544:} 1535:i 1532:, 1526:( 1511:; 1502:) 1490:( 1484:{ 1481:) 1478:i 1472:, 1466:* 1457:( 1438:} 1432:i 1429:, 1417:( 1408:) 1405:i 1402:, 1390:( 1378:; 1369:) 1366:i 1351:( 1339:; 1330:) 1318:( 1312:{ 1309:) 1306:i 1300:, 1294:* 1285:( 1206:O 1200:) 1198:n 1196:( 1194:O 1186:C 1166:} 1160:n 1157:( 1145:; 1142:1 1136:) 1133:1 1127:n 1124:( 1118:{ 1115:) 1112:n 1106:( 1097:} 1094:; 1091:n 1088:* 1085:) 1079:n 1076:( 1064:; 1061:2 1055:) 1052:2 1046:n 1043:( 1034:{ 1031:) 1028:n 1022:( 1007:} 1004:; 1001:n 998:* 995:) 989:n 986:( 974:; 971:1 965:) 962:0 956:n 953:( 947:{ 944:) 941:n 935:( 797:. 767:) 763:( 684:g 680:f 676:g 672:f 668:f 664:g 656:g 652:g 648:f 629:g 625:f 617:f 355:| 349:= 280:n 276:n 261:e 234:n 232:( 230:n 226:n 219:n 42:. 20:)

Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.

Knowledge

Recursion (computer science)

Index