下面呢我们来看看递归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个皇后，那怎么做？
我们看看这个代码。
请看这里，这里呢
我们N是8，N等于8，这个，这个常数，fina int，
然后我们用一个数组，整数的数组呢来表示 每一列上皇后放的位置，就是一共
8列，就放8列。8列呢这个，因为
一列上面只能放一个了，所以我们记录这一列上面放的皇后的 纵向的位置y，这个y。那我们
在做的时候是怎么做呢？就是这样的，当x大于0，我们while一直循环下去，
然后我们在这个x这个位置上，这个x呢就表示
第x列了，就是横坐标x，那y[x] ++也就是把这一列上的数字啊，这个位置啊，
这个y位置呢++，先加一个，然后呢我们去判断它，
如果不满足，那我们while那个值呢再，再++，就一直往下。
如果我们找到了这个y N呢，
y的位置呢小于等于N就是可行的，那么可行的呢 我们又判断x是不是等于N，如果是等于N呢，
就找到了一个所有的列呢都找到了，然后我们把它显示出来。
那更一般的情况下呢，我们就x++，也就是说 我们每找到一个满足条件的，然后我们就
到下一列，那就是继续地走一步，继续寻找下一步。
否则的话，那就说明这个条件是不满足的，说明这个
就else，那我们怎么办呢？我们就把这一列呢 就这个置为空，也就是说这个是没有用的。
然后呢我们x再--，回溯一步，这样的话我们就
基本的模式呢就是一般的情况下呢，就是找到的话，就x++，
那没找到呢，我们就x--，就是要么前进一步，要么后退一步。
在前进的过程当中，我们做一些处理，比如说放这个位置，然后进行判断。
这就是呢回溯算法呢它的
前进，然后后退，基本上是这样的一个模式。
也就是说回溯算法的那种基本模式呢，是x++，如果
某种条件就x--，然后在循环里面反复地去这样做，
直到呢我们找到最后的结果。这个回溯算法当然也是
我们计算机里面最常用的算法之一，因为我们很多问题呢就是
如果我们有好多步骤，那我们要直接找到答案是很困难的，但是我们
可以呢试着往前走，走到如果不对，那我们再回过头来。
所以回溯算法呢也是计算机里面 最常用的算法之一。
唐大仕博士
