[用JS來寫演算法和了解資料結構] Day12 Algorithm - Recursion 遞迴 - Factorial / Fibonacci numbers

Recursion 遞迴

• 在函式之中呼叫函式自己本身

1. Identify the base case
2. Identify the recursive case
3. Get closer and return when needed. Usually 2 returns.

let counter = 0;
function inception(){
  console.log(counter);
  if(counter > 3){
    return 'done';
  }
  counter++
  return inception();
}

inception();

Factorial 階層

• 5! = 5 * 4 * 3 * 2 * 1

可分解成

• 5! = 5 * 4!
• 5! = 5 * 4 * 3!
• 5! = 5 * 4 * 3 * 2!
• 5! = 5 * 4 * 3 * 2 * 1

// Write two functions that finds the factorial of any number. 
// One should use recursive, the other should just use a for loop

// input 5
// output 120 // 5 * 4 * 3 * 2 * 1

// Recursive 遞迴 O(n)
function findFactorialRecursive(number) {
  if (number === 0) {
    return 0;
  }
  if (number === 1){
    return 1;
  }
  return number * findFactorialRecursive(number - 1);
}

console.log(findFactorialRecursive(5));
console.log(findFactorialRecursive(3));


//Iterative 迭代 0(n)
function findFactorialIterative(number) {
  if (number === 0) {
    return 0;
  }
  let answer = 1;
  for (let i = 2; i <= number; i++) {
    answer *= i;
  }
  return answer;
}

console.log(findFactorialIterative(5));
console.log(findFactorialIterative(3));

Fibonacci numbers 費波那契數列

// Given a number N return the index value of the Fibonacci sequence, 
// where the sequence is:
// 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 ...
// the pattern of the sequence is that each value is the sum of the 2 previous values, that means that for N=5 → 2+3

// For example: 
// input 6
// output 8
// 8 => 5 + 3
//      5 => 3 + 2
//           3 => 2 + 1
//                2 => 1 + 1
//                     1 => 1 + 0


// Recursive 遞迴 O(2^n)
function fibonacciRecursive(n) {
  if(n < 2){
    return n
  }
  return fibonacciRecursive(n - 2) + fibonacciRecursive(n - 1);
}
console.log(fibonacciRecursive(6)); //8


// Iterative 迭代 O(n)
function fibonacciIterative(n){
  let fibonacciArr = [0, 1];
  for(i = 2; i <= n; i++){
    fibonacciArr[i] = fibonacciArr[i - 1] + fibonacciArr[i - 2]
  }
  return fibonacciArr[n];
}
console.log(fibonacciIterative(6)); //8

Reverse String - use Recursion

function reverseStringRecursive(str) {
    if (str === "") {
        return "";
    }
    return reverseStringRecursive(str.slice(1)) + str[0];
}

console.log(reverseStringRecursive("hello"));

為何要用 O(2^n) 的 Recursion？

Pro:

1. make code dry
2. Readability
   Con:
3. Large Stack

使用時機

• Every time you are using a tree or converting something into a tree, consider Recursion.

1. Divided into a number of sub problems that are smaller instances of the same problem. 能夠拆分成更小但類似的問題
2. Each instance of the sub problem is identical in nature. 計算方式雷同
3. The solution of each sub problem can be combined to solve the problem at hand. 拆分的結果能夠組合

• Divide and Conquer (分而治之) using Recursion

學習與參考資料

• 遞迴 Recursion by hannahpun
• Master the Coding Interview: Data Structures + Algorithms