由合并排序算法谈如何理解递归

时间:2022-12-04 11:07:16
 

今天早上突然来了兴致,拿起了尘封多月的《算法导论》翻看起来,正好看到合并排序一章,看完介绍后自己动手编程实现,经过简单的调试纠错后程序正确执行,但是细细一品其中用到的递归知识,感觉糊里糊涂,有种只知表面不知根源的感觉。上网查阅相关资料发现有部分朋友跟我有同样地感受,不知道递归的原理究竟是什么,经过我苦思冥想后,决定用一种通俗易懂但也许并不符合科学的方式理解递归,写这篇文章的目的就是和大家一起交流关于递归的经验,共同进步。

合并排序的具体代码就不在这里给出了,不清楚的朋友可以查阅相关资料。这个算法有关递归的一段程序如下(伪代码):

Merge_sort(A,p,r)

{

         If p < r

                   Then q ← 下取整[(p + r) / 2]

                     Merge_sort(A,p,q)

                     Merge_sort(A,q+1,r)

                     Merge(A,p,q,r)

}

其中,Merge_sort是分解过程的函数,Merge是合并过程的函数;A存放待排序数列,p是操作序列起点序号,r是操作序列终点序号。

我们用一种树的概念来理解,由于这个递归是双向的,类似于二叉树。递归一定有一个终止条件,不到达这个终止条件递归是不会停止。如果到达了终止条件,递归就会返回上一层,利用上一层的变量进行相关操作。如果上一层还有其他路径的递归,则按照其他路径一路递归到底,然后返回,在逐层返回的过程中,在每层利用该层的变量完成相关的操作。说了一些晦涩难懂的文字,想必大家一定看着头晕,下面结合实例予以进一步的解释:

由合并排序算法谈如何理解递归

从图中可以看到,假如我们一开始的函数是merge_sort(A,0,2),那么程序就会一直将merge_sort(A,p,r)执行到底,即merge_sort(A,0,2)→merge_sort(A,0,1)→merge_sort(A,0,0),直到执行到merge_sort(A,0,0)时,满足推出条件,这是程序返回上一层(图中所示2层),这一层的参数是p=0,r=1,q=0,这一层下一条语句是merge_sort(A,q+1,r),即merge_sort(A,1,1),其实这条语句在图中反应的就是由2层走右侧路径到达3层,由于满足退出条件所以再次返回2层,接下来执行2层的最后一条语句merge(A,p,q,r),即merge(A,0,0,1)。执行完这条语句后,左侧2层的任务结束,返回一层,一层的变量是p=0,r=2,q=1。由于1层已经执行完成了第一条语句,所以1层要执行第二条语句,即merge_sort(A,q+1,r),即merge_sort(A,2,2),满足退出条件,再次返回1层,接下来执行1层的merge(A,0,1,2)后,程序结束,完成合并排序的功能。

    由于合并排序有两个递归函数,所以该程序的执行路径类似于二叉树的遍历过程。其实,好多程序只涉及到一个递归,为了加强理解,我们再举一例:

         考虑如下递归程序,最终的输出是多少?

void a(int num)

{

     if(num > 0)

     {

         num -- ;

         a(num) ;

         printf("%d " , num);

     }

}

main()

{

      a(4) ;

      system("pause");

      return 0 ;

}

输出结果:0 1 2 3

按照之前所说,我们先画出递归树,写出每一层的变量值,按照先递归到底再逐层返回的步骤分析:

由合并排序算法谈如何理解递归

由图分析,当执行a(4)时,会直接递归到底a(4)→a(3)→a(2)→a(1)→a(0),递归到a(0)后由于满足递归退出条件所以逐层向上返回,由于每一层的第一(num--)、第二(a(i))语句已经执行完毕,所以每当返回到某一层是,就会根据该层的num值打印出相应结果,所以最终的输出结果时0 1 2 3。

看了两个例子,大家是不是已经有了一些想法啊,浣熊在这里总结一下:如果遇到递归,如果没有达到递归条件,就要一直递归到底;递归到底后,逐层返回,到每一层时,利用该层的变量值去执行递归语句的下一条语句,直到返回到根节点的一层,程序结束。

好啦,总之我现在对递归的工作过程有了深入的理解,不知道你看过文章后是否有了一些想法呢,如果有的地方看不懂,随时欢迎给我留言,我们一起进行讨论学习,加油哦。