一、遞歸 遞歸（英語：Recursion） 在數學與電腦科學中，是指在函數的定義中使用函數自身的方法 在函數內部，可以調用其他函數。如果一個函數在內部調用自身本身，這個函數就是遞歸函數 其核心思想是把一個大型複雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解 一般來說，遞歸需要有邊界條件、 ...
一、遞歸
遞歸（英語：Recursion）
在數學與電腦科學中，是指在函數的定義中使用函數自身的方法
在函數內部，可以調用其他函數。如果一個函數在內部調用自身本身，這個函數就是遞歸函數
其核心思想是把一個大型複雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解
一般來說，遞歸需要有邊界條件、遞歸前進階段和遞歸返回階段。當邊界條件不滿足時，遞歸前進；當邊界條件滿足時，遞歸返回
下麵實現一個函數 pow(x, n)，它可以計算 x 的 n 次方
使用迭代的方式，如下：
function pow(x, n) {
let result = 1;
// 再迴圈中，用 x 乘以 result n 次
for (let i = 0; i < n; i++) {
result *= x;
}
return result;
}
使用遞歸的方式，如下：
function pow(x, n) {
if (n == 1) {
return x;
} else {
return x * pow(x, n - 1);
}
}
pow(x, n) 被調用時，執行分為兩個分支：
if n==1 = x
/
pow(x, n) =
\
else = x * pow(x, n - 1)
也就是說pow 遞歸地調用自身 直到 n == 1
為了計算 pow(2, 4)，遞歸變體經過了下麵幾個步驟：
pow(2, 4) = 2 * pow(2, 3)pow(2, 3) = 2 * pow(2, 2)pow(2, 2) = 2 * pow(2, 1)pow(2, 1) = 2
因此，遞歸將函數調用簡化為一個更簡單的函數調用，然後再將其簡化為一個更簡單的函數，以此類推，直到結果
二、尾遞歸
尾遞歸，即在函數尾位置調用自身（或是一個尾調用本身的其他函數等等）。尾遞歸也是遞歸的一種特殊情形。尾遞歸是一種特殊的尾調用，即在尾部直接調用自身的遞歸函數
尾遞歸在普通尾調用的基礎上，多出了2個特征：
- 在尾部調用的是函數自身
- 可通過優化，使得計算僅占用常量棧空間
在遞歸調用的過程當中系統為每一層的返回點、局部量等開闢了棧來存儲，遞歸次數過多容易造成棧溢出
這時候，我們就可以使用尾遞歸，即一個函數中所有遞歸形式的調用都出現在函數的末尾，對於尾遞歸來說，由於只存在一個調用記錄，所以永遠不會發生"棧溢出"錯誤
實現一下階乘，如果用普通的遞歸，如下：
function factorial(n) {
if (n === 1) return 1;
return n * factorial(n - 1);
}
factorial(5) // 120
如果n等於5，這個方法要執行5次，才返回最終的計算表達式，這樣每次都要保存這個方法，就容易造成棧溢出，複雜度為O(n)
如果我們使用尾遞歸，則如下：
function factorial(n, total) {
if (n === 1) return total;
return factorial(n - 1, n * total);
}
factorial(5, 1) // 120
可以看到，每一次返回的就是一個新的函數，不帶上一個函數的參數，也就不需要儲存上一個函數了。尾遞歸只需要保存一個調用棧，複雜度 O(1)
二、應用場景
數組求和
function sumArray(arr, total) {
if(arr.length === 1) {
return total
}
return sum(arr, total + arr.pop())
}
使用尾遞歸優化求斐波那契數列
function factorial2 (n, start = 1, total = 1) {
if(n <= 2){
return total
}
return factorial2 (n -1, total, total + start)
}
數組扁平化
let a = [1,2,3, [1,2,3, [1,2,3]]]
// 變成
let a = [1,2,3,1,2,3,1,2,3]
// 具體實現
function flat(arr = [], result = []) {
arr.forEach(v => {
if(Array.isArray(v)) {
result = result.concat(flat(v, []))
}else {
result.push(v)
}
})
return result
}
數組對象格式化
let obj = {
a: '1',
b: {
c: '2',
D: {
E: '3'
}
}
}
// 轉化為如下：
let obj = {
a: '1',
b: {
c: '2',
d: {
e: '3'
}
}
}
// 代碼實現
function keysLower(obj) {
let reg = new RegExp("([A-Z]+)", "g");
for (let key in obj) {
if (obj.hasOwnProperty(key)) {
let temp = obj[key];
if (reg.test(key.toString())) {
// 將修改後的屬性名重新賦值給temp，併在對象obj內添加一個轉換後的屬性
temp = obj[key.replace(reg, function (result) {
return result.toLowerCase()
})] = obj[key];
// 將之前大寫的鍵屬性刪除
delete obj[key];
}
// 如果屬性是對象或者數組，重新執行函數
if (typeof temp === 'object' || Object.prototype.toString.call(temp) === '[object Array]') {
keysLower(temp);
}
}
}
return obj;
};
參考文獻
- https://zh.wikipedia.org/wiki/%E5%B0%BE%E8%B0%83%E7%94%A8
如果對您有所幫助，歡迎您點個關註，我會定時更新技術文檔，大家一起討論學習，一起進步。
