演算法練習-遞迴(recursive)

什麼是遞迴函數(recursive function)?

遞迴函數就是函數呼叫自身的函數。

好吧，我知道這講跟沒講差不多，我們先來看一下簡單的函數，然後寫一個簡單的遞迴函數做個比較。

基本函數

function add(a,b){
  return a+b
}

遞迴函數(以階層函數為例)

function fraction(num){
  if (num===1) return 1
  return num *  fraction(num-1)
} 

我們可以看到在遞迴函數中我們不單是return一個值，而是在回傳時再次呼叫函數。要成功執行遞迴，就需要了解在JS中執行stack時有個核心的觀念:當一個函數A執行時碰到另一個函數B時，會先等待B執行完的回傳結果再回傳A的結果。沒錯~!就是讓不少人頭痛不已的callback的概念。我們再仔細的看一下我們範例中的階層函數(順帶一提，我之前針對這個函數寫過如何利用js簡單的做排列組合的運算:D)

當我執行fraction(3)的時候，整段code是如何運行的呢?

執行過程

1st :回傳 3*fraction(3-1) <===由此進入第二次執行
2nd :回傳 2*fraction(2-1) <===由此進入第三次執行
3rd :回傳 1 

而最終的結果便是將三次執行的結果倒著放回去(剛說過的，後來碰到的函數要先執行)
也就是3 * 2 * 1 = 6囉!

實際範例(Leetcode46- Permutations)

這是個相當有趣的問題，任意給定一unique陣列，試求出所有可能的組合。假設今天給你[1,2,3]，你最終回傳的結果就必須包含[1,2,3]、 [1,3,2]、 [2,1,3]、 [2,3,1]、 [3,1,2]、 [3,2,1]等六種組合的陣列，很明顯用遞迴的方法去解決會相當的合理!

虛擬碼邏輯

1.若陣列長度 = 1，就回傳陣列本身，因為只會有那一種組合
2.每一次抓其中一個元素作為排列的開頭，並將其從陣列中排除，利用剩餘的元素做排列(假設[1,2,3]，第一次便將1拔出來，讓剩下的2,3去做組合，也就是再一次呼叫函數本身)

最終結果

var permute = function(nums,sets=[],answers=[]) {
    if (!nums.length) answers.push([...sets]);

    for (let i=0;i<nums.length;i++){
      const newNums = nums.filter((item,index)=> index !==i)
      sets.push(nums[i])
      permute(newNums,sets,answers)
      sets.pop()
    }
    return answers
}; 

結語

遞迴一直是個較為難以理解的概念，到現在我都無法很直覺的用遞迴解決問題，許多時候我會逼迫自己用遞迴面對一些問題，目前看起來有些許的進步了，演算法也是個大坑，繼續加油吧~!這個解法在效能上不是特別的出色，time complexity 屬於O(n!)的做法，且最大的硬傷在於記憶體的使用，在陣列的操作上用了不少記憶體的空間，應該可以利用slice之類的做法達成一些優化，之後再研究看看!

參考資料

演算法-遞迴函數
Leetcode46-permute影片講解