Recursion (adjective: recursive) occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics and computer science, where a function being defined is applied within its own definition. While this apparently defines an infinite number of instances (function values), it is often done in such a way that no infinite loop or infinite chain of references ("crock recursion") can occur. Formal definitions In mathematics and computer science, a class of objects or methods exhibits recursive behavior when it can be defined by two properties: A simple base case (or cases) — a terminating scenario that does not use recursion to produce an answer A recursive step — a set of rules that reduces all successive cases toward the base case. For example, the following is a recursive definition of a person's ancestor. One's ancestor is either: One's parent (base case), or One's parent's ancestor (recursive step). The Fibonacci sequence is another classic example of recursion: as base case 1, as base case 2, For all integers , . Many mathematical axioms are based upon recursive rules. For example, the formal definition of the natural numbers by the Peano axioms can be described as: "Zero 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. Other recursively defined mathematical objects include factorials, functions (e.g., recurrence relations), sets (e.g., Cantor ternary set), and fractals. There are various more tongue-in-cheek definitions of recursion; see recursive humor. Informal definition Recursion is the process a procedure goes through when one of the steps of the procedure involves invoking the procedure itself. A procedure that goes through recursion is said to be 'recursive'. To understand recursion, one must recognize the distinction between a procedure and the running of a procedure. A procedure is a set of steps based on a set of rules, while the running of a procedure involves actually following the rules and performing the steps. Recursion is related to, but not the same as, a reference within the specification of a procedure to the execution of some other procedure. When a procedure is defined as such, this immediately creates the possibility of an endless loop;