5.如何转发和返回？很多人看完递归原理会有这种感觉，哦，这个原理我懂了，然后再找个题目看看能不能写出来，突然发现还是不行。其实这种现象很普遍，所以如果你也是这样，也没什么好郁闷的。递归执行过程我敢保证你能看懂，基本优于30%的人。所以我想，还是写一下我对递归思维的理解吧。我对递归这个词的理解应该是传递和回归。如何传递自己的状态，如何返回一个结果，是递归问题的基本思路。所谓怎么转，我觉得思考的难点就是数学模型怎么抽象出来，如果是一个公式明确的斐波那契数列，就很简单，怎么直接按照公式去运算，难得就是只有叙述性的语言，比如这种题：一段楼梯有n个台阶。您可以选择一次上一级，也可以选择一次上两级。有多少种方法可以登顶？好像很深奥吧？事实上，这只是斐波那契数列的一种变体。对于这种描述性的题目，如果要抽象出一个数学模型，我觉得最好的办法是先列几个，看看有没有规律可循，然后再猜测证明。首先，让我们看看有多少种方法可以上2楼的楼梯。2层楼梯可以一次爬，也可以分两步，一步一步，所以F(2)=2。如果只有一层又没有呢？，显然只有一种方法可以走（一次上一层不走），即F(0)=1，F(1)=1，下面，你想上三楼，你的方式要么是从一层开始到二层到三层，要么是从一层到三层，或者一层层往上走，所以F(3)=3，好像有还是没有规律，然后往下走，现在我们要上四楼了，那我们换个思路，怎么上四楼呢？要么你是三楼到四楼，要么二楼到四楼，为什么不说一楼到四楼呢？因为如果你把这个当成一种情况，你会发现在第一个层次，无论你接下来做什么，都会回到上面两种情况。所以去四楼的方式是F(3)+F(2)，因为你已经到了三楼或者二楼（如果你选择二楼的下一层，你就去三楼)方法不谋而合），确定了下面的方法，不同的是前面的方法，就是F(4)=5，现在让我们加大难度，如果你想去第n层，那么你应该说***一步可以从n-1层走两层，也可以从n层走两层。也就是说，到第n层的方式取决于你是如何到第n-1层和第n层的，所以这个走法应该是F(n)=F(n-1)+F(n-2).另一种不知道如何迁移是不知道如何将递归算法转换为程序。你知道如何用语言来描述递归，但你就是不知道如何用程序来描述它，所以最好的办法就是找一个递归程序。然后查看每次递归的输出。至于如何返回，需要找到递归的终止条件，比如斐波那契数列，n=0就是数列的终止条件，不要小看终止条件，如果找不到终止条件或者定义错误，后果是无限递归导致程序栈崩溃，最终整个程序快速崩溃。我们从一个简单的开始，用递归算法求***公约数，用滚动除法。简单的说，对于两个数m和n，用公式gcd(m,n)=gcd(n,m%n)=gcd(m%n,m%n%n)，直到余数为0，这就是一个比较明显的递归模式，有一个数学公式，所以根据这个数学公式的逻辑，这个递归算法的回归是n==0，所以这个算法很容易写。***共同点代码比较简单，思路应该很清晰。然后，让我们再看看二分查找。二分查找就是在排序好的序列中寻找目标数，比如{1,2,...,10}。如果要找2，那么先找出这组数的中值是5，2比5小，所以就到0-5这部分，那里的值为2，然后就找到了。这个搜索过程也是一个不断传递的过程。将某个数列的中值与要求的目标值进行比较。如果比它小，则在数列的后半部分做同样的操作。如果它比它大，就对前半部分做同样的事情。那么这次回归的条件是什么？应该说有两种，一种是找到了，也就是某个中值等于目标值，还有一种是没有找到，可以定义为找到第一个元素，最后一个元素还是没有找到，则递归结束，代码如下：intBinarySearch(inta[],intn,intlow,inthigh){intmid=(low+high)/2;if(n==a[mid])returnmid;if((mid==high||mid==low)&&n!=a[mid])return0;if(n>a[mid])BinarySearch(a,n,mid+1,high);elseBinarySearch(a,n,low,mid);}通过代码可以看出思路和我上面语言描述的基本一致。这就是递归的好处，可以让代码更清晰。6.“高帅夫”设备如果你看过一些时间复杂度可以达到O(NLOGN)的排序算法，你会发现它们不仅效率高，而且代码也很简单，因为递归的使用使得很多复杂的过程变得简单，这样算法就可以更容易地实现。首先要说的是归并排序。归并排序简单的说就是把一个数列平均分为两个小数列，然后对每个小数列进行独立排序，然后合并在一起进行排序。也就是用几个有序的子序列得到一个有序的数列。说明一下，举个例子，就用百度的这个例子：比如 有一个序列{6,202,100,301,38,8,1}初始状态：[6][202][100][301][38][8][1] i=1[6202][100301][838][1] i=2[6100202301][1838] i=3 [16838100202301] 整个过程就是不断的划分子序列，不断的排序，这显然是一个在过程中递归，传递的过程就是不断传递子序列，那么回归条件是什么？看来，能看到这里并不容易。从上面的过程可以大致看出，如果series的个数只有1，那么就会开始回归，所以我们采用了一种方法。既然我们要找中间的值，那么要保存左边的索引和右边的索引，利用这两个索引，就可以判断数组中有多少个值了，所以我们取一个先看代码。voidMergeSort(intnumbers[],intarray_size){int*tmpArray=newint[array_size-1];MergeSort(numbers,tmpArray,0,array_size-1);}voidMergeSort(intnumbers[],inttmpArray[],intleft,intright){if(left
