遞歸: 所謂遞歸,就是既有傳遞,又有回歸,與其說是傳遞與回歸,初學不如理解是一種 “循序遞進”與“規律約束”。 為什麼這樣說,因為遞歸演算法相比較於迴圈在代碼結構方面個人認為更加簡潔清晰,清晰易懂,遞歸註重的是一種有序的規律,所以在每個程式開始之前,我們只要能找到一個使程式循序遞進的規律;並且在整個過 ...
遞歸:
所謂遞歸,就是既有傳遞,又有回歸,與其說是傳遞與回歸,初學不如理解是一種 “循序遞進”與“規律約束”。
為什麼這樣說,因為遞歸演算法相比較於迴圈在代碼結構方面個人認為更加簡潔清晰,清晰易懂,遞歸註重的是一種有序的規律,所以在每個程式開始之前,我們只要能找到一個使程式循序遞進的規律;並且在整個過程都在用此規律進行傳遞,但是遞歸演算法也有很大的缺點,會造成記憶體空間不足,從而形成記憶體溢出;所以針對這種缺點,就會引入“規律約束”,在每一次演算法的的開始之前,先對演算法進行一個規律約束,而這種約束可以理解為一個“歸期”;即到這個歸期不得已而為之……
eg:1 計算1+2+3+4+……+100的值。
function fn(n){ if(n==1)return 1; //歸期 return n+fn(n-1); //規律 } console.log(fn(100));
eg:2 計算n 和 1/n!的階乘。
1. n!
function fn(n){ if(n==1)return 1; //歸期 return n*fn(n-1); //規律 } console.log(fn(5));
2. 1/n!
function fn(n){ if(n==1)return 1; //歸期 return 1/n*fn(n-1); //規律 } console.log(fn(5));
eg:3 斐波拉契數列(求第n個數的數值)
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,377,610,987……function fn(n){ if(n==1||n=2)return 1; //歸期 return fn(n-1)+fn(n-2); //規律 } console.log(fn(8));eg:4 編寫一個函數,輸入n為偶數時,調用函數求1/2+1/4+...+1/n,當輸入n為奇數時,調用函數求/1+1/3+...+1/n
function fn(n){ if(n%2==0){ if(n<=2)return 1/2; //歸期 return 1/n+fn(n-2); //規律 } if(n%2!=0){ if(n==1)return 1; //歸期 return 1/n+fn(n-2); } } console.log(fn(4));
eg:5 求1!+1/2!+1/3!+...+1/n!(遞歸與迴圈的結合)
// function fn(n) { // if (n == 1) return 1; //歸期 // return 1 / n * fn(n - 1); //規律 // } // console.log(fn(5));
// function fn1(n) { // var sum = 0; // for (i = 1; i <= n; i++) { // sum += fn(i); // } // return sum; // } // console.log(fn1(5))