[软件工程师的数学]notes——chapter 6
[程序员的数学]notes——chapter 6
第6章 递归——自己定义自己
汉诺塔问题
递推公式（recursion relation, recurrence）
解析式：只使用n表示H(n)的式子。
在问题中找出递归结构——> 建立递归公式
阶乘的递归定义：n!=n×n(n-1)!
递归和归纳：
同：都是“将复杂问题简化”；
异：“从一般性前提退出个别性结论”——递归；“从个别性前提推出一般性结论”——归纳。
斐波那契数列
思考题：不断繁殖的动物
斐波那契数列例子：
摆砖头、创作旋律、鹦鹉螺的内壁间隔、葵花种子的排法、植物枝叶的长法、“一次走1阶或2阶，爬n层阶梯的方法”
帕斯卡三角形：每个数字都是上方与它相邻的两数之和。
帕斯卡三角形中出现组合数的原因：“相邻两数相加”和“n中选k的组合数”的计算对象相同。
递归定义组合数：
组合的数学分析法
找出问题中的递归结构的步骤：
从n层的整体问题中隐去部分问题 -> 判断剩余部分是否是n-1层的问题
递归图形：树、谢尔平斯基三角形(Sierpinski gasket, Sierpinski triangle)
分形图：含有递归结构的图形。