递归是一种解决问题的方法，其精髓在于将问题分解为规模更小的相同问题，持续分解，直到问题规模小到可以用非常简单直接的方式来解决。递归的问题分解方式非常独特，其算法方面的明显特征就是：在算法流程中调用自身。
递归为我们提供了一种对复杂问题的优雅解决方案，精妙的递归算法常会出奇简单，令人赞叹。
1.黄金分割
在古希腊有有位叫欧多克索斯先哲，他在研究怎么把一个线段一分为二最好看，这个点究竟要分在哪才给它看上去最协调好看，他给出了个确切的答案0.618，那为什么必须是0.618呢？
这其实来源于线段的自相似性。如下图其中
再比如一个长方形，长方形的长宽比满足黄金分割比，我们可以在它中间划分出一个正方形，剩下的小的长方形，仍然是一个黄金比例的长方形于是我们可以再画正方形这样无穷的操作下去就得到如下图所示的图形。这其实是一个反直觉的图形，一般的图形都是整体比局部大而满足黄金分割图形它的整体和局部拥有同样多的精细的结构和信息，我们称有这种性质叫自相似性，科学界把它称为分形。
然界中的具有这种自相似性的还有很多，海岸线、山脉、闪电、云朵、树等，让我们不得不感叹大自然的神奇。很容易发现这些自相似的图形其实是满足递归特性的，可以将图形分解为规模更小的相同图形。
给出总结：递归三要素：
(1)递归算法必须有一个基本终止条件（最小规模问题的直接解决）
(2)递归算法必须能改变状态向基本结束条件演进（减小问题规模）
(3)递归算法必须调用自身（解决减小了规模的相同问题）
接下来看看Scratch如何使用递归算法来模拟画出这些自相似的递归图形。
具体程序如下：
0 评论 最近
没有评论！