Recursion termination: Difference between revisions

Revision as of 22:29, 4 November 2012

Revision as of 09:46, 11 February 2013

Line 1:

{{dead end|date=February 2013}}

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>

{{cite book

Line 7 ⟶ 9:

==Examples==

===Fibonacci function===

The Fibonacci function(fibonacci(n)), which takes integer n(n >= 0) as input, has three conditions

Line 14 ⟶ 17:

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++===

Line 42 ⟶ 45:

[[Category:Recursion]]

{{compu-prog-stub}}