微信号:grzlwx

介绍:光荣之路官方资讯

算法洗洗脑——第二篇 递归思想

2015-07-08 23:04 光荣之路

今天说说递归思想,在我们编码时,有的时候递归能够让我们的算法更加通俗易懂,并且代码量也是大大的减少。比如我先前的系列中说到了关于树的“先序,中序和后序”遍历,那么看看用递归来描叙这个问题是多少的简洁,多么的轻松。

 1 #region 二叉树的先序遍历
2 /// <summary>
3 /// 二叉树的先序遍历
4 /// </summary>
5 /// <typeparam name="T"></typeparam>
6 /// <param name="tree"></param>
7 public void BinTree_DLR<T>(ChainTree<T> tree)
8 {
9 if (tree == null)
10 return;
11
12 //先输出根元素
13 Console.Write(tree.data + "\t");
14
15 //然后遍历左子树
16 BinTree_DLR(tree.left);
17
18 //最后遍历右子树
19 BinTree_DLR(tree.right);
20 }
21 #endregion
22
23 #region 二叉树的中序遍历
24 /// <summary>
25 /// 二叉树的中序遍历
26 /// </summary>
27 /// <typeparam name="T"></typeparam>
28 /// <param name="tree"></param>
29 public void BinTree_LDR<T>(ChainTree<T> tree)
30 {
31 if (tree == null)
32 return;
33
34 //优先遍历左子树
35 BinTree_LDR(tree.left);
36
37 //然后输出节点
38 Console.Write(tree.data + "\t");
39
40 //最后遍历右子树
41 BinTree_LDR(tree.right);
42 }
43 #endregion
44
45 #region 二叉树的后序遍历
46 /// <summary>
47 /// 二叉树的后序遍历
48 /// </summary>
49 /// <typeparam name="T"></typeparam>
50 /// <param name="tree"></param>
51 public void BinTree_LRD<T>(ChainTree<T> tree)
52 {
53 if (tree == null)
54 return;
55
56 //优先遍历左子树
57 BinTree_LRD(tree.left);
58
59 //然后遍历右子树
60 BinTree_LRD(tree.right);
61
62 //最后输出节点元素
63 Console.Write(tree.data + "\t");
64 }
65 #endregion

看看,多么简洁明了。当然递归都是可以改成非递归的,但是就不见得简洁和通俗易懂了。


一: 概念

递归,说白了就是直接或者间接的调用自己的一种算法。它是把求解问题转化为规模较小的子问题,然后通过多次递归一直到可以得出结果的最小解,然后通过最小解逐层向上返回调用,最终得到整个问题的解。总之递归可以概括为一句话就是:“能进则进,不进则退”。


二:三要素

<1> 递归中每次循环都必须使问题规模有所缩小。

<2> 递归操作的每两步都是有紧密的联系,如在“递归”的“归操作时”,前一次的输出就是后一次的输入。

<3> 当子问题的规模足够小时,必须能够直接求出该规模问题的解,其实也就是必须要有结束递归的条件。


三: 注意

<1> 前面也说了,递归必须要有一个递归出口。

<2> 深层次的递归会涉及到频繁进栈出栈和分配内存空间,所以运行效率比较低,当问题规模较大时,不推荐使用。

<3> 在递归过程中,每次调用中的参数,方法返回点,局部变量都是存放在堆栈中的,如果当问题规模非常大时,容易造成堆栈溢出。


四: 举二个例子

<1> 相信大家在初中的时候都学过阶乘吧,比如:5!=5*4*3*2*1

思路:根据上面的阶乘特征很容易我们就可以推导出n!=n*(n-1)*(n-2)....*2*1,

那么进一步其实就是: n!=n*(n-1)! ,

(n-1)!=(n-1)*(n-2)!。

显然他是满足递归的三要素,当n的规模不大时,我们可以用递归拿下。

 1 static void Main(string[] args)
2 {
3 while (true)
4 {
5 //阶乘问题
6 Console.WriteLine("\n请输入一个求阶乘的一个数:");
7
8 int num = int.Parse(Console.ReadLine());
9
10 Console.WriteLine("\n阶乘的结果为:" + fact(num));
11 }
12 }
13
14 static int fact(int n)
15 {
16 if (n == 1)
17 return 1;
18
19 return n * fact(n - 1);
20 }


第一次: 输入5的时候能够正确求出。

第二次: 输入10的时候求出来竟然362万之多,可见多恐怖,如果俺们的时间复杂度是n!,那程序也就Game Over了,

第三次:输入100,已经超过了int.MaxValue了,

第四次: 输入10w,蹦出著名了“堆栈溢出”,好家伙,我们知道“递归”在程序中使用“栈”的形式存放的,每一次“递归”中,方法的返回值包括函数中的参数都会存放在栈中,C#中每个线程分配的栈空间为1M,所以当N的规模非常大时,就把栈玩爆了。


<2> 在大一时上计算机文化基础的时候我们就接触过”进制转换问题“,比如将”十进制“转化为”二进制“。

思路:采用除2取余法,取余数为相应二进制数的最低位,然后再用商除以2得到次低位.......直到最后一次相除商为0时得到二进制的最高位,

比如(100)10=(1100100)2, 仔细分析这个问题,会发现它是满足”递归“的三要素的,

① 进制转换中,数据规模会有所缩小。

② 当商为0时,就是我们递归的出口。

所以这个问题我们就可以用递归拿下。


static void Main(string[] args)
{
Console.WriteLine("请输入一个十进制数:");

int num = int.Parse(Console.ReadLine());

string result = string.Empty;

Console.WriteLine("转化的二进制为:" + ConvertToBinary(ref result, num));

Console.ReadLine();

}

static string ConvertToBinary(ref string str, int num)
{
//递的过程
if (num == 0)
return string.Empty;

ConvertToBinary(ref str, num / 2);

//归的过程
return str += (num % 2);
}


(作者:一线码农 来源:http://www.cnblogs.com/huangxincheng/archive/2011/12/30/2306875.html)


一字一句当思来之不易,感谢作者,传播测试知识、技能与正能量!




光荣之路软件测试培训

官网:http://www.gloryroad.cn/

微信公众号:gloryroadtrain

性能测试QQ群:415987441
软件测试招聘QQ群: 203715128
自动化3群QQ: 371211499




 
光荣之路 更多文章 今天晚上的 linux 公开课- Awk 编程 7月28日(今天)晚上的 linux 公开课- shell编程 8月4日(今天)晚上的 linux 公开课- shell编程 9月1日(本周一)晚8点半,光荣之路Web自动化系列基础课—javascript第二讲 推荐本好书《与机器赛跑》
猜您喜欢 JAVA-CAS简介以及ABA问题 GPG入门教程 有人向我提了一个 Bug,说 5 分钟就可以搞定 PHP语言基础简单整理 Growth Hacking简史