首页 > 代码库 > 《递归》算法设计一
《递归》算法设计一
什么是递归?
它有这样的特征,求解规模为N的问题时,设法将它分解成规模较小的问题,然后根据这些小问题方便的构造出大问题的解。当然程序必须有一个出口,当规模为1的时候,能直接的到解。
小结:就是把问题层层分解,直到程序的出口处。
注意事项
1.递归应有终止的时候,也就是每一个递归必须有一个出口,否则会无限递归出去。
2.递归就是调用自身的方法。例如f(n)=n*f(n-1)
裴波纳契数列
先观察下面一组数字有何规律呢
1、1、2、3、5、8、13、21、34……
如果给你上面这些数字,估计能够很快的写出后面的55、89等
如果细心的话,就可以发现规律f1=1、f2=1、 f(n)=f(n-1)+f(n-2)(n>2)
到此我们在返回去看递归的定义,就会发现,每一个根问题都可以通过子问题来得到结果,所以最终呈现出这样一种现象,层层递归。
DEMO
class Fibonacci { static void Main(string[] args) { int result = fib(5); Console.WriteLine(result); } public static int fib(int index) { //定义能够直接得到的值 //也就是程序的出口 if(index==1||index==2) { return 1; }else { //嵌套递归 return fib(index - 1) + fib(index - 2); } } }
程序的分析流程图如下
还有一些求N的阶乘的问题,跟上面类似都是一类的套路。下面看一个经典的问题。
汉塔诺问题
看上面的图片要解决的问题是
如何把A上面的N个盘子借助B移动到C上,条件是
1.一次只能够移动一个盘子
2.移动过程中大盘子永远不能放到小盘子上面
看了这个问题,我们可以肢解一下,实现过程如下
1.先把A柱子上的前N-1个盘子从A借助C移动到B上
2.将A柱子上的第N个盘子直接移动到C
3.再将B柱子上的N-1个盘子借助A移到C上
通过分析,我们发现上面的过程也是递归的,不管事N个还是N-1个盘子,实现的步骤都是上面的过程。
class HuoNaTa { static void Main(string[] args) { //定义三个盘子 char ch1 = 'A'; char ch2 = 'B'; char ch3 = 'C'; move(5, ch1,ch2,ch3); } /// <summary> /// //移动的过程 /// </summary> /// <param name="num">盘子数目</param> /// <param name="A">A柱子</param> /// <param name="B">B柱子</param> /// <param name="C">C柱子</param> private static void move(int num,char A,char B,char C) { //如果是一个盘子 //直接将A柱子上的盘子从A移动到C if(num==1) { Console.WriteLine("移动盘子1从" + A + "到" + C); } else { //如果是多个盘子 //先将A柱子上的N-1个盘子借助C移到B //直接将A柱子上的盘子从A移到C //最后将B柱子上的N-1个盘子借助A移到C move(num - 1, A, C, B); Console.WriteLine("移动盘子" + num + "从" + A + "到" + C); move(num - 1, B, A, C); } } }
总结
对于算法,确实刚上来理解不是特别的容易,但是所有的操作都需要亲身实践,包括每一步流程都需要认真的写下来,在写的过程中摸索规律,对于汉诺塔自己理解的也不是特别的深刻,但是能够从宏观上知道每一步的流程,然后通过递归来实现。也不知各位发现了木有,所有的递归在实现上都是有两步。一则定义出口,二则定义需要递归的地方。如果这么看的话,递归也就这么一回事。
当然关于递归还有需要要学习的,有不对的地方,多多指正!
《递归》算法设计一