Part 02 Recursion 递归
covering 5.3 ~ 5.4
1. Recursion 递归
1.1. Definition 定义
Recursion is a principle closely related to mathematical induction.
In a recursive definition, an object is defined in terms of itself.
We can recursively define sequences, functions and sets.
1.2. Use recursion to define things 使用递归进行定义
1.2.1. Recursively defined functions 递归定义的函数
Like The Fibonacci numbers
Well-defined 良定义
Recursively defined functions are well-defined.
Let P(n) be the statement “f is well-defined at n“.
- P(0) is true.
- Assume that P(n-1) is true. Then fis well-defined at n. Since f(n) is given in terms of some f(n-1).
1.2.2. Recursively defined sets 递归定义的集合
Sets can be defined recursively.
Basis Step: specifies an initial collection of elements.
Recursive Step: gives rules for forming new elements of the set from those elements already known to be in the set.
Sets described in this way are well-defined.
2. Structural Induction 结构归纳法
To prove results about recursively defined sets, we can use Structural Induction
- Basis Step: Show that the result holds for all elements specified in the basis step of the recursive definition to be in the set.
- Recursive Step: Show that if the statement is true for each of the elements used to construct new elements in the recursive step of the definition, the result holds for these new elements.
2.1. The validity of structural induction
The validity of structural induction follows from the principle of mathematical induction for the nonnegative integers.
p(n): the result is true for all elements of the set that are generated by n or fewer applications of the rules in the recursive step of a recursive definition.
Basis Step:Show that p(0) is true.
Recursive Step: if we assume p(k) is true, it follows that p(k+1) is true.
3. Generalized Induction 广义归纳法
Extend M.I’s discourse from the set of positive (or nonnegative) integers to other sets that have the well-ordering property
4. Summary for Inductions 归纳法总结
| Weak Mathematical Induction | Strong Mathematical Induction | Structural Induction | |
|---|---|---|---|
| Used for | Usually formulae | Usually formulae not provable via mathematical induction | Only things defined via recursion |
| Assumption | Assume P(k) | Assume P(1), P(2), …, P(k) | Assume statements is true for some “old elements” |
| What to prove | True for P(k+1) | True for P(k+1) | Statement is true for some “new” elements created with “old” elements |
| Step 1 | Base case | Base case | Basis step |
| Step 2 | Inductive step | Inductive step | Recursive step |
5. Recursive Algorithms 递归算法
An algorithm is called recursive if it solves a problem by reducing it to an instance of the same problem with smaller input.
5.1. Recursive Algorithm vs. Iterative Algorithm 递归与迭代
For every recursive algorithm, there is an equivalent iterative algorithm!
Recursive algorithms are often shorter, more elegant, and easier to understand than their iterative counterparts.
However, iterative algorithms are usually more efficient in their use of space and time.