Recursion termination: Difference between revisions

Revision as of 03:00, 1 March 2009

Revision as of 15:23, 27 June 2009

Line 6:

</ref>

==Examples==

==Examples==

===Fibonacci function===

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

Line 13 ⟶ 12:

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)]<br>

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.

Line 38 ⟶ 37:

{{reflist|2}}

==External Linkslinks==

* [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:Computer programming]]

{{compu-prog-stub}}