递归

递归

如果一个对象部分地由它自己组成或按它自己定义,则称它是递归的(Recursive)

递归

函数/过程/子程序在运行过程中直接或间接调用自身而产生的重用现象

递归——阶乘

$$N! = 1 * 2 * 3 … N$$

$$N! = 1 * 2 * 3 …(N-1) * N$$

$$N! = (N - 1)! * N$$

$$(N - 1)! = (N - 2)! * (N - 1)$$

递归算法必须包含如下两个部分

• 有其自身定义的与原始问题类似的更小规模的子问题，它使递归过程持续进行，称为==一般条件（General case）==
  • 计算n！问题的一般条件可以用递归公式表示为： $$n! = n * (n-1)!$$ 当 n>1时
• 所藐视问题的最简单的情况，他是一个能控制递归过程结束的条件，称为==基本条件（Base case）==
  • 计算n！问题的基本条件可以表示为：$$n! = 1$$ n=1时

优势

• 逻辑清楚，结构清晰，可读性好，更逼近数学公式的表示，符合人的思维习惯，能使一个蕴含递归关系且结构复杂的程序简洁精炼
• 特别是在难于找到从边界到解的全过程的情况下，如果把问题推进一步，其结果仍维持原问题的关系

劣势

• 嵌套层次深，函数调用开销大
• 重复计算

特别适用于使用递归算法的三种情况

• 数学定义递归的，如计算阶乘、最大公约数和Fibonacci数列等
• 数据结构是递归的，如队列、链表、树和图等
• 问题的解法是递归的，如Hanoi塔，骑士游历、八皇后问题等