|
#REDIRECT [[Recursion (computer science)]]
<!-- Please do not remove or change this AfD message until the discussion has been closed. -->
{{Article for deletion/dated|page=Recursion termination|timestamp=20190128113254|year=2019|month=January|day=28|substed=yes}}
<!-- Once discussion is closed, please place on talk page: {{Old AfD multi|page=Recursion termination|date=28 January 2019|result='''keep'''}} -->
<!-- End of AfD message, feel free to edit beyond this point -->
In computing, '''recursion termination''' is when certain conditions are met and a [[recursive algorithm]] stops calling itself and begins to return values. This happens only if, with every recursive call, the recursive algorithm changes its state and moves toward the base case. Cases that satisfy the definition, without being defined in terms of that definition, are called base cases. They are small enough to solve directly.<ref>
{{Citation
| title = What On Earth is Recursion?
| url=https://www.youtube.com/watch?v=Mv9NEXX1VHc
}}
</ref>
{{Rcat shell|
==Examples==
{{R to related topic}}
===Fibonacci Function===
The [[Fibonacci function]](fibonacci(n)), which takes [[integer]] n(n >= 0) as input, has three conditions
1. If n is 0, returns 0.<br>
2. If n is 1, returns 1.<br>
3. Otherwise, return [fibonacci(n-1) + fibonacci(n-2)]
This recursive function [[termination (computer science)|terminates]] if either conditions 1 or 2 are satisfied. We see that the function's recursive call reduces the value of n(by passing n-1 or n-2 in the function) ensuring that n reaches either condition 1 or 2.
If we look at an example of this in Python we can see what's going on a bit more clearly:
<pre>
def fibonacci (n):
if n == 0:
return 0
elif n == 1:
return 1
elif n > 1:
return fibonacci(n-1) + fibonacci(n-2)
</pre>
===Factorial Example===
An example in the programming language [[C++]]:<ref>
{{cite book
| title = An Introduction to the Imperative Part of C++
| url=http://www.doc.ic.ac.uk/~wjk/C++Intro/RobMillerL8.html
}}
</ref>
<pre>
int factorial(int number)
{
if (number == 0)
return 1;
else
return (number * factorial(number - 1));
}
</pre>
Here we see that in the recursive call, the number passed in the recursive step is reduced by 1. This again ensures that the number will at some point reduce to 0 which in turn terminates the recursive algorithm since we have our base case where we know that the factorial of 0 is 1 (or 0! = 1).
In the C programing language we could similarly do something like this:
<pre>
long factorial(int n)
{
if (n == 0)
return 1;
else
return(n * factorial(n-1));
}
</pre>
==References==
{{reflist}}
==External links==
* [http://www.cs.princeton.edu/courses/archive/spr05/cos126/lectures/07.pdf Princeton university: "An introduction to computer science in the context of scientific, engineering, and commercial applications"]
* [http://www.cdf.toronto.edu/~csc148h/winter/stg/lectures/w3/1/m/Recursion.pdf University of Toronto: "Introduction to Computer Science"]
* [https://www.youtube.com/watch?v=Mv9NEXX1VHc Computerphile: "What On Earth is Recursion?"]
[[Category:Recursion]]
{{compu-prog-stub}}
| 