下面呢我们来看看递归recursive。
递归呢,就是一个过程在调用这个过程自身,或者说函数里面
这个函数本身。那一般来说呢,在递归的调用过程中,
它一般呢一个过程执行呢要利用到前一步的这个结果, 就是一步一步的这个结果。下面我们看一个例子。
请看这里。fac呢是求阶层,这个函数呢求n的阶层,
这个阶层呢,我们知道是从1乘到n自身,
那么在一般的情况下呢,如果0,那就什么也不乘,也就返回一个1,在更一般的情况下,
它是怎么样做的呢?我们知道这个6的阶层是乘以1,乘了6,
那我们可以用5的阶层,就是n-1的阶层乘以n,
就得到了这个n的阶层。所以呢,这边这里呢
阶层这个函数里面,又调用了n-1的阶层, 它是这么一个,通过这个函数呢
自己调用自己,从而得到一个 结果。那在这里面呢,我们一般说呢,它是这样的一个模式,就是说,
一种特殊情况,那我们特殊处理。一般的情况下呢, 会调用前一步,比如说,n-1的,就是
结果,然后呢得到这一步的结果。实际上就是我们把那个任务呢分解了,就是
分解成同样的一个问题,这就是递归。
我们下面呢再看一个例子。好,这个例子呢,是画一棵树,我们用
Cayley这个数学家的名字命名的这个Cayley树,
我们运行一下看看这个结果。你看这就是一棵漂亮的树,
那在这里面呢,这棵树如果我们用传统的办法去画它是很困难的,
但是我们换一个角度来考虑问题,就是任何一棵树呢,它是
一个直线,也就是树干,再加上呢两棵子树,
而这个子树呢本身呢又是一个树干,我们画一个直线就行了,再加两棵子树。
所以我们可以看出呢,它实际上呢就是树,
画树呢是,还是调用画树的过程,所以这就是我们这个 程序的一个流程。我们看看程序代码是怎么写的。
其中呢这个核心的代码就是draw,draw,画树这个过程,画树这个过程呢,我们要画- 一棵树呢,
给它一个树的级别n,然后呢一个生长点x0,y0, 这个位置,还有这个树干的长度
以及呢树的倾斜的角度θ,那这个地方呢我们可以把
树,如果n=0,那就什么也不画了,这个特殊情况,我们看看一般情况下。
一般情况下,我们算出来x1等于x0,加上长度,乘上 cos角度,y1呢乘以sin的角度,
这里是。所以这就是我们说的 另一个树干的那个分叉的
就是x1,y1。然后呢我们画一条直线,然后呢
再画两棵子树,画两棵子树呢也就是drawTree,所以又调这个drawTree,
其中呢我们在这里面这个级别呢,就是n-1了, 然后这个树的生长点呢是x1,y1,它的长度
是我们这个长度乘上个person1,是一个比例,然后角度呢再加一个th1,
另一棵子树呢我们角度呢减一个th2,
长度呢也是另一个百分率乘上一个百分数。所以这样我们就可以把这棵树呢
从自身再调用自身就draw出来了。当然还有一些具体的drawlining,我们用g- raphics
那这个graphics呢,我用this.
得到的。另外要注意的就是我们在这个地方呢,
画图啊等等界面的一些操作呢,
我们都要尽量地用SwingUtilities .invokeLater,就是过后调用,或者稍后调用,
稍后调用我们简单地理解。
那这里面呢我们是,调用的它是一个
runnable的一个接口,当然我们可以用Lambda表达式
来写成,就是0个参数,然后箭头号,
一个方括号,要执行的事情。
总地说呢,递归算法呢基本模式呢就是 f(n)当中再调用f(n-1)。
那么递归算法呢也是我们计算机最擅长做的,
这是因为我们可以把很多问题呢划归为 自己的问题,这里我们刚才举了两个例子,
当然呢,现实生活里面,还有很多这样的例子。它实际上呢就是一个局部
跟一个整体是相似的,那这是局部问题跟一个整体问题它具有相似性,
所以这也是递归算法呢它之所以用途广泛的一个原因。
我们下面再看看回溯算法。
回溯算法呢,也叫试探回溯法,它的意思呢
就是说我们在寻找一个解决方案的时候,我们向前走一步,
那么在走的过程当中,如果发现这个不满足条件了,然后我们再回过头来进行纠正,
那这个呢就是一个试探回溯办法。那我们这里举一个
八皇后的问题。八皇后呢可能大家都清楚了,指的是 我们在一个棋盘上要放8个皇后,
因为这个皇后呢就纵的,纵线的、横线的,它都不能够在,就是两个了
都不能够在同一条纵线、横线,也不能在一条45度的斜对角线上面。
所以这样的话,就是我们要把这个棋盘呢8个格子放8个皇后,那怎么做?
我们看看这个代码。