一.遞歸的概念 一個直接或間接調(diào)用自身的算法叫做遞歸算法。即自己調(diào)用自己。 遞歸的關(guān)鍵點在結(jié)束條件。 二.通過例子看遞歸 1.求數(shù)的階乘 數(shù)學公式:
0!,1!-->1這可以作為遞歸結(jié)束的判斷條件//遞歸形式實現(xiàn)數(shù)的階乘int Factorial(int n){ if(n == 0 || n == 1) //0和1作為遞歸結(jié)束的條件 return 1; return (n * Factorial(n-1));}//非遞歸形式實現(xiàn)數(shù)的階乘int Factorial2(int n){ int sum = 1; if(n == 0 || n == 1) return sum = 1; while(n != 1) { sum = sum * (n--); } return sum;}2.斐波那契數(shù)列遞歸求解 形如1,1,2,3,5,8,13,21,34,55這樣的數(shù)列即為斐波那契數(shù)列，其中第1和第二個數(shù)要求為1. 遞歸求解第n個數(shù)的值，其遞歸結(jié)束條件即為當?shù)?和第二個數(shù)要求為1時結(jié)束。
//非遞歸求解斐波那契數(shù)列第n個值int Fib(int n){ int fib1 = 1; int fib2 = 1; int fib = 2; for(int i=3; i<=n; i++) { fib = fib1 + fib2; fib1 = fib2; fib2 = fib; } return fib;}//遞歸求解斐波那契數(shù)列第n個值int Fib2(int n){ if(n == 1 || n == 2) return 1; return (Fib2(n-1)+Fib2(n-2));}3.二分法查找 分治法的基本思想： 分治法的基本思想是將一個規(guī)模為n的問題分解為k個規(guī)模較小的子問題，這些問題互相獨立又與原問題相同。遞歸的解決這些子問題，然后將各子問題的解合并得到原問題的解。 舉例：在一串有序數(shù)列中找到某元素,如果找到，返回元素下標；反之，返回-1.
//非遞歸二分法查找//ar為一整型數(shù)組，len為其長度，key為要查找的值int Find(int ar[], len, int key){ int low = 0; //記錄查找起始位置 int high = len-1; //記錄查找結(jié)束位置 while(low <= high) { mid = (low+high)/2; if(key > ar[mid]) low = mid + 1; else if(key < ar[mid]) high = mid - 1; else return mid; } return -1;}//遞歸二分法查找...int low = 0;int high = n - 1;...int Find2(int ar[], int low, int high, int key){ mid = (low+high)/2; if(low > high) return -1; if(key == ar[mid]) return mid; else if(key > ar[mid]) Find2(ar, mid+1, high, key); else Find2(ar, low, mid-1, key); }}新聞熱點
疑難解答
