递归的理解
1.什么是递归?
递归就是直接或间接的调用自己,体现了以此类推,重复同样的步骤。
2.怎么对一个问题建模并转化为递归的形式?
这个问题就大了,首先建模这个东西已经超出了程序员的范畴,那其实是数学的一部分。
3.什么时候会考虑使用递归?
分析这个问题的内在规律,也即分析出递推形式。如果有这种形式,可以考虑递归,如果存在着这种嵌套中带有嵌套,嵌套中,又有嵌套,可以考虑递归。
递归程序设计流程:
(1)分析问题,寻找递归关系。找出大规模问题和小规模问题的关系。换句话说,如果一个问题能用递归方法解决,它必须可以向下分解为若干个性质相同的规模较小的问题。
(2)找出停止条件,何时终止。
(3)设计递归算法,确定参数,即构建递归体。
递归算法包括两个阶段,一个是递推,另外一个是回归。
递推,是从未知到已知推进,最终达到已知的条件。
回归,是从从已知到未知,最后达到递推的开始处。
4.举例
合并排序
8个数进行排序,采用合并排序思想,先进行分析,然后画图,最后进行编程
分析:8个数分为2段,针对左半段进行分析,有半段进行分析
做半段也是如此分为2段。有半段也是如此,分为2段
最后到了分成很小的段,有很多个,然后对其进行合并,合并完了之后,在进行向上合并,
知道左半段和有半段思想和整体思想一样,所以函数是递归形式的。
画图:
如果C中没有合并函数,则A中合并和B中的合并更无从谈起,所以要以嵌套中的嵌套的嵌套来理解,这才是编写程序的出路
现在分析已经分析完了,画图也画出来了,编程如下:
MergeSort(int A[],int low,int high)
{
int middle=(low+high)/2;
MergeSort(A,low,middle);
MergeSort(A,middle,high);
//最重要的就是这条,因为已经想通了
Merge(A,low,middle,high)//说白了,最后的合并排序,其实就是插入排序思想吗。
}
还有就是图画出来之后,还要想程序的出口,比如这里的出口是low<high,想到这里之后,剩下的就是代码组合了。最后在看看少不少逻辑,在修改下,即可。
5.用以上这个方法,就可以对图中的深度优先遍历,观察其代码,是否可以以这样的思路这样写。
还有就是图画出来之后,还要想程序的出口,比如这里的出口是low<high,想到这里之后,剩下的就是代码组合了。最后在看看少不少逻辑,在修改下,即可。方法完全适用。
转载于:https://blog.51cto.com/1464490021/1864934