第6章 递归——自己定义自己
汉诺塔问题
递推公式(recursion relation, recurrence)
解析式:只使用n表示H(n)的式子。
在问题中找出递归结构——> 建立递归公式
阶乘的递归定义:n!=n×n(n-1)!
递归和归纳:
同:都是“将复杂问题简化”;
异:“从一般性前提退出个别性结论”——递归;“从个别性前提推出一般性结论”——归纳。
斐波那契数列
思考题:不断繁殖的动物
斐波那契数列例子:
摆砖头、创作旋律、鹦鹉螺的内壁间隔、葵花种子的排法、植物枝叶的长法、“一次走1阶或2阶,爬n层阶梯的方法”
帕斯卡三角形:每个数字都是上方与它相邻的两数之和。
帕斯卡三角形中出现组合数的原因:“相邻两数相加”和“n中选k的组合数”的计算对象相同。
递归定义组合数:
组合的数学分析法
找出问题中的递归结构的步骤:
从n层的整体问题中隐去部分问题 -> 判断剩余部分是否是n-1层的问题
递归图形:树、谢尔平斯基三角形(Sierpinski gasket, Sierpinski triangle)
分形图:含有递归结构的图形。
相关推荐
[12]优秀程序员之路——C++开发经验及技巧大汇总.zip上位机开发VC串口学习资料源码下载[12]优秀程序员之路——C++开发经验及技巧大汇总.zip上位机开发VC串口学习资料源码下载[12]优秀程序员之路——C++开发经验及...
程序员面试宝典——经典 易于理解 分析透彻 很经典
好的代码风格对于优秀的程序员是必须的。 免费共享 程序员之路——关于代码风格。
程序员面试宝典——自己整理 整理了很久,希望大家喜欢
Java程序员面试宝典——第7章__输入输出流
C~C++程序员实用大全——C~C++最佳编程指南.pdf(3)
程序员之路——一个老程序员对刚上大学的学弟学妹的忠告.
王牌9 优秀程序员之路——Java开发经验及技巧大汇总
王牌9_优秀程序员之路——C++开发经验及技巧大汇总
C_C++程序员面试宝典——目录,是本不可多得的面试书籍
C#与.NET程序员面试宝典——第4章__面向对象程序设计
C~C++程序员实用大全——C~C++最佳编程指南
C~C++程序员实用大全——C~C++最佳编程指南.pdf(1)
程序员之路——一个老程序员对刚上大学的学弟学妹的忠告.docx
C~C++程序员实用大全——C~C++最佳编程指南.pdf(2)
C~C++程序员实用大全——C~C++最佳编程指南.part6.rar
优秀程序员之路——Java开发经验及技巧大汇总.zip
如何像NASA顶级程序员一样编程——10条重要原则.docx
优秀程序员之路——ASP.NET开发经验及技巧大汇总
C#从入门到精通的王牌九: 优秀程序员之路——C# 开发经验及技巧大汇总