HomeLập trìnhJavaScriptĐệ quy trong...

Đệ quy trong JavaScript


bởi Kevin Enni

Tôi sẽ giải quyết vấn đề này ngay từ đầu, bởi vì mọi người sẽ thực sự tức giận nếu không:

Hãy coi bài đăng này như một loạt các bài tập học tập. Những ví dụ này được thiết kế để khiến bạn phải suy nghĩ — và, nếu tôi làm đúng, có thể mở rộng hiểu biết của bạn về lập trình hàm một chút.

Này, dawg. Tôi nghe nói bạn thích đệ quy, vì vậy tôi đã đặt câu “Này, dawg. Tôi nghe nói bạn thích đệ quy, vì vậy tôi đặt câu “Này, dawg…

Được định nghĩa một cách lỏng lẻo, đệ quy là quá trình xử lý một vấn đề lớn và chia nhỏ nó thành nhiều trường hợp nhỏ hơn của cùng một vấn đề.

Đưa vào thực tế, điều đó thường có nghĩa là viết một hàm gọi chính nó. Có lẽ ví dụ cổ điển nhất của khái niệm này là yếu tố chức năng.

Bạn có thể nhớ từ lớp toán rằng giai thừa của một số N là tích của tất cả các số nguyên dương nhỏ hơn hoặc bằng N. Nói cách khác, giai thừa của 55x4x3x2x1. Ký hiệu toán học cho điều này là 5!.

Một điều thú vị mà bạn có thể nhận thấy về mẫu đó: 5! thực ra chỉ là 5 x 4!. Và 4! Chỉ là 4 x 3!. Cứ tiếp tục như vậy cho đến khi bạn xuống đến 1.

Đọc thêm  Thuộc tính trong javascript là gì? - JavaScript

Đây là cách chúng tôi viết nó trong JavaScript:

Nếu điều này có vẻ khó hiểu, tôi khuyến khích bạn xem qua mã trong đầu bằng cách sử dụng ví dụ về giai thừa( 3 ).

Đây là một chút trợ giúp, trong trường hợp bạn cần:

  1. giai thừa( 3 ) 3 x giai thừa( 2 ).
  2. giai thừa( 2 )2 x giai thừa( 1 ).
  3. giai thừa( 1 ) đáp ứng của chúng tôi nếu điều kiện, vì vậy nó chỉ là 1.

Vì vậy, điều đang thực sự xảy ra ở đây là bạn đang kết thúc ngăn xếp cuộc gọi, chuyển xuống 1, và sau đó giải phóng ngăn xếp. Khi bạn giải phóng ngăn xếp cuộc gọi, bạn nhân từng kết quả. 1x2x36và đó là giá trị trả về của bạn.

Đảo ngược một chuỗi

Một trong những đồng nghiệp của tôi gần đây đã nói với tôi về một câu hỏi trên bảng trắng mà anh ấy đã được hỏi trong một cuộc phỏng vấn và tôi nghĩ đó là một vấn đề thú vị.

Viết một hàm chấp nhận một chuỗi a đảo ngược nó. đệ quy.

Nếu bạn thuộc tuýp người đầy tham vọng, tôi khuyên bạn nên dành vài phút và cố gắng tự mình giải quyết vấn đề này. Hãy ghi nhớ nguyên tắc cốt lõi của đệ quy, đó là lấy một vấn đề lớn và chia nó thành các trường hợp nhỏ hơn của chính nó.

Nếu bạn gặp khó khăn (hoặc bạn quyết định không có tham vọng type), đây là giải pháp của tôi:

Đọc thêm  Sự kiện trình duyệt được giải thích bằng tiếng Anh đơn giản

Một lần nữa, tôi sẽ đưa ra một ví dụ hướng dẫn nhanh trong trường hợp bạn gặp khó khăn. chúng tôi sẽ sử dụng đảo ngược (‘thanh’) như một điểm khởi đầu.

  1. đảo ngược (‘thanh’)đảo ngược (‘ar’) + ‘b’
  2. đảo ngược (‘ar’)đảo ngược (‘r’) + ‘a’
  3. đảo ngược (‘r’) đáp ứng của chúng tôi nếu điều kiện, vì vậy nó chỉ là ‘r’

Khi ngăn xếp cuộc gọi thư giãn, chúng tôi kết thúc với ‘r’ + ‘a’ + ‘b’.

Viết một hàm bản đồ đệ quy

Đối với ví dụ cuối cùng của chúng tôi, chúng tôi sẽ viết một bản đồ() chức năng. Chúng tôi muốn có thể sử dụng nó như thế này:

Một lần nữa, tôi muốn mạnh mẽ khuyến khích bạn dành một vài phút và tự mình thử cái này. Dưới đây là một vài gợi ý và nhắc nhở:

  1. bản đồ() phải luôn trả lại một Mới mảng.
  2. Chia vấn đề thành các phần nhỏ hơn.
  3. Nhớ cái gì đó đảo ngược() ví dụ.

Ồ tốt. Bạn đã quay lại. Làm thế nào mà nó đi?

j/k, đây là một blog và tôi không thể nghe thấy bạn. cười lớn.

Dù sao, đây là cách tôi đã làm:

Vì vậy, hãy xem qua điều này bằng cách sử dụng ví dụ tôi đã đưa ra trước đó:

  1. Cuộc gọi bản đồ() sử dụng mảng [ ‘a’, ‘b’, ‘c’ ]
  2. Tạo một Mới mảng chứa kết quả gọi fn(‘a’)
  3. Trở lại [ ‘A’ ].concat(bản đồ([ ‘b’, ‘c’ ]) )
  4. Lặp lại các bước từ 1 đến 3 với [ ‘b’, ‘c’ ]
  5. Lặp lại các bước từ 1 đến 3 cho [ ‘c’ ]
  6. Cuối cùng, chúng tôi gọi bản đồ() với một mảng trống, kết thúc đệ quy.
Đọc thêm  Cách sao chép một mảng trong JavaScript

GHI CHÚ:
Bạn không bao giờ nên làm điều này trong một ứng dụng thực tế. Bạn sẽ thổi bay ngăn xếp trên các mảng lớn và quan trọng hơn, bạn tạo ra một to lớn lượng rác bằng cách khởi tạo rất nhiều đối tượng mới. Sử dụng Mảng#bản đồ trong mã sản xuất.

Gói (lại

Hy vọng rằng tôi đã làm một công việc tốt trong việc giải thích những thứ này. Nếu bạn vẫn đang gặp khó khăn một chút để giải quyết vấn đề đệ quy, thì lời khuyên tốt nhất mà tôi có thể đưa ra là bắt đầu với các ví dụ nhỏ và theo dõi trong đầu ngăn xếp cuộc gọi. Hãy thử một cái gì đó như đảo ngược (‘abc’) và đi qua nó, từng bước một. Cuối cùng, nó sẽ nhấp.

— –

theo tôi trên Twitter hoặc Phương tiện để có thêm bài viết. Tôi đang cố gắng viết mỗi ngày một lần trong 30 ngày tới.

Và nếu bạn đang ở khu vực Boston và muốn cùng tôi giải quyết những vấn đề điên rồ, thú vị và hóc búa tại Starry, hãy gửi email cho tôi. Tôi đang tuyển dụng.





Zik.vn – Biên dịch & Biên soạn Lại

spot_img

Create a website from scratch

Just drag and drop elements in a page to get started with Newspaper Theme.

Buy Now ⟶

Bài viết liên quang

DMCA.com Protection Status