Every core concept I need to know as a developer - Computer science

WIFI

不同Wi-Fi等級傳輸的速度不同，以最新的Wi-Fi 6為例，除了提供更快的傳輸速度之外，還能增加訊號穩定度、減少訊號干擾、一次連線多個存取點，讓你享受不延遲的8K影片，快速下載與上傳大檔案，大幅提升網路使用體驗。以下提供無線網路標準的比較表作為參考：

What is Li-Fi: Link

Recursive Problem - GCD and LCM

Let's break this down:

1. GCD (Greatest Common Divisor)

   We'll use the Euclidean algorithm to compute the GCD, as it's a classic example of recursion. Given two integers a and b, where a > b, subtract b from a. The difference replaces a. The process is repeated until a equals b. That common value then becomes the GCD of the original a and b.

   A recursive approach to the Euclidean algorithm involves using the modulo % operation:

   function gcd(a, b) {
       if (b === 0) {
           return a;
       }
       return gcd(b, a % b);
   }
   
   console.log(gcd(48, 18)); // 6
   

2. LCM (Least Common Multiple)

   The least common multiple of two integers a and b can be computed using the formula:

   lcm(a, b) = |a * b| / gcd(a, b)

   Since we've already got a recursive function to find the GCD, finding the LCM becomes straightforward:

   function lcm(a, b) {
       return Math.abs(a * b) / gcd(a, b);
   }
   
   console.log(lcm(15, 10)); // 30
   

Given the recursive nature of the GCD function, the LCM function also indirectly becomes recursive.

Recursive Problem - Some simple examples

Recursion can sometimes be applied in scenarios where it's not the most intuitive approach. Here are a few more examples of functions that can be implemented recursively:

1. Factorial: Factorial of a non-negative integer n is the product of all positive integers less than or equal to n.

   function factorial(n) {
       if (n <= 1) return 1;
       return n * factorial(n - 1);
   }
   
   console.log(factorial(5));  // Outputs: 120
   

2. Towers of Hanoi: A classic problem involving moving discs between three pegs.

   function towersOfHanoi(n, source, auxiliary, target) {
       if (n === 1) {
           console.log(`Move disc 1 from ${source} to ${target}`);
           return;
       }
       towersOfHanoi(n - 1, source, target, auxiliary);
       console.log(`Move disc ${n} from ${source} to ${target}`);
       towersOfHanoi(n - 1, auxiliary, source, target);
   }
   
   towersOfHanoi(3, 'A', 'B', 'C');
   

3. Sum of Array Elements: Find the sum of all elements in an array.

   function sumArray(arr, n) {
       if (n <= 0) return 0;
       return sumArray(arr, n - 1) + arr[n - 1];
   }
   
   console.log(sumArray([1, 2, 3, 4, 5], 5));  // Outputs: 15
   

4. Binary Search: Recursively find a target value within a sorted array.

   function binarySearch(arr, x, low = 0, high = arr.length - 1) {
       if (low > high) return -1;
   
       let mid = Math.floor((low + high) / 2);
   
       if (arr[mid] === x) return mid;
   
       if (arr[mid] < x) {
           return binarySearch(arr, x, mid + 1, high);
       }
   
       return binarySearch(arr, x, low, mid - 1);
   }
   
   console.log(binarySearch([1, 2, 3, 4, 5], 4));  // Outputs: 3
   

5. Reverse a String: Recursively reverse a given string.

   function reverseString(str) {
       if (str === "") return str;
       return reverseString(str.substr(1)) + str[0];
   }
   
   console.log(reverseString("hello"));  // Outputs: "olleh"
   

6. Flattening Arrays

   Flattening arrays might not seem like a natural fit for recursion, but it works quite well when dealing with arrays that might contain other arrays.

   function flatten(arr) {
       if (arr.length === 0) return [];
       if (Array.isArray(arr[0])) {
           return flatten(arr[0]).concat(flatten(arr.slice(1)));
       } else {
           return [arr[0]].concat(flatten(arr.slice(1)));
       }
   }
   
   console.log(flatten([1, [2, 3], 4, [5, [6, 7]]])); // [1, 2, 3, 4, 5, 6, 7]
   

7. Counting ways to climb stairs

   Imagine you're climbing a staircase and at each step you can either take a single step or jump two steps. The problem of counting the number of unique ways to reach the top can be tackled recursively, even though it may not be the first solution that comes to mind.

   function countWays(n) {
       if (n <= 1) return 1;
       return countWays(n - 1) + countWays(n - 2);
   }
   
   console.log(countWays(5));  // 8
   

8. Towers of Hanoi

   The Towers of Hanoi is a classic recursive problem, but for those unfamiliar with it, the recursive solution can seem non-intuitive.

   function hanoi(n, source, target, auxiliary) {
       if (n > 0) {
           hanoi(n - 1, source, auxiliary, target);
           console.log(`Move disk ${n} from ${source} to ${target}`);
           hanoi(n - 1, auxiliary, target, source);
       }
   }
   
   hanoi(3, 'A', 'C', 'B');
   

9. String Permutations

   Generating all permutations of a string can be tackled recursively. For every character in the string, we can swap it with the first character and recursively generate permutations for the remainder of the string.

   生成字串的所有排列都可以遞迴處理。 對於字串中的每個字元，我們可以將其與第一個字元交換，併為字串的其餘部分遞迴生成排列。

   This function, permute, is designed to generate all possible permutations of a given string str.

   Let's break down the function step by step:

   1. Base Parameters:

      • str: The string of which we want to find the permutations.
      • prefix: An optional parameter that helps the function keep track of the characters chosen so far. Initially, it's an empty string.

   2. Base Case:

      • If the length of str is 0, this means we've formed a permutation stored in the prefix and we can print or push it to our result.

   3. Recursive Case:

      • For every character in the string str, the function does the following:
        • Takes the character out from str to form a new string rem. This is achieved by concatenating the slice of the string before the character and the slice of the string after the character.
        • Calls itself (recursively) with the new string rem and updates the prefix with the character that's taken out.

   To better understand, consider the string "ABC":

   • For i = 0: the function chooses "A", and rem becomes "BC". The function is then called with "BC" and "A" as the prefix.

     • Within this call, the function chooses "B" from "BC", and rem becomes "C". The function is then called with "C" and "AB" as the prefix.
       • This ultimately leads to the permutation "ABC".

   • For i = 1: the function chooses "B", and rem becomes "AC". The process continues like the previous step, leading to the permutation "BAC".

   • For i = 2: the function chooses "C", and rem becomes "AB". This leads to the permutation "CAB".

   The function repeats these steps for every character in the string until all permutations are found.

   In the code you provided, instead of collecting the results in the result array, the permutations are being printed out directly using console.log(prefix). If you uncomment the lines related to result, you can collect the permutations in an array and return them.

   let r = [];
   function permute(str, prefix = "") {
     if (str.length === 0) {
       r.push(prefix)
       console.log(prefix)
     } else {
       for (let i = 0; i < str.length; i++) {
         let rem = str.slice(0, i) + str.slice(i + 1);
         permute(rem, prefix + str[i]);
       }
     }
   }
   
   permute("abc");
   console.log(r) // [ 'abc', 'acb', 'bac', 'bca', 'cab', 'cba' ]
   

All these examples showcase that even if recursion may not seem like the most obvious solution, it can provide elegant solutions to problems. However, it's essential to note that recursion can have its downsides, such as possible stack overflows and sometimes inefficiencies, especially when not combined with techniques like memoization.

These are just a few of the countless problems that can be solved using recursion. Some are more intuitive than others, but recursion provides a powerful tool for simplifying complex problems.

Recursive Problem - Towers of Hanoi

The "Towers of Hanoi" (often simply referred to as "Hanoi") is a classic mathematical game or puzzle. Here's a more detailed breakdown:

You have three rods and n discs of different sizes. The discs are initially stacked on one rod in order of size, with the largest disc at the bottom and the smallest at the top. The objective of the puzzle is to move the entire stack of discs to another rod, obeying the following rules:

1. Only one disc can be moved at a time.
2. A disc can only be placed on top of a larger disc or an empty rod.
3. A disc can be moved from the top of a stack on one rod to the top of a stack on another rod (or to an empty rod).

The recursive approach to solving the Towers of Hanoi problem can be broken down as follows:

1. Move the top n-1 discs from the source rod to an auxiliary rod, using the target rod as a temporary holding place.
2. Move the nth (largest) disc from the source rod to the target rod.
3. Move the n-1 discs from the auxiliary rod to the target rod, using the source rod as a temporary holding place.

Here's the algorithm for the above:

function towersOfHanoi(n, source, auxiliary, target) {
    // Base case: if only one disc, move it from source to target
    if (n === 1) {
        console.log(`Move disc 1 from ${source} to ${target}`);
        return;
    }
    // Recursively move the top n-1 discs from source to auxiliary
    towersOfHanoi(n - 1, source, target, auxiliary);
    // Move the nth disc from source to target
    console.log(`Move disc ${n} from ${source} to ${target}`);
    // Recursively move the n-1 discs from auxiliary to target
    towersOfHanoi(n - 1, auxiliary, source, target);
}

The Towers of Hanoi puzzle has been widely studied in mathematics, particularly in algorithms and recursion. It's a popular problem because:

• It's a clear example of how a seemingly complex problem can be broken down into simpler sub-problems using recursion.
• It showcases the power and elegance of recursive solutions.
• The puzzle has a deep mathematical significance, with relations to binary numbers and Sierpinski triangles.

There's a legend associated with the Towers of Hanoi puzzle. The legend says that in an ancient temple, monks are attempting to solve a 64-disc version of this puzzle. According to the legend, once they complete the puzzle, the world will end. Fortunately for us, even at a rate of one move per second, it would take more than 500 billion years to solve the 64-disc version!

Recursive Problem - fibonacci

Here's a simple Fibonacci sequence generator using TypeScript:

function fibonacci(n: number): number {
    if (n <= 1) return n;
  
    return fibonacci(n - 1) + fibonacci(n - 2);
}

console.log(fibonacci(10));  // Outputs: 55

This is a basic recursive implementation. However, this isn't the most efficient way to compute the Fibonacci sequence, especially for larger numbers. A more efficient approach would be to use iteration or memoization.

Here's a version using iteration:

function fibonacciIterative(n: number): number {
    if (n <= 1) return n;
    
    let previous = 0;
    let current = 1;
    
    for (let i = 2; i <= n; i++) {
        const next = previous + current;
        previous = current;
        current = next;
    }
    
    return current;
}

console.log(fibonacciIterative(10));  // Outputs: 55

And here's a version using memoization:

function fibonacciMemoized(n: number, memo: Map<number, number> = new Map()): number {
    if (n <= 1) return n;
    
    if (memo.has(n)) return memo.get(n)!;

    const value = fibonacciMemoized(n - 1, memo) + fibonacciMemoized(n - 2, memo);
    memo.set(n, value);
    
    return value;
}

console.log(fibonacciMemoized(10));  // Outputs: 55

With TypeScript, we can use its type-checking capabilities to ensure the input to the function is a number, and that the function always returns a number.