Recursion: Difference between revisions

Revision as of 04:53, 18 May 2011

Revision as of 20:17, 18 May 2011

Line 20:

* Fib(1) is 1 [base case]

* For all integers n > 1: Fib(n) is (Fib(n-1) + Fib(n-2)) [recursive definition]

A convenient mental model of recursion defines the recursive object (whether that object is an equation, an algorithm, an image, or a rule) in terms of "previously defined" objects of the same class. For example: How do you move a stack of 100 boxes? Answer: you move one box, remember where you put it, and then solve the smaller problem: how do you move a stack of 99 boxes? Eventually, you're left with the problem of how to move a single box, which you know how to do.

Many mathematical axioms are based upon recursive rules. For example, the formal definition of the [[natural number]]s in [[set theory]] follows: 1 is a natural number, and each natural number has a successor, which is also a natural number. By this base case and recursive rule, one can generate the set of all natural numbers