各种算法七
在第六篇中，我简单的提了一下递归的思想；至于什么是递归，以及我对递归的理解，你可以看我的这篇博文：http://www.cnblogs.com/mc67/p/5114008.html
如果，不理解递归就看上面的图，如果还是不理解，就自己百度；
递归的作用在于把问题的规模不断缩少，直到问题缩少到能简单地解决
阶乘n！= 1 * 2 * 3 * 4 * ··· * n
//具体的实现； //ps阶乘的英文是：factorial public static int factorial(int n) { if (n == 1) { return 1; } else { return n * factorial(n - 1); } }
然后就是我们的....
2.递归的应用：输入 n，求斐波那契数列第n个数，
这到道题可以说是被我们的面试官考烂的一道一呀；
首先你得要找出斐波那契数的规律滴啊:0 1 1 2 3 5 8 13 21......
第3项开始，每一项都等于前两项之和
public static int fibonacci(int n) { if (n == 0) { return 0; } if (n == 1) { return 1; } //从第三项，开始，我们的规律就出来了滴啊； return fibonacci(n) + fibonacci(n - 1); //这个及时我们的额规律滴哎呀；,效果还是不错滴哎呀 }
3.递归的应用：找到我们的回文数滴呀
首先你要理解什么是我们的额回文数滴呀；
就是一个字符串,从左到右边，以及从右到左边，完全是一样的；level aoa oco aabb
递归的作用在于把问题的规模不断缩少，直到问题缩少到能简单地解决
1. 字符串长度可能会奇数或偶数：
- 如果字符串长度是奇数，字符串会剩下最中间那位字符，但其不影响回文。当检查到长度为1的时候即代表此字符串是回文
- 如果字符串长度是偶数，当两端的字符串两两比较检查后不会剩下字符。即检查到长度为0的时候即代表此字符串是回文
2. 如果检查到两端两个字符不相同。则说明此字符串不是回文，直接返回0，不需要继续检查
数组问题存在奇数和偶数的情况是，我们一般不用 len/2 的方式，而使用的是我们的low 和 high 两个类似指针的效果来进行寻找滴哎呀；
//接下来是我们回文数的 判断滴啊； public static int fun(int low, int high, string arr, int length) { //数组的长度在不断的减小滴呀； if (length == 0 || length == 1) { return 1;} if (arr[low] != arr[high]) { return 0; } //否则就继续查找；匹配滴呀； return fun(low+1,high-1,arr,length-2); }
效果还是不错滴呀；不过，当然有我们的优化方式了滴呀；效果还是不错滴呀；
public static int fun2(int low, int high, string arr) { if (low < high) { if (arr[low] != arr[high]) { return 0; } return fun2(low + 1, high - 1, arr); }else { return 1; //两个指针都已经超出了，还没遇到不想等的值，我们就返回一滴呀； } }
4.递归的应用：字符串反转；
将字符串 fuck 翻转，变为kcuf
先看看我们的常规方式的呀；
public static void reverseString( string val) { //最low的方式， var newString = ""; var len = val.Length; for(var i = 0; i < len; i++) { newString += val[len-1-i]; } Console.WriteLine(newString); //low逼方式二 string str = ""; for(var i = len - 1; i >= 0; i--) { str += val[i]; //这样是我们的额low方式之一滴呀； } Console.WriteLine("low method :{0}",str); Console.WriteLine(); //当然有我们的方式三滴呀；效果还是不滴呀； var low = 0; var high = len - 1; //折是一种交换的方式滴呀； var arr = val.ToArray(); for(var i = 0; i < len; i++) { if (low < high) //用这种方式就不存在所谓的奇数个 和 偶数个的区分了滴呀；效果还是不错i呀； { //这里可以加一个判断，如果相同，就不交换滴啊； if(arr[low]!=arr[high]) { char temp = arr[low]; arr[low] = arr[high]; arr[high] = temp; } low++; //这里我们可以将i 和low high 三个变量关联起来，但是，没这个必要，否则逻辑就不清晰了； high--; }else { break; } } foreach (var i in arr) { Console.Write(i.ToString()); } }
接下来就是我们的优化了滴呀；
接下来使用我们的递归进行各种优化滴呀；效果还是不错i哎呀；然后..........
你会发现上面的代码都是嵌套在我们的for 循环中滴啊；那么我们可以使用递归来替换滴啊；
public static int reverseStr(int low,int high,char [] arr,int length) { if (length==0 || length == 1) { return 0; } if (arr[low] != arr[high]) { char temp = arr[low]; arr[low] = arr[high]; arr[high] = temp; } return reverseStr(low+1,high-1,arr,length-2); }
最后额效果还是不错滴呀
最后的优化滴呀；
public static int reverseStr(int low,int high,char [] arr) { if (low>high) { return 0; //这种方式也是可以滴呀；//而且效果不错滴呀； } if (arr[low] != arr[high]) { char temp = arr[low]; arr[low] = arr[high]; //这里就是交换的事项滴啊 arr[high] = temp; } return reverseStr(low+1,high-1,arr); }
5.递归的应用：折半查找滴啊；
这种查找，的前提是我们的数组是有序的顺序滴呀；才有折半意义滴呀；查找又是另外一个比较大的话题了；
第一种查找：漫无目的的遍历；
第二种查找：折半循环查找；可以将循环的次数减少为：len/2 但是这种方式仅仅限于偶数个的数组中，奇数的话，无法整除，但是我们可以使用low 和 high两个指针滴呀；
第三种查找：对有序数组的这边查找，现在我们讨论的就是现在这种滴呀；
还是先看我们比较low的算法，然后再一步一步的优化吧
public static int LookUpIndex() { string str = "fuck the life"; char key = 'e';//找到第一个就停止了； int len = str.Length; int low = 0; int high = len - 1; //一般又是一个循环 for (var i = 0; i < len; i++) { if (low > high) return -1; if (str[low] == key) { return low; };//返回下标 if (str[high] == key) { return high; } //返回下标 low++; high--; } return -1; }
用我们的递归来替换我们的for循环滴啊；
public static int LookUpIndex2(int low,int high,int [] arr,int key) { //记住这查找的是我们额有序数组滴呀； int middle = (low + high) / 2; if (arr[middle] == key) { return middle; } //这里就不能返回执行的数字的额小标了； if (low > high) { return 0; } //终止我们循环的条件滴呀；我不知道这个算不算我们正规意义上的递归滴呀； if (arr[middle] > key) { //在左边进行查找//就要移动我们额high high = middle - 1; return LookUpIndex2(low,high,arr,key); }else { //在右边进行查找滴啊 low = middle + 1; return LookUpIndex2(low, high, arr, key);//继续我们的额折半查找滴哎呀； } }
这样我们递归的常用方式就总结到这里滴啊；