刷题后感——递归

1 递归的次数和递归的深度问题。

递归次数与每次划分后得到的分区处理顺序无关。

对n个记录的线性表进行快速排序为减少算法递归深度,每次分区后先处理较短部分。

以上是题目中总结的知识点,第一条比较好理解,假设1,2,3,4四个数字,第一次划分得到(1),(2,3,4),先处理1 ,返回,处理(2,3,4)->(2)返回,(3,4)->(3)返回,(4)返回,和先处理大分区是相同的划分过程,(1,2,3,4)->(1),(2,3,4)->(1),(2),(3,4)->(1),(2),(3),(4)再逐一返回。由这个划分大致可以看出大小分区的处理先后顺序并不影响递归的次数。

递归深度可以理解为系统栈保存的深度(题目解析这么说的,摊手)。那同样是上面这个例子,两种处理方式就可以看出栈的深度不同,小分区,处理1时,栈中存一个元素(2,3,4),返回后再处理(2,3,4),同样(3,4)仅占用一个位置,这样栈的深度仅为1。第二种方式,处理(2,3,4)时,1入栈,->2入栈,处理(3,4)->3入栈->处理4,再依次返回,所以在处理4的时候栈的深度可以达到4。