Recursion
本文描述Recursion，其实上一篇"Recursive-definition"中的内容是更加容易理解的。
wikipedia Recursion
Recursion (adjective: recursive) occurs when a thing is defined in terms of itself or of its type.
NOTE: 其实上述定义就是的含义其实就是recursive definition。在维基百科Recursive acronym中使用 “refers to itself” 来表达这种含义。
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 loop or infinite chain of references can occur.
NOTE: 如果出现loop或者infinite chain，则程序就会出现死循环；
Formal definitions
In mathematics and computer science, a class of objects or methods exhibits recursive behavior when it can be defined by two properties:
1、A simple base case (or cases)—a terminating scenario that does not use recursion to produce an answer
2、A set of rules that reduces（这个词用得非常好） all other cases toward the base case
NOTE: “reduce”说明recursion是自顶向下的。
The Fibonacci sequence is a classic example of recursion:
$ {\text{Fib}}(0)=0{\text{ as base case 1,}} $
$ {\text{Fib}}(1)=1{\text{ as base case 2,}} $
$ {\text{For all integers }}n>1,~{\text{ Fib}}(n):={\text{Fib}}(n-1)+{\text{Fib}}(n-2). $
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: 0 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.
Recursively defined mathematical objects include functions, sets, and especially fractals.
NOTE: 软件工程师应该对recursive definition敏感。
In mathematics
Recursively defined sets
参见文章Recursive definition。
Functional recursion
递归函数
A function may be recursively defined in terms of itself. A familiar example is the Fibonacci number sequence: F(n) = F(n − 1) + F(n − 2). For such a definition to be useful, it must be reducible to non-recursively defined values: in this case F(0) = 0 and F(1) = 1.
A famous recursive function is the Ackermann function, which, unlike the Fibonacci sequence, cannot be expressed without recursion.
Finite subdivision rules
Main article: Finite subdivision rule
The recursion theorem
递归定理
In set theory, this is a theorem guaranteeing that recursively defined functions exist. Given a set X, an element a of X and a function $ f:X\rightarrow X $, the theorem states that there is a unique function $ F:\mathbb {N} \rightarrow X $ (where $ \mathbb {N} $ denotes the set of natural numbers including zero) such that
$ F(0)=a $
$ F(n+1)=f(F(n)) $
for any natural number n.
NOTE: 并没有搞懂
In computer science
参见工程文章
Recursion-in-computer-science\Recursion(computer-science)。