Recursion termination: Difference between revisions

Revision as of 03:18, 24 February 2009

Revision as of 10:50, 26 February 2009

Line 1:

WhenIn computing, '''Recursion termination''' is when certain conditions are met, aand 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>

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

| title = Recursion Lecture, Introduction to Computer Science pg. 3

Line 8 ⟶ 7:

==Examples==

Example:

===Fibonacci function===

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

Line 18 ⟶ 17:

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++ Example<ref>

{{cite book

Line 39:

==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"]

{{stub}}