Vòng lặp đệ quy javascript
|
Đệ quy là một khái niệm phức tạp mà một số nhà phát triển JS sẽ tránh nếu họ có thể (và họ có thể làm được) - nhưng nó có thể là một mẫu siêu hữu ích, đặc biệt là khi viết các hàm tiện ích hiệu năng. Đó là một chủ đề thường được giới thiệu với các nhà phát triển như thể họ chỉ cần “hiểu”… đó có thể là lý do tại sao một số nhà phát triển chỉ nhìn chằm chằm vào nó trong vài phút và tiếp tục. Hãy loại bỏ… Show Đệ quy là kẻ thù không đội trời chung của mọi nhà phát triển, chỉ có người bạn của nó, các biểu thức chính quy mới sánh được về sức mạnh Đệ quy có thể khó hiểu vì một vài lý do. Đầu tiên bạn phải nắm được khái niệm hàm gọi chính nó. Thứ hai, bạn phải hiểu sự khác biệt giữa trường hợp cơ sở và trường hợp đệ quy, nếu không, bạn có thể thấy mình bị mắc kẹt trong một vòng lặp vô hạn cho đến khi bạn gây ra tràn ngăn xếp Nếu bạn có thể nắm vững hai khái niệm đó, đệ quy không đáng sợ hay phức tạp như bạn nghĩ. Mã đệ quy thường viết ngắn hơn và (trong một số trường hợp) dễ đọc hơn Hãy cùng nhau xem qua năm ví dụ mã. Trước tiên, chúng tôi sẽ giải quyết từng vấn đề bằng cách sử dụng vòng lặp, sau đó chúng tôi sẽ giải quyết vấn đề đó bằng cách sử dụng đệ quy. Cách tiếp cận nào tốt hơn? Ví dụ 1. yếu tốViết hàm tính giai thừa cho số nguyên dương. Giai thừa được viết như thế này. 5! = 5 * 4 * 3 * 2 * 1 = 1208. Và công thức cho một giai thừa trông như thế nàyn! = n * (n - 1) * (n - 2) * .. * 1Vì vậy, 5! = 5 * 4 * 3 * 2 * 1 = 1208 sẽ là5! = 5 * 4 * 3 * 2 * 1 = 120Làm thế nào chúng ta có thể viết một chức năng cho điều này? . Chúng ta có thể tạo một biến cho 5! = 5 * 4 * 3 * 2 * 1 = 1201 của mình và sau đó nhân nó với 5! = 5 * 4 * 3 * 2 * 1 = 1200 trong một vòng lặp, giảm 5! = 5 * 4 * 3 * 2 * 1 = 1200 đi 1 mỗi lần. Mã trông như thế nàyLưu ý rằng chúng tôi cũng đã xử lý các đầu vào xấu nhỏ hơn 0 và chúng tôi đã đơn giản hóa các trường hợp 0 và 1 vì 5! = 5 * 4 * 3 * 2 * 1 = 1202 và 5! = 5 * 4 * 3 * 2 * 1 = 1203 đều bằng 1Vì vậy, đó là một giải pháp sử dụng một vòng lặp. Nếu chúng ta muốn viết hàm này theo cách đệ quy thì sao? Ái chà. Điều đó ngắn hơn nhiều. Lưu ý rằng ở dòng cuối cùng, chúng tôi trả về 5! = 5 * 4 * 3 * 2 * 1 = 1200 nhân với kết quả của việc gọi lại hàm 5! = 5 * 4 * 3 * 2 * 1 = 1205 tương tự với đối số là 5! = 5 * 4 * 3 * 2 * 1 = 1206. Đây là trường hợp đệ quyNếu chúng ta chỉ gọi hàm của mình theo cách đệ quy, chúng ta sẽ kết thúc trong một vòng lặp vô hạn, vì vậy chúng ta cần một số cách để thoát ra. Đó là lý do tại sao chúng ta có điều kiện xử lý khi 5! = 5 * 4 * 3 * 2 * 1 = 1207. Khi chúng tôi đạt đến điểm đó, chúng tôi ngừng gọi đệ quy hàm 5! = 5 * 4 * 3 * 2 * 1 = 1205 của mình. Đây là trường hợp cơ bảnSẵn sàng cho một ví dụ khác? Ví dụ #2. Quyền lựcHãy thử một ví dụ tương tự. Lần này, hãy thực hiện hàm lũy thừa, tính toán kết quả của một số cơ số được nâng lên thành số mũ. Vì vậy, ví dụ, 5! = 5 * 4 * 3 * 2 * 1 = 1209 là hai lũy thừa của ba, hoặc 5! = 5 * 4 * 3 * 2 * 1 = 12020, là 8Trong JavaScript, có một số cách để thực hiện các hàm lũy thừa một cách tự nhiên, chẳng hạn như bằng cách gọi 5! = 5 * 4 * 3 * 2 * 1 = 12021 hoặc sử dụng cú pháp lũy thừa như 5! = 5 * 4 * 3 * 2 * 1 = 12022. Bây giờ, hãy giả vờ như những tiện ích đó không tồn tại. Làm thế nào chúng ta có thể tự viết chức năng này?Sử dụng một 5! = 5 * 4 * 3 * 2 * 1 = 1200, chúng ta có thể viết một hàm giống như thế nàyLưu ý rằng chúng ta sẽ bỏ qua số mũ âm cho ví dụ này, mặc dù việc có số mũ âm trong đời thực là hoàn toàn hợp lệ. Chúng tôi cũng sẽ xử lý trường hợp số mũ bằng 0 vì bất kỳ số nào tăng lên 0 luôn là 1 ( 5! = 5 * 4 * 3 * 2 * 1 = 12024)Giống như chúng tôi đã làm cho ví dụ giai thừa của mình, chúng tôi đã bắt đầu với một 5! = 5 * 4 * 3 * 2 * 1 = 1201 ban đầu của 1. Sau đó, chúng tôi nhân 5! = 5 * 4 * 3 * 2 * 1 = 1201 với 5! = 5 * 4 * 3 * 2 * 1 = 1200 trong một vòng lặp khi chúng tôi giảm 5! = 5 * 4 * 3 * 2 * 1 = 12028 cho đến khi đạt 0Bây giờ, giải pháp đệ quy sẽ như thế nào? Wow, nó lại ngắn hơn nhiều. Ở dưới cùng, chúng tôi có trường hợp đệ quy trong đó chúng tôi nhân 5! = 5 * 4 * 3 * 2 * 1 = 1200 với kết quả của việc gọi hàm 5! = 5 * 4 * 3 * 2 * 1 = 12090 của chúng tôi với 5! = 5 * 4 * 3 * 2 * 1 = 1200 và một số giảm dần 5! = 5 * 4 * 3 * 2 * 1 = 12092Trên đó, chúng tôi có trường hợp cơ sở trong đó chúng tôi trả về một nếu 5! = 5 * 4 * 3 * 2 * 1 = 12028 bằng 0. Bằng cách đó, chúng ta có thể thoát khỏi việc gọi vô hạn hàm 5! = 5 * 4 * 3 * 2 * 1 = 12090 của mìnhMột chú thích thú vị là chúng ta không phải theo dõi biến 5! = 5 * 4 * 3 * 2 * 1 = 1201 trong cả hai giải pháp đệ quy của mình. Ngăn xếp cuộc gọi làm điều đó cho chúng tôiSẵn sàng để di chuyển? Ví dụ #3. Tính tổng các số trong một mảngHãy viết một hàm tính tổng tất cả các số trong một mảng. Trong JavaScript, phương thức 5! = 5 * 4 * 3 * 2 * 1 = 12096 cung cấp một công cụ đơn giản để rút gọn một mảng thành một tổng như thế này5! = 5 * 4 * 3 * 2 * 1 = 1202Tạm thời, hãy coi như 5! = 5 * 4 * 3 * 2 * 1 = 12096 không tồn tại. Làm thế nào chúng ta có thể viết chức năng của riêng mình? . Mã trông như thế nàyNgắn gọn và đơn giản. Và nếu chúng ta muốn làm điều này một cách đệ quy thì sao? Mỗi lần chúng ta thêm số đầu tiên vào kết quả gọi hàm 5! = 5 * 4 * 3 * 2 * 1 = 12099 trên phần còn lại của mảng, ngoại trừ số đầu tiênBây giờ đây có phải là cách tốt hơn so với sử dụng 5! = 5 * 4 * 3 * 2 * 1 = 12098 không? . Bạn nghĩ sao?Trong khi chờ đợi, hãy xem xét một ví dụ khác Ví dụ #4. Tìm số lớn nhất trong một mảngHãy viết một hàm nhận vào một mảng các số và trả về số lớn nhất. Trong JavaScript, chúng ta có thể sử dụng hàm tiện ích 5! = 5 * 4 * 3 * 2 * 1 = 12001 như thế này5! = 5 * 4 * 3 * 2 * 1 = 1209Nhưng để tranh luận, hãy giả sử rằng chúng tôi không có sẵn chức năng này. Làm thế nào chúng ta có thể tự viết nó? Chúng tôi bắt đầu bằng cách giả sử rằng số đầu tiên trong mảng của chúng tôi là số lớn nhất. Sau đó, chúng tôi lặp qua mảng, bắt đầu từ phần tử thứ hai và so sánh phần tử hiện tại với số tối đa. Nếu phần tử hiện tại lớn hơn số tối đa, chúng tôi sẽ cập nhật số tối đa với giá trị đó. Khi chúng tôi đã hoàn thành việc lặp qua danh sách của mình, chúng tôi đã tìm thấy số lớn nhất Vì vậy, khá đơn giản. Bây giờ, nếu chúng ta muốn viết điều này một cách đệ quy thì sao? Điều này có cảm thấy khó nắm bắt hơn một chút bằng trực giác không? Nếu mảng chứa 0 phần tử hoặc một phần tử, chúng ta sẽ chỉ trả về phần tử đầu tiên ( 5! = 5 * 4 * 3 * 2 * 1 = 12003 trong trường hợp mảng trống). Đó là trường hợp cơ sở của chúng tôiChúng tôi sẽ so sánh các mảng có chứa hai hoặc nhiều phần tử. Chúng ta sẽ lấy phần tử đầu tiên trong mảng và sau đó so sánh nó với kết quả của việc gọi đệ quy 5! = 5 * 4 * 3 * 2 * 1 = 12004 trên phần còn lại của mảng. Sau đó, chúng tôi sẽ trả lại bất kỳ số nào lớn hơnVẫn chưa rõ ràng? Hãy xem một ví dụ về cách gọi này và hãy thực hiện các bước mỗi lần. Hãy tưởng tượng chúng ta gọi hàm với đối số này 5! = 5 * 4 * 3 * 2 * 1 = 1200Khi hàm tự gọi đệ quy, các hàm chưa được giải quyết sẽ được đẩy lên ngăn xếp cuộc gọi. Khi chúng ta đạt đến trường hợp cơ sở của một mảng chỉ có một phần tử, các hàm bắt đầu giải quyết. Vì vậy, đây là kết quả so sánh của chúng ta trông như thế nào 5! = 5 * 4 * 3 * 2 * 1 = 1206Vì vậy, về mặt khái niệm, chúng ta đang đi ngược qua mảng, bắt đầu với hai số cuối. Ta so sánh hai số đó và giữ số lớn nhất. Sau đó, chúng tôi di chuyển sang trái một phần tử và so sánh phần tử đó với số tối đa hiện tại của chúng tôi Chúng tôi tiếp tục di chuyển sang trái cho đến khi đến đầu mảng, tại thời điểm đó, chúng tôi đã so sánh tất cả các số của mình và tìm thấy số lớn nhất Ví dụ đệ quy này có tốt hơn không? . Mức độ phức tạp về nhận thức của việc nắm bắt cách thức hoạt động của hàm đệ quy này cao hơn nỗ lực cần thiết để hiểu hàm được triển khai bằng một vòng lặp Hàm đệ quy giống như một giải pháp “thông minh” nhưng không phải là một giải pháp “rõ ràng” Hãy làm một ví dụ nữa trước khi chúng ta kết thúc Ví dụ #5. Tìm một chiếc chìa khóa ẩn bên trong những chiếc hộp bên trong những chiếc hộpĐây sẽ là ví dụ phức tạp nhất của chúng tôi, nhưng nó là một trường hợp sử dụng hoàn hảo cho đệ quy. Hãy tưởng tượng rằng bạn có một hộp. Hộp này có thể chứa nhiều hộp khác, hộp khác, v.v. Một hộp cũng có thể trống. Và cuối cùng, chiếc hộp mà chúng tôi đang tìm kiếm có chứa một chiếc chìa khóa Vì vậy, hãy tưởng tượng rằng
Đầu của bạn có đau chưa? Làm thế nào chúng ta có thể viết một chức năng tìm kiếm qua các hộp cho đến khi tìm thấy chìa khóa? Chúng ta có thể viết hàm này bằng cách sử dụng một 5! = 5 * 4 * 3 * 2 * 1 = 1200 như thế nàyChúng tôi bắt đầu với một đống trống (một mảng mà chúng tôi có thể sử dụng làm cấu trúc dữ liệu ngăn xếp) và sau đó thêm hộp đầu tiên của chúng tôi vào đống Sau đó, trong khi đống đó không trống, chúng tôi lấy một cái hộp từ đống đó và nhìn vào bên trong nó Mỗi mục chúng tôi tìm thấy trong hộp có thể là chìa khóa (yay, chúng tôi đã tìm thấy nó. ) hoặc hộp khác (tuyệt vời…). Nếu chúng tôi tìm thấy một chìa khóa, thì chúng tôi đã hoàn thành. Nếu chúng tôi tìm thấy một hộp, thì chúng tôi sẽ thêm hộp đó vào đống của mình Chúng tôi lặp lại vòng lặp của mình cho đến khi hết hộp hoặc cho đến khi tìm thấy chìa khóa Bây giờ, nếu chúng ta muốn tìm một giải pháp đệ quy cho vấn đề này thì sao? Lưu ý sự khác biệt giữa giải pháp đệ quy và giải pháp vòng lặp của chúng tôi. Trong giải pháp đệ quy, chúng tôi không theo dõi đống. Chúng tôi chỉ cần xem qua hộp đầu tiên và sau đó, nếu chúng tôi tìm thấy nhiều hộp hơn, chúng tôi sẽ gọi đệ quy hàm 5! = 5 * 4 * 3 * 2 * 1 = 12006 của mình trên hộp đó. Ngăn xếp cuộc gọi một lần nữa theo dõi trạng thái của chúng tôi cho chúng tôiSự kết luậnVì vậy, cái nào tốt hơn. vòng lặp hoặc đệ quy? . Thường không có sự khác biệt đáng kể về hiệu suất giữa các vòng lặp và đệ quy và ký hiệu Big O cũng giống nhau, vì cùng một số thao tác được thực hiện trong mỗi trường hợp Điều thực sự mà bạn đang tối ưu hóa là khả năng đọc. Bạn có dễ hiểu giải pháp đệ quy hoặc giải pháp vòng lặp hơn không? Mã được đọc gấp 10 lần so với viết, vì vậy hãy tối ưu hóa để dễ đọc Cảm ơn vì đã đọc. Nếu bạn muốn xem lại các ví dụ này và xem các trường hợp thử nghiệm, bạn có thể tìm thấy tất cả các chức năng mà chúng ta đã thảo luận trong repo GitHub này Vòng lặp đệ quy là gì?Một vòng lặp đệ quy là một loại cấu trúc vòng lặp đặc biệt trong đó một thực thể cụ thể cố gắng gọi chính nó từ bên trong mã vòng lặp của nó . Do đó, thực thể tiếp tục gọi chính nó cho đến khi một điều kiện hoặc sự cố cụ thể được chỉ định.
Đệ quy có tốt trong JavaScript không?Tuy nhiên, đệ quy không phải lúc nào cũng là một ý tưởng hay khi nó dẫn đến một thuật toán tốn nhiều bộ nhớ và tính toán , đặc biệt là trong các ngôn ngữ .
Chức năng đệ quy trong JavaScript với ví dụ là gì?Một hàm là đệ quy nếu nó gọi chính nó và đạt đến điều kiện dừng . Trong ví dụ sau, testcount() là một hàm gọi chính nó. Chúng tôi sử dụng biến x làm dữ liệu, tăng dần theo 1 ( x + 1 ) mỗi lần chúng tôi lặp lại. Đệ quy kết thúc khi biến x bằng 11 ( x == 11 ).
Một phương pháp đệ quy có thể có một vòng lặp?Bạn chắc chắn có thể sử dụng vòng lặp trong hàm đệ quy . Điều khiến một hàm trở nên đệ quy chỉ là thực tế là hàm đó tự gọi chính nó tại một số điểm trong đường dẫn thực thi của nó. Tuy nhiên, bạn nên có một số điều kiện để ngăn các cuộc gọi đệ quy vô hạn mà chức năng của bạn không thể trả về. |
