|
#REDIRECT [[Recursion (computer science)]]
{{Rcat shell|
In computing, '''Recursion termination''' is when certain conditions are met and the [[recursive algorithm]] ceases calling itself and begins to return values.<ref>http://www.itl.nist.gov/div897/sqg/dads/HTML/recursiontrm.html</ref> This happens only if with every recursive call the recursive algorithm changes its state and moves towards the base case. Cases that satisfy the definition without being defined in terms of the definition itself are called base cases. They are small enough to solve directly.<ref>
{{R to related topic}}
{{cite book
| title = Recursion Lecture, Introduction to Computer Science pg. 3
| url=http://www.cdf.toronto.edu/~csc148h/winter/stg/lectures/w3/1/m/Recursion.pdf
}}
</ref>
==Examples==
===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 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.
===C++===
[[C++ (programming language)|C++]] Example:<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)
{
else 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.
==References==
{{reflist|2}}
==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"]
[[Category:Recursion]]
{{compu-prog-stub}}
| 