递归算法的基本思想呢是分而治之,也就是说我们说把一个问题呢划归为
还是同样的问题,那么这个同样的问题呢实际上又划成
两个或者多个子问题,所以这就是分而治之的思想 下面我们看一个例子呢,要画一棵树
这个树呢,如果我们用普通的这种比如说穷举的办法,你是很难把
一棵一棵的树枝呢全都描述出来。
那我们换一个考虑问题的办法就是分而治之 我们看到任何一棵树,这个树呢它是由树干和两个子树
而这个子树呢,又是一棵树干然后呢两个子树来构成的
所以我们这样来看呢,就画树的问题呢,就划归为呢画子树的问题
所以这样我们就能把这一棵树呢,看似复杂的一颗树呢就可以画出来
那当然我们画树的时候呢,给它一个坐标这个点 (x0,
y0) 然后呢这个树干的长度 Length,然后呢,以及这个
θ 的角度 当然两棵子树呢,它又是有个生长点,然后呢这两个子树的又有个子树、
又有个角度 所以我们写成程序呢,程序里面呢那我们
这是一个窗体了,而这个窗体呢 Paint 事件里头为了画图
那这个画图呢调用一个函数呢叫 drawTree,这个 drawTree 这个函数呢
它里面做的事情呢就是首先,这个 x0,
y0 是它的生长点,这是它的长度,θ 呢是角度 然后我们用一个 n 呢来表示这个数的级别。
那如果是 0 呢,就什么也不做,这就是我们所谓的出口
那程序里面的任务呢,主要是算出 x1 和 y1 x1,
y1 呢等于 x0 加上长度乘上 Cos θ y 呢就是乘 Sin θ。
那首先我们画一条直线,drawLine 画一条直线。
然后呢,再画两棵子树 啊,这两棵子树呢,它的级别是减 1,生长点呢是 x1,
y1 然后这个角度呢,我们乘上一个 这里呢,per1 就是
precent 1 呢,一个比例系数呢是 0.6,就是说子树呢长度要短一点儿
然后子树的角度呢,我们加一个 θ1,这个 θ1 呢在这里是
那么为 40 度和 30 度,θ2 呢是 30 度。
所以画树的 问题呢,就变成了画一棵直线,然后呢再画两个子树的问题
这个子树的级别呢,只不过是少了 1 目的呢,是为了有递归出口。
我们运行一下看看这个效果 那这就是一棵漂亮的树就画出来了
这里呢,其中有一个 drawLine 函数,这个 drawLine 函数呢就是 x0,
y0 到 x1, y1 然后我们再加一个宽度。
再用一个 graphics 对象的 DrawLine,这个 DrawLine 然后呢
为了我们达到这个宽度不同的笔呢,所以我们 new 一个 Pen,Color.Blue,用蓝颜色 然后这个宽度。
啊就是 DrawLine函数 这个程序呢,我们可以再稍微做一点变化
做什么变化呢?这就是加上一点随机因素,因为刚才那个图啊是固定的 加点随机因素。
就在这个地方,当这个长度呢,我们乘上个随机因素就是 0.5
乘上一个 rand,然后呢另外一棵树呢也是,这个角度呢也乘上一个随机因子
甚至我们还加一点,如果是这个随机数大于 0.6 啊 也就是在某种情况下,啊就是在百分之
四十的这个情况下呢,我们还可以再画第三棵子树 啊这是,其中的这个
rand 这个函数呢写在这儿 就是 rand.NextDouble。
另外一个呢 呃为了让它多次画呢,我们就写了一个 this.Click
+= 啊 += 一个函数,这个函数里面,就是 Redraw
这个函数呢 这个 Redraw 函数里面做了一件什么事情呢?就是 Invalidate,那 Invalidate
是什么意思呢?就是让它呢,这、 这个界面,就是这个窗体呢 它是无效。
所谓无效呢,意思就是要重新画 那么重新画呢,意思就是强制让这个系统、 告诉系统说 啊我要重画了。
所以它就会发生这个 Paint 事件 也就是 Paint
里面呢,我们又调用了 drawTree 这个函数 好,我们看看运行效果。
你看,画出来多漂亮啊 再看一下。
再 Click 点一下,这些树呢
千姿百态 是不是美的不得了啊?
所以你看这个树呢,就是这样生成出来的 所以我每次呢,看见那个大树啊、
看见那个小草啊 我就亲切地走过去啊,因为我是它的知音呐
我知道它就是这样生长出来的呀 我们在现实世界里面呢
你看,这样的树它也是就是这么长出来的。
这样的花,还有甚至我们吃的这个菜 啊,它都是这样生长出来的。
所以递归呢是我们程序里面呢 表达自然界里面的一种最常见的一种现象
那这种现象的本质是什么呢?它的每一部分 它跟整体的相似性。
这是中国古代哲学里面呢,最讲究的一个 原理:就是人是一个小的宇宙,那人的一部分,一个指甲盖
一个耳朵轮廓,也能看出这个人的各个部分 这个指甲盖就能看出这个人生了什么病。
所以在这个意义上来说 递归正是这种自然界本质规律的反映。
所以它也是一种常用的算法