Content deleted Content added
m unpiped links using script |
m Added the word fractal in visual terms Tags: Visual edit Mobile edit Mobile web edit |
||
| (6 intermediate revisions by 6 users not shown) | |||
Line 6:
{{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.]]
[[File:Sierpinski triangle turtle.gif|thumb|Recursive drawing of a [[Sierpiński triangle|Sierpiński Triangle]] through turtle graphics
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 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 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 850 ⟶ 851:
| first1 = Stuart J. | last1 = Russell | author1-link = Stuart J. Russell
| first2 = Peter. | last2 = Norvig | author2-link = Peter Norvig
| title=[[Artificial Intelligence: A Modern Approach
| year = 2021
| edition = 4th
Line 857 ⟶ 858:
| 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==
| |||