遞迴分為直接遞迴和間接遞迴兩種:
直接遞迴: 直接在函式內再次呼叫本身函式
function fn1() {
fn1();
}
間接遞迴: 函式呼叫另外的函式,再從另外函式呼叫原來的函式
function fn1() {
fn2();
}
function fn2() {
fn1();
}
遞迴真的蠻常見的,像以下的案例都有使用到:
和分治法、和樹資料結構相關的狀況
// flatten([1, 2, 3, [4, 5] ]) // [1, 2, 3, 4, 5]
// flatten([1, [2, [3, 4], [[5]]]]) // [1, 2, 3, 4, 5]
// flatten([[[[1], [[[2]]], [[[[[[[3]]]]]]]]]]) // [1, 2, 3]
// 用 for loop
function flatten(arr){
let result = [];
for(let i = 0; i < arr.length; i++) {
if(Array.isArray(arr[i])) {
result = result.concat(flatten(arr[i]));
} else {
result.push(arr[i]);
}
}
return result;
}
// 用 reduce
function flatten(arr){
return arr.reduce((result, ele) => {
if(Array.isArray(ele)) {
return result.concat(flatten(ele));
}
return result.concat(ele);
}, [])
}
所謂的回文就是一個字串從左邊讀到右邊結果和從右邊讀到左邊的內容都一樣,這樣就是回文。
ex:level
,Race car
,Do geese see God?
因此問題就是: 給定一個字串,然後判斷此字串是否為回文,若是回文就回傳 true,不是就回傳 false
了解問題後就來實作吧!
我們可以把思考邏輯寫下來:
思考完畢,先建立一個判斷函式並完成部分內容:
// 設定start索引為0,end索引未知,故為null
function isPalindrome(str, start = 0, end = null) {
// 先初始化end的值
if (end === null) end = str.length - 1
if(str.length < 2) { // 只有一個或零個字元,歸類為回文
return true;
} else if (end <= start) { // 全部字元都比較完成時
return true;
} else {
}
}
完成剩下 else{} 的部分:
const ALPHABET = "ABCDEFGHIJKLMNOPQRSTVWXYZ"
function isPalindrome(str, start = 0, end = null) {
if (end === null) end = str.length - 1
if(str.length < 2) {
return true;
} else if (end <= start) {
return true;
} else {
// 將要比較的字母都轉大寫
let c1 = str.charAt(start).toUpperCase()
let c2 = str.charAt(end).toUpperCase()
// c1,c2 不是字母的話,必須移動到後一個/前一個字母,並再呼叫一次isPalindrome()
if (!ALPHABET.includes(c1)) {
return isPalindrome(str, start + 1, end)
} else if (!ALPHABET.includes(c2)) {
return isPalindrome(str, start, end - 1)
} else if (c1 !== c2) { // 兩個比較字母不同,肯定不是回文
return false
} else {
return isPalindrome(str, start + 1, end - 1) // 讓start到後一個字元位置,end到前一個字元位置,重新執行函式
}https://github.com/a90100/javascript-data-structure/blob/master/day10-recursion.js
}
}
完成判斷函式了,完整的程式碼在以下連結:
https://github.com/a90100/javascript-data-structure/blob/master/day10-recursion.js
function stringifyNumbers(obj) {
let newObj = {}
for (let i in obj) {
if (typeof obj[i] === 'number') {
newObj[i] = obj[i].toString();
} else if (typeof obj[i] === 'object' && !Array.isArray(obj[i])) {
console.log(obj[i])
newObj[i] = stringifyNumbers(obj[i])
} else {
newObj[i] = obj[i];
}
}
return newObj;
}
let obj = {
num: 1,
test: [],
data: {
val: 4,
info: {
isRight: true,
random: 66
}
}
}
console.log(stringifyNumbers(obj));
/*
{
num: "1",
test: [],
data: {
val: "4",
info: {
isRight: true,
random: "66"
}
}
}
*/
這次的介紹到此結束。明天我們將會來介紹樹 Tree 此種資料結構!
tail call optimization 可以研究一下,用來優化遞迴