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 <= 1 ) {    
          return str;  
   }  
      return reverse(string.substr(1)) + string[ 0 ];
}

Ví dụ này sử dụng chuỗi con JavaScript. Phương thức substring() trả về tập hợp con của string giữa chỉ mục này và chỉ mục khác hoặc thông qua phần cuối của chuỗi. Phương thức lấy chỉ mục bắt đầu và chỉ mục kết thúc tùy chọn

str.substring(indexStart[, indexEnd])

Vì trong trường hợp này, nó được áp dụng theo cách đệ quy, nên việc sử dụng chỉ mục kết thúc trong trường hợp này sẽ không hợp lý. Thay vào đó, chúng ta có thể thấy điều này tuân theo một khuôn mẫu rất giống với giai thừa

Logic của chức năng có thể được nghĩ ra như sau

reverseString("mary")return reverse(string.substr(1)) + "m"return (reverse(string.substr(1)) + "a") + "m"return ((reverse(string.substr(1)) + "r") + "a") + "m"return ((("y") + "r") + "a") + "m"

kiểm tra bảng chữ cái

function isPalindrome(string) {      
   if (string.length === 0 || string.length === 1) {        
       return true;    
    }        
   if (string[0] === string[string.length - 1]) {        
     return isPalindrome( string.slice(1, string.length - 1) );     
   }       
  return false;
};

Nói một cách dễ hiểu, nếu chữ cái đầu tiên của một chuỗi bằng với chữ cái cuối cùng, hãy gọi lại hàm, bây giờ với chuỗi có chữ cái đầu tiên bị cắt bớt

Viết ra, logic sẽ trông giống như,

isPalindrome(“hannah”)is string[0] === string[5]? "h" === "h"  trueisPalindrome("anna") is string[0] === string[3]? "a" === "a" true isPalindrome("nn") is string[0] === string[2]? "n" === "n" true

Nhìn chung, các bước quan trọng để suy nghĩ thông qua các hàm đệ quy là ghi nhớ ngăn xếp, chia nhỏ nó thành một trường hợp cơ sở và sau đó tìm ra sự sửa đổi cần thiết đối với đối số được chuyển vào lời gọi đệ quy của hàm

Có nhiều tài nguyên tuyệt vời cho đệ quy, bao gồm các giải thích sâu hơn về ngăn xếp cuộc gọi, trường hợp cơ bản và nhiều vấn đề thực hành như được liên kết bên dưới

Đệ quy trong JavaScript w3schools là gì?

Đệ quy trong mã hóa là gì?

Đệ quy trong JavaScript MDN là gì?

Đệ quy là gì và nó hoạt động như thế nào?