Khi nào không sử dụng đệ quy trong Python?

Nếu bạn định chọn một ngôn ngữ để viết các thuật toán đệ quy, thì hãy tránh Python. Tại sao? . Có một số lý do cho việc này. Đầu tiên Python về bản chất là lờ đờ, tôi. e. sẽ mất nhiều thời gian để chạy các thuật toán. Tiếp theo, trình thông dịch Python không thực hiện bất kỳ loại tối ưu hóa đệ quy nào. Do đó, giới hạn đệ quy thường khá thấp. Trên hầu hết các hệ thống, nó được đặt ở 1000. Điều này có nghĩa là khi một hàm đệ quy phải lặp đi lặp lại nhiều lần thì hệ thống sẽ sinh ra lỗi

RecursionError: maximum recursion depth exceeded in comparison

Điều này được thực hiện để tránh tràn ngăn xếp và để tránh các lần truy cập vô hạn. Đẹp. Nhưng không hữu dụng lắm. Tất nhiên chúng ta có thể ghi đè điều này bằng cách sử dụng hàm setrecursionlimit(), hàm này nhận một tham số, giá trị của giới hạn đệ quy mới. Nhưng thành thật mà nói, tốt nhất là sử dụng một ngôn ngữ khác hoàn toàn

import sys
sys.setrecursionlimit(10**6)

Để minh họa việc Python không có khả năng đối phó với đệ quy, chúng tôi sẽ triển khai thuật toán Slowsort đệ quy trong Python và C. Thuật toán này được chọn, không phải vì khả năng tuyệt vời của nó, mà vì thực tế là nó không hiệu quả và sẽ thúc đẩy việc sử dụng tài nguyên đệ quy. Dưới đây là thuật toán được viết bằng Python

def slowsort(A, i, j):
    if i >= j:
        return
    m = int((i+j) / 2)
    slowsort(A, i, m)
    slowsort(A, m+1, j)
    if A[j] < A[m]:
        A[j], A[m] = A[m], A[j]
    slowsort(A, i, j-1)

Đoạn mã sau đó được chạy với đoạn mã sau, đoạn mã này đọc từ một tệp và sắp xếp các số

with open('num25.txt') as file:
    lines = [int(i) for i in file]
a = 0
b = len(lines)-1
slowsort(lines,a,b)

Để sắp xếp chỉ 25 số bằng thuật toán này mất 655 giây trong Python. Thuật toán tương tự được viết bằng C phải mất 0 giây (có thể là nano giây). Trong nhiều khía cạnh nếu bạn đang lập trình bằng Python, có rất ít khả năng bạn sẽ thực sự cần đệ quy

Phần lớn, các khái niệm trong bài viết này được thảo luận trong ngữ cảnh của Python 3, nhưng chúng cũng có thể chuyển sang nhiều ngôn ngữ khác

Trò đùa nổi tiếng của Google có tính năng đệ quy

Cracking the Coding Interview tuyên bố rằng “Tất cả các thuật toán đệ quy có thể [cũng] được triển khai lặp đi lặp lại…” trong phần tiếp cận các vấn đề phỏng vấn kỹ thuật bằng cách sử dụng đệ quy

Giải quyết vấn đề Python lặp đi lặp lại có thể bao gồm sử dụng vòng lặp for hoặc while. Đây là một số công cụ phổ biến nhất được sử dụng để giải quyết vấn đề gia tăng trong bất kỳ ngôn ngữ lập trình nào. Các vòng lặp rất tuyệt vời bởi vì, trong nhiều trường hợp, việc triển khai chúng rất trực quan và dễ hiểu

Tuy nhiên, có những lúc các giải pháp lặp đi lặp lại có thể biến thành cơn ác mộng khó đọc

Cố gắng viết mã phức tạp và được lồng ghép nhiều trên bảng trắng với ánh mắt tò mò của người phỏng vấn đang kiểm tra công việc của bạn có thể là một cách chắc chắn để khiến bạn vấp ngã trong một cuộc phỏng vấn kỹ thuật

Mặc dù việc chuyển đổi từ vòng lặp sang đệ quy không phải lúc nào cũng làm cho mã của bạn tốt hơn, nhưng đây là một công cụ tuyệt vời cần có trong hộp công cụ của bạn

Một thời gian, tôi sợ học đệ quy. Khi biết rằng các vấn đề với giải pháp đệ quy chắc chắn cũng có một giải pháp lặp lại, tôi đã cố gắng giải quyết mọi vấn đề kỹ thuật bằng các vòng lặp

Tuy nhiên, khi các kỹ năng phỏng vấn kỹ thuật của tôi phát triển, tôi đã gặp phải nhiều vấn đề về LeetCode và HackerRank đòi hỏi sự đệ quy với độ phức tạp của chúng. Đã đến lúc mở rộng các công cụ theo ý của tôi

Vòng lặp là gì?

Sơ đồ vòng lặp for và vòng lặp while

Một vòng lặp được sử dụng để thực hiện một khối mã lặp đi lặp lại nhiều lần nếu cần thiết cho chương trình

Đối với các vòng lặp, giống như vòng lặp trong ví dụ trên, lặp qua một chuỗi. Chúng ta thường sử dụng vòng lặp for khi biết mình cần thực thi một khối mã bao nhiêu lần. Trong ví dụ trên, chúng ta chỉ cần thực hiện dòng 2 và 3 cho số lượng tên trong name_list

Chúng tôi cũng có thể cần lặp lại một số lần không xác định hoặc cho đến khi một điều kiện nhất định được đáp ứng. Đây có thể là thời điểm tốt để sử dụng vòng lặp while

Một cách để trả về độ dài của Danh sách liên kết không thể lặp lại có thể liên quan đến việc sử dụng vòng lặp while để duyệt qua tất cả các nút như trong ví dụ trên

OK, vậy đệ quy là gì?

Một sự khác biệt lớn giữa đệ quy và phép lặp là cách chúng kết thúc. Trong khi một vòng lặp thực thi khối mã, mỗi lần kiểm tra xem nó có ở cuối chuỗi hay không, không có kết thúc tuần tự như vậy đối với mã đệ quy

Giống như truyện tranh Winnie the Pooh kinh hoàng ở trên, một hàm đệ quy có thể tồn tại mãi mãi mà không có điều kiện nào để đưa nó ra khỏi tình trạng khốn khổ của nó

Hiển thị trường hợp cơ sở và lệnh gọi đệ quy trong hàm đệ quy trên ví dụ giai thừa. Hình ảnh từ https. //www. trình chiếu. net/alhazmy13/data-structures-part5-recursion

Một hàm đệ quy như hàm trên bao gồm hai phần. cuộc gọi đệ quy và trường hợp cơ sở

Trường hợp cơ sở (hoặc đôi khi là trường hợp cơ sở) là điều kiện kiểm tra xem liệu chúng tôi có nhận được thông tin mà chúng tôi cần từ chức năng của mình hay không. Mọi hàm đệ quy nên có ít nhất một trường hợp cơ sở, mặc dù có thể có nhiều

Trong ví dụ giai thừa ở trên, chúng ta đã kết thúc các cuộc gọi đệ quy cần thiết khi chúng ta đến số 0

Lời gọi đệ quy, như bạn có thể nghi ngờ, là khi hàm gọi chính nó, thêm vào ngăn xếp lời gọi đệ quy

Ngăn xếp là các đối tượng LIFO (Last In First Out), nghĩa là mục cuối cùng được thêm vào đầu ngăn xếp là mục đầu tiên được xóa khỏi ngăn xếp sau này

Khi nào tôi nên sử dụng đệ quy?

Đệ quy được thực hiện để giải quyết các vấn đề có thể được chia thành các vấn đề nhỏ hơn, lặp đi lặp lại. Nó đặc biệt tốt khi làm việc với những thứ có thể có nhiều nhánh và quá phức tạp đối với cách tiếp cận lặp lại

Một ví dụ điển hình về điều này là tìm kiếm thông qua hệ thống tệp. Bạn có thể bắt đầu từ thư mục gốc, sau đó bạn có thể tìm kiếm qua tất cả các tệp và thư mục trong thư mục đó. Sau đó, bạn sẽ vào từng thư mục và tìm kiếm từng thư mục bên trong đó

Đệ quy hoạt động tốt cho loại cấu trúc này vì bạn có thể tìm kiếm nhiều đường dẫn phân nhánh mà không cần phải đưa vào nhiều kiểm tra và điều kiện khác nhau cho mọi khả năng

Đối với những người quen thuộc với cấu trúc dữ liệu, bạn có thể nhận thấy rằng hình ảnh ở trên của hệ thống tệp trông rất giống cấu trúc cây

Cây và đồ thị là một thời điểm khác khi đệ quy là cách tốt nhất và dễ nhất để thực hiện duyệt

Tôi có nên luôn sử dụng đệ quy không?

Đệ quy có vẻ thực sự hữu ích. Có lẽ tôi nên sử dụng nó mọi lúc?

Chà, giống như bất cứ điều gì, đệ quy là tốt nhất với liều lượng. Đệ quy là một công cụ hữu ích, nhưng nó có thể làm tăng mức sử dụng bộ nhớ

Vì vậy, hãy quay lại hình ảnh ngăn xếp cuộc gọi giai thừa từ phía trên. Mỗi khi chúng tôi thêm một cuộc gọi mới vào ngăn xếp, chúng tôi sẽ tăng dung lượng bộ nhớ mà chúng tôi đang sử dụng. Nếu chúng tôi đang phân tích thuật toán bằng ký hiệu Big O, thì chúng tôi có thể lưu ý rằng điều này làm tăng độ phức tạp không gian của chúng tôi

Đôi khi chúng ta có thể muốn trả chi phí này để có được một thuật toán ngắn gọn, hữu ích, chẳng hạn như khi chúng ta đi ngang qua một cái cây. Nhưng có những thời điểm khác khi có thể có những cách tốt hơn, hiệu quả hơn để giải quyết vấn đề này

Đối với nhiều dự án nhỏ, ngăn xếp cuộc gọi sẽ không cản trở bạn lập trình nhiều. Tuy nhiên, khi chương trình của bạn bắt đầu thực hiện nhiều lệnh gọi đệ quy, thì bạn có thể muốn xem xét tác động tiềm ẩn của ngăn xếp lệnh gọi lớn của mình

Ảnh của John-Mark Smith trên Bapt

Một điều khác cần xem xét là việc hiểu và đọc mã của bạn đôi khi có thể dễ thực hiện hơn trong một giải pháp lặp lại

Sử dụng đệ quy là tuyệt vời bởi vì nó loại bỏ nhiều vấn đề phụ gia tăng ra khỏi tầm tay của bạn

Nhưng khi bạn đang cố gắng hiểu đầy đủ các vấn đề phụ mà bạn đang giải quyết và cách chúng được giải quyết, thì có thể đáng để thực hiện một giải pháp lặp đi lặp lại. Nếu đây không phải là một lộ trình khả thi, thì ít nhất hãy lập sơ đồ quy trình đệ quy do mã của bạn thực hiện để đào sâu kiến ​​thức của bạn

Khi nào nên tránh đệ quy?

Tại sao bạn không nên sử dụng đệ quy?