JavaScript đệ quy là gì?

Ở cấp độ cơ bản nhất, sử dụng đệ quy trong lập trình có nghĩa là gọi một hàm bên trong chính nó cho đến khi đạt được một điều kiện nhất định

Trong JavaScript, vì các hàm được truyền theo tham chiếu, nên hàm có thể được truyền cho chính nó dưới dạng một trong các đối số và sau đó được gọi trong phần thân của hàm

Ví dụ cổ điển về hàm đệ quy đang sử dụng giai thừa. Trong toán học, một giai thừa [được viết bằng. ] là tích của một số nguyên [n] và mọi số nguyên dương nhỏ hơn n

Ví dụ: 4. bằng 4 x 3 x 2 x 1, hay 24

Tại sao một hàm đệ quy tốt cho một vấn đề như thế này trong lập trình?

Trong lập trình, giai thừa là một ví dụ hoàn hảo về trường hợp nên sử dụng hàm đệ quy. Tại sao? . — Codecademy, Đệ quy trong JavaScript

Đối với mỗi bước, bạn đang nhân số nguyên với giai thừa của số nguyên dương nhỏ nhất tiếp theo. 4. thực sự giống như 4 x 3. [vì đó là 4 x 3 x 2 x 1]. Do đó, nó giống như 4 x 3 x 2. , và như thế

Vì vậy, sử dụng đệ quy ở đây có ý nghĩa hoàn hảo. Phương pháp đơn giản nhất là viết một cái gì đó như

function factorial[n] {
  if [n === 0] {
    return 1;
  }
  return n * factorial[n - 1];
}

Câu lệnh if là điểm đột phá của chúng ta, nghĩa là kết thúc đệ quy khi chúng ta đáp ứng điều kiện n === 0. Đây được gọi là trường hợp cơ bản

Được rồi, nhưng điều gì sẽ xảy ra nếu chúng ta làm điều gì đó như, giai thừa [-2]. Điều đó sẽ không hiệu quả, vì vậy có lẽ nên cập nhật chức năng này một chút để chúng ta không mãi mãi rơi vào vòng lặp tiêu cực trong một vòng lặp vô tận

function factorial[n] { if [n < 0] {
    return - 1;
  }  if [n === 0] {
    return 1;
  }  return n * factorial[n - 1];
}

Nếu chúng ta viết điều này ra, chính xác thì chuyện gì sẽ xảy ra?

function factorial[4] {
  if [n === 0] {     //4 !==0
    return 1;
  }
  return n * factorial[n - 1];
}//so we get 4 * factorial[3]function factorial[3] {
  if [n === 0] {    //3 !==0
    return 1;
  }
  return n * factorial[n - 1];
}//so we get 4 * [3 * factorial[2]]function factorial[2] {
  if [n === 0] {    //2 !==0
    return 1;
  }
  return n * factorial[n - 1];
}//so we get 4 * [3 * [2 * factorial[1]]]]function factorial[1] {
  if [n === 0] {    //1 !==0
    return 1;
  }
  return n * factorial[n - 1];
}//so we get 4 * [3 * [2 * [1 * factorial[0]]]]]function factorial[0] {
  if [n === 0] {    //0 === 0, so we've hit our break!
    return 1;
  }
  return n * factorial[n - 1];
}// so the end return is 4 * [3 * [2 * [1 * [1]]]]]
// with parentheses used just to illustrate the values that are returned with each call of the function

Hiểu đệ quy bằng cách suy nghĩ về ngăn xếp cuộc gọi

Cách chính xác hơn để hình dung hàm trên không phải là nghĩ về nó theo cách nó được viết 4 * [3 * [2 * [1 * [1]]]]], mà là xem xét cách nhập trước

Mỗi lần lặp lại của đệ quy sẽ thêm vào ngăn xếp cuộc gọi, xây dựng cho đến khi chức năng không được gọi nữa. Sau đó, JavaScript được thực thi. Vì vậy, cách chính xác hơn để viết những gì đang xảy ra sẽ là 1 x 1 x 2 x 3 x 4

Xác định các kịch bản khác để sử dụng đệ quy

Bây giờ rõ ràng rằng các thành phần chính của việc hiểu đệ quy là hàm gọi chính nó và đảo ngược [FIFO] trong ngăn xếp cuộc gọi, chúng ta có thể sử dụng thông tin này để áp dụng đệ quy cho các vấn đề phổ biến khác

Một vấn đề phổ biến trong các cuộc phỏng vấn kỹ thuật là sử dụng đệ quy để đảo ngược chuỗi hoặc thực hiện kiểm tra bảng màu. Đây là những liên quan và xây dựng trên các khái niệm trên

đảo ngược chuỗi

function reverseString[string] {  
   if [ str.length