Content deleted Content added
→Binary trees: add UML image Tag: Reverted |
m Added the word fractal in visual terms Tags: Visual edit Mobile edit Mobile web edit |
||
| (38 intermediate revisions by 24 users not shown) | |||
Line 1:
{{Short description|Use of functions that call themselves}}
{{About|recursive approaches to solving problems
|proofs by recursion|Mathematical induction
|recursion in computer science acronyms|Recursive acronym#Computer-related examples{{!}}Recursive acronym § Computer-related examples
|general use of the term|Recursion}}
{{Use dmy dates|date=March 2020|cs1-dates=y}}▼
[[File:recursiveTree.JPG|thumb|300px|Tree fractal created using the [[Logo (programming language)|Logo programming language]] and relying heavily on recursion. Each branch can be seen as a smaller version of a tree.]]▼
▲{{Use dmy dates|date=March 2020|cs1-dates=y}}
[[File:Sierpinski triangle turtle.gif|thumb|Recursive drawing of a [[Sierpiński triangle|Sierpiński Triangle]] through turtle graphics]]
▲[[File:recursiveTree.JPG|thumb|300px|Tree created using the [[Logo (programming language)|Logo programming language]] and relying heavily on recursion. Each branch can be seen as a smaller version of a tree.]]
{{Programming paradigms}}▼
In [[computer science]], '''recursion''' is a method of solving a [[computational problem]] where the solution depends on solutions to smaller instances of the same problem.<ref>{{cite book
Line 18 ⟶ 17:
| chapter-url = http://www-cs-faculty.stanford.edu/~knuth/gkp.html
| chapter=1: Recurrent Problems
|publisher = Addison-Wesley
}}</ref><ref>{{cite journal|title=Teaching Recursive Thinking using Unplugged Activities|journal=
|author-last = Epp
|author-first = Susanna
Line 26:
|edition = 2nd
|page = [https://archive.org/details/discretemathema000epps/page/427 427]
|publisher = PWS Publishing Company
}}</ref>
Line 40 ⟶ 41:
}}</ref>}}
Most computer [[programming language]]s support recursion by allowing a function to call itself from within its own code. Some [[functional programming]] languages (for instance, [[Clojure]])<ref>{{Cite web|title=Functional Programming {{!}} Clojure for the Brave and True|url=https://www.braveclojure.com/functional-programming/#Recursion_Instead_of_for_while|access-date=2020-10-21|website=www.braveclojure.com}}</ref> do not define any looping constructs but rely solely on recursion to repeatedly call code. It is proved in [[computability theory]] that these recursive-only languages are [[
Repeatedly calling a function from within itself may cause the [[call stack]] to have a size equal to the sum of the input sizes of all involved calls. It follows that, for problems that can be solved easily by iteration, recursion is generally less [[algorithmic efficiency|efficient]], and, for
{{toclimit|3}}
==Recursive functions and algorithms==
A common [[
===Base case===
Line 58 ⟶ 59:
==Recursive data types==
Many [[computer program]]s must process or generate an arbitrarily large quantity of [[data]]. Recursion is a technique for representing data whose exact size is unknown to the [[programmer]]: the programmer can specify this data with a [[
{{further|Algebraic data type}}
Line 65 ⟶ 66:
{{main|Recursive data type}}
An inductively defined recursive data definition is one that specifies how to construct instances of the data. For example, [[linked list]]s can be defined inductively (here, using [[
<syntaxhighlight lang="haskell">data ListOfStrings = EmptyList | Cons String ListOfStrings</syntaxhighlight>
Line 184 ⟶ 185:
}
</syntaxhighlight>
| VALIGN=TOP | <syntaxhighlight lang=
// assert(n >= 2);
if (n == 2)
Line 267 ⟶ 268:
</syntaxhighlight>
Note the use of [[short-circuit evaluation]] of the Boolean && (AND) operators, so that the recursive call is made only if the node is valid (non-Null). Note that while the first term in the AND is a pointer to a node, the second term is a
===Hybrid algorithm===
Line 273 ⟶ 274:
==Recursion versus iteration==
Recursion and [[iteration]] are equally expressive: recursion can be replaced by iteration with an explicit [[call stack]], while iteration can be replaced with [[
Compare the templates to compute x<sub>n</sub> defined by x<sub>n</sub> = f(n, x<sub>n-1</sub>) from x<sub>base</sub>:
Line 279 ⟶ 280:
|-
|
'''function''' recursive(n)
'''if''' n == base
'''return''' x<sub>base</sub>
'''else'''
'''return''' f(n, recursive(n - 1))
||
'''function''' iterative(n)
x = x<sub>base</sub>
'''for''' i = base + 1 to n
x = f(i, x)
'''return''' x
|}
Line 315 ⟶ 316:
In languages (such as [[C (programming language)|C]] and [[Java (programming language)|Java]]) 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 [[functional languages]], a function call (particularly a [[tail call]]) is typically a very fast operation, and the difference is usually less noticeable.
As a concrete example, the difference in performance between recursive and iterative implementations of the "factorial" example above depends highly on the [[compiler]] used. In languages where looping constructs are preferred, the iterative version may be as much as several [[
===Stack space===
Line 327 ⟶ 328:
===Refactoring recursion===
Recursive algorithms can be replaced with non-recursive counterparts.<ref>{{cite web| last=Mitrovic| first=Ivan| title=Replace Recursion with Iteration| publisher=[[ThoughtWorks]]| url=https://www.refactoring.com/catalog/replaceRecursionWithIteration.html}}</ref> One method for replacing recursive algorithms is to simulate them using [[memory management|heap memory]] in place of [[
==Tail-recursive functions==
Line 360 ⟶ 361:
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 [[call stack]]; when the recursive call returns, it will branch directly on the previously saved return position. Therefore, in languages that recognize this property of tail calls, tail recursion saves both space and time.
==Order of execution==
Line 386 ⟶ 388:
[[Image:Recursive2.svg|350px]]
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.
Line 762 ⟶ 764:
The above example illustrates an [[Tree traversal|in-order traversal]] of the binary tree. A [[Binary search tree]] is a special case of the binary tree where the data elements of each node are in order.
===Filesystem traversal===
Line 831:
where {{mvar|a}} represents the number of recursive calls at each level of recursion, {{mvar|b}} represents by what factor smaller the input is for the next level of recursion (i.e. the number of pieces you divide the problem into), and {{math|''f''(''n'')}} represents the work that the function does independently of any recursion (e.g. partitioning, recombining) at each level of recursion.
==Recursion in Logic Programming==
In the procedural interpretation of [[logic programming|logic programs]], clauses (or rules) of the form <syntaxhighlight inline lang="prolog">A :- B</syntaxhighlight> are treated as procedures, which reduce goals of the form <code>A</code> to subgoals of the form <code>B</code>.
For example, the [[Prolog]] clauses:
<syntaxhighlight lang="prolog">
path(X,Y) :- arc(X,Y).
path(X,Y) :- arc(X,Z), path(Z,Y).
</syntaxhighlight>
define a procedure, which can be used to search for a path from ''X'' to ''Y'', either by finding a direct arc from ''X'' to ''Y'', or by finding an arc from ''X'' to ''Z'', and then searching recursively for a path from ''Z'' to ''Y''. Prolog executes the procedure by reasoning top-down (or [[backward chaining|backwards]]) 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 ''Z'' to ''Y'', it backtracks and tries to find an arc from ''X'' to another node, and then searches for a path from that other node to ''Y''.
However, in the logical reading of logic programs, clauses are understood [[declarative program|declaratively]] as universally quantified conditionals. For example, the recursive clause of the path-finding procedure is understood as [[Knowledge representation and reasoning|representing the knowledge]] that, for every ''X'', ''Y'' and ''Z'', if there is an arc from ''X'' to ''Z'' and a path from ''Z'' to ''Y'' then there is a path from ''X'' to ''Y''. In symbolic form:
:<math>\forall X, Y, Z(arc(X,Z)\land path(Z,Y) \rightarrow path(X,Y)).</math>
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 [[forward chaining|forwards]]), as in [[Datalog]], to derive conclusions from conditions. This [[separation of concerns]] is a form of [[Abstraction (computer science)|abstraction]], which separates declarative knowledge from problem solving methods (see [[Algorithm#Algorithm = Logic + Control]]).<ref>{{Cite book
| first1 = Stuart J. | last1 = Russell | author1-link = Stuart J. Russell
| first2 = Peter. | last2 = Norvig | author2-link = Peter Norvig
| title=[[Artificial Intelligence: A Modern Approach|Artificial Intelligence: A Modern Approach §9.3, §9.4]]
| year = 2021
| edition = 4th
| isbn = 978-0134610993
| lccn = 20190474
| publisher = Pearson | ___location = Hoboken
}}</ref>
== Infinite recursion ==
{{See also|Infinite loop#Infinite recursion}}
A common mistake among programmers is not providing a way to exit a recursive function, often by omitting or incorrectly checking the base case, letting it run (at least theoretically) infinitely by endlessly calling itself recursively. This is called ''infinite recursion'', and the program will never terminate. In practice, this typically exhausts the available [[Stack (abstract data type)|stack]] space. In most programming environments, a program with infinite recursion will not really run forever. Eventually, something will break and the program will report an error.<ref>{{Cite web |title=4.8. Infinite Recursion |url=https://runestone.academy/ns/books/published/thinkcpp/Chapter4/InfiniteRecursion.html}}</ref>
Below is a Java code that would use infinite recursion:<syntaxhighlight lang="java" line="1">public class InfiniteRecursion {
static void recursive() { // Recursive Function with no way out
recursive();
}
public static void main(String[] args) {
recursive(); // Executes the recursive function upon runtime
}
}</syntaxhighlight>
Running this code will result in a [[stack overflow]] error.
==See also==
Line 838 ⟶ 881:
* [[Kleene–Rosser paradox]]
* [[Open recursion]]
* [[Recursion]] (in general)
* [[Sierpiński curve]]
* [[McCarthy 91 function]]
Line 844 ⟶ 887:
* [[Primitive recursive function]]s
* [[Tak (function)]]
* [[Logic programming]]
==Notes==
Line 861 ⟶ 905:
{{refend}}
▲{{Programming paradigms navbox}}
{{Algorithmic paradigms}}
{{DEFAULTSORT:Recursion (Computer Science)}}
| |||