iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 10
1

遞迴分為直接遞迴間接遞迴兩種:
直接遞迴: 直接在函式內再次呼叫本身函式

function fn1() {
    fn1();
}

間接遞迴: 函式呼叫另外的函式,再從另外函式呼叫原來的函式

function fn1() {
    fn2();
}

function fn2() {
    fn1();
}

比較: 遞迴 vs. 迴圈

  1. 遞迴執行效率較迴圈慢,因為需要進行函式呼叫
  2. 若在求解時需要使用到堆疊特性的資料結構時,使用遞迴的話,程式碼會比較簡潔

常見的遞迴應用問題:

  1. 最大公因數
  2. Fibonacci 數列
  3. 河內塔問題

在了解遞迴後,我們也要來實作一個可以應用到遞迴的問題。

判斷字串是否為回文

所謂的回文就是一個字串從左邊讀到右邊結果和從右邊讀到左邊的內容都一樣,這樣就是回文。
ex:
levelRace carDo geese see God?
因此問題就是: 給定一個字串,然後判斷此字串是否為回文,若是回文就回傳 true,不是就回傳 false

了解問題後就來實作吧!

我們可以把思考邏輯寫下來:

  1. 要判斷回文的話,我們就要將字串的第一個字元和最後一個字元作判斷是否一樣,第二個字元和倒數第二個字元作判斷...以此類推,在作判斷時要記得忽略非英文字的字元。
  2. 就算同個字母,但大小寫不同,依舊可判定為回文。

思考完畢,先建立一個判斷函式並完成部分內容:

  1. 共有三個參數,一個記錄字串,一個記錄前面判斷的字元位置,一個記錄後面判斷的字元位置
  2. 接著設定最後一個字元 end 的值,字串最後一個字元的索引一定是字串的長度減1(第1個字元索引0),因此便完成 end 值設定
  3. 當字串長度為1個或0個字元時,我們可以當作回文,直接回傳true,而當 start 大於等於 end 位置代表所有的字元都已經判斷過
// 設定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{} 的部分:

  1. 先將 start 和 end 都轉為大寫,目的是因為回文無視大小寫,前面讀到後面和後面讀到前面一樣就好。
  2. 接著我們判斷 start 和 end 是否是字母,不是的話就往後/往前移動一個字元,透過遞迴再此呼叫判斷函式
  3. 之後當判斷的兩個字母不相同時,代表肯定不是回文,因此回傳 false
  4. 如果兩個字母相同時,就讓 start 到後一個字元位置,end 到前一個字元位置,重新用遞迴呼叫判斷函式一次
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

這次的介紹到此結束。明天我們將會來介紹樹 Tree 此種資料結構!


上一篇
Day9-使用佇列實作質數篩選
下一篇
Day11-來介紹資料結構-樹(Tree)吧!
系列文
使用JavaScript學習資料結構與演算法30

尚未有邦友留言

立即登入留言