Khi nào sử dụng đệ quy python

Nói tóm lại, đệ quy không phải là xấu trong Python và thường cần thiết cho các chương trình sẽ thực hiện các thao tác duyệt theo chiều sâu đầu tiên như trình thu thập dữ liệu web hoặc tìm kiếm thư mục. Bài toán số bước nhỏ nhất của Tháp Hà Nội cũng có thể được giải bằng thuật toán đệ quy với mã Python sau

def hanoi(num_disks):
  if n < 1:
    raise ValueError("num_disks must be larger than or equal to 1")
  if num_disks == 1:
    return 1
  return 2 * (hanoi(num_disks - 1)) + 1

Cố gắng tránh đệ quy cho các trường hợp sử dụng tiêu chuẩn này sẽ là một phản mẫu và đi ngược lại các nguyên tắc của python để “ưu tiên đơn giản hơn phức tạp” và “số lượng dễ đọc”. Viết mã không thể đọc được để tránh đệ quy vì bạn nghe nói nó tệ trong Python không có lợi cho các kỹ sư đồng nghiệp trong nhóm của bạn, những người cần cố gắng hiểu bạn đang viết cái quái gì ba tháng sau

Khi nào đệ quy xấu trong Python?

Đệ quy có thể bị coi là xấu trong Python khi có một cách tối ưu hơn để triển khai cùng một thuật toán bằng cách sử dụng phép lặp hoặc trường hợp sử dụng đệ quy có khả năng tạo ra hơn 1000 lệnh gọi hàm trên ngăn xếp lệnh gọi. Điều này là do Python có phí gọi hàm trong đó trình thông dịch thực hiện kiểm tra kiểu động của các đối số hàm được thực hiện trước và sau khi gọi hàm, dẫn đến độ trễ thời gian chạy bổ sung. Python cũng có giới hạn đệ quy mặc định là 1000 lệnh gọi hàm và mặc dù điều này có thể được ghi đè thủ công bằng cách sử dụng mã bên dưới, thực tế là điều này đã được đưa vào ngôn ngữ ngay từ đầu nên là một chỉ số lớn mà nó không được mong muốn theo người bạn Ludwig của chúng tôi

import sys
r_limit = 2500 
sys.setrecursionlimit(r_limit)

Lập trình động để giải cứu các trường hợp sử dụng đệ quy xấu

Trước khi viết đoạn mã trên vào bất kỳ đâu trong bất kỳ chương trình python nào của bạn vì bạn thấy mình đạt đến giới hạn đệ quy; . Ngoài ra, loại kỹ năng giải quyết vấn đề theo thuật toán này áp dụng cho tất cả các ngôn ngữ mã hóa chứ không chỉ Java. Nó cũng thường được kiểm tra trong các câu hỏi viết mã trong cuộc phỏng vấn khi người phỏng vấn tăng mức độ phức tạp của các vấn đề cơ bản của họ

Mặc dù Lập trình động có thể khó để thành thạo, nhưng nó thường tóm gọn trong 4 bước giải quyết vấn đề giống nhau này

1. Xác định các trường hợp cơ sở của bạn
2. Tạo một giải pháp đệ quy
3. Ghi nhớ các cuộc gọi đệ quy
4. Chuyển đổi sang giải pháp lặp lại từ dưới lên

Thí dụ

# Standard recursive algorithm
def Fibonacci(n): 
    if n<0: 
        print("Incorrect input") 
    # First Fibonacci number is 0 
    elif n==0: 
        return 0
    # Second Fibonacci number is 1 
    elif n==1: 
        return 1
    else: 
        # Add recursive calls to the call stack
        # as N gets large the call stack grows exponentially
        # and can easily reach over the 1000 recursion limit
        return Fibonacci(n-1)+Fibonacci(n-2) 

# Solving Standard Fibonacci with dynamic programming
def fibonacci(n):  
    # Memoization array space, can be expanded for more inputs and
    # used as a circular buffer
    dp = [0,1]
    if n < 0: 
        print("Incorrect input") 
    elif n == 0: 
        return dp[0]
    elif n == 1: 
        return dp[1]
    else: 
        # Use a bottom up iterative solution to calculate the fibonaci
        # numbers and return the Nth term we care about
        #
        # However subsequent calls to this function would result
        # in recalculating all the values again. This is a trade off
        # for saving memory space at the expense of CPU usage.
        for i in range(2,n+1): 
            c = dp[0] + dp[1] 
            dp[0] = dp[1]
            dp[1] = c 
        return dp[2] 

Trong khi phát triển các kỹ năng thuật toán của bạn hoặc chuẩn bị cho các cuộc phỏng vấn trên các trang web như Leetcode, bạn sẽ thường gặp phải các vấn đề chỉ có thể giải quyết bằng cách tìm giải pháp lập trình động/ghi nhớ. Đệ trình giải pháp đệ quy tiêu chuẩn sẽ gặp phải “lỗi đệ trình của bạn đã hết thời gian chờ” và bạn sẽ rất buồn khi điều này khiến bạn mất 100 thứ hạng trên điểm số cuộc thi toàn cầu của mình. Và vâng, điều đó đã thực sự xảy ra với tôi

Cách tốt nhất để thực sự quen với việc giải các bài toán đệ quy và động là thực hiện chúng lặp đi lặp lại và thường xuyên. Vì vậy, hãy thoải mái, truy cập google và nhập các câu hỏi mã hóa lập trình động cho tháng tới. “Nhưng Stefan có vẻ như làm quá nhiều việc, tôi chỉ muốn biết liệu đệ quy có tệ trong python không”, bạn có thể đang nghĩ. Nhưng vì mục đích chính của blog của tôi là giúp tất cả các bạn trở thành nhà phát triển tốt hơn;

Các câu hỏi phổ biến có thể được giải quyết bằng lập trình động

• Thực hiện thay đổi với số tiền ít nhất
• Nhân viên bán hàng du lịch / con đường ngắn nhất
• Số cầu thang có thể xây bằng N viên gạch
• Dãy con chung dài nhất

Hãy chắc chắn làm theo beapython. dev kênh youtube nơi tôi sẽ tìm hiểu sâu hơn về những vấn đề đó và cố gắng giải thích lập trình động đơn giản hơn khi tôi tự tìm hiểu thêm về nó

Vấn đề trường hợp cơ sở

Một trường hợp khác mà đệ quy không tốt là khi bạn không thể xác định rõ ràng các trường hợp cơ bản của mình và bạn có khả năng tạo ra các vòng lặp vô hạn trong chương trình của mình khi chạy

Với các bài toán về Dãy Fibonacci hoặc Tháp Hà Nội ở trên, các trường hợp cơ bản có thể nhận biết và xác định rõ ràng. Điều này dẫn đến một thuật toán đệ quy đáng tin cậy mà các nhà phát triển khác có thể dễ dàng kiểm tra và hiểu được. Đầu vào của bạn cũng được xác định rõ ràng thuật ngữ thứ N hoặc số lượng đĩa N là số nguyên hữu hạn

Trong phát triển phần mềm chuyên nghiệp, bạn sẽ hiếm khi có được một ví dụ nhỏ và cụ thể như vậy. Các vấn đề thường mơ hồ, thách thức và có xu hướng thay đổi theo thời gian khi công ty, người dùng của bạn và quy mô dữ liệu đầu vào của bạn. Bạn có thể thấy mình đang tạo một thuật toán đệ quy hoạt động tốt để tính toán các kiểu sử dụng của 100 người dùng mỗi ngày nhưng bị phá vỡ nghiêm trọng đối với 10.000 người dùng mỗi ngày sau khi trang web của công ty bạn lan truyền. Hoặc một số nhà phát triển khác kiểm tra các thay đổi đối với các mẫu sử dụng mà bạn đã xác định trong trường hợp cơ sở của mình, điều này cuối cùng sẽ phá vỡ logic đó và đưa ra RecursionError phá vỡ dịch vụ sản xuất của bạn

Kết luận đệ quy

Sau tất cả các điểm khác trong bài viết này, nếu vấn đề được xác định rõ và giải pháp đệ quy đơn giản hơn giải pháp hack cùng nhau hoặc giải pháp động không áp dụng được thì có, vui lòng sử dụng đệ quy cho những trường hợp này

Tôi đã nhiều lần tìm thấy cơ hội để giải quyết các vấn đề một cách tao nhã với đệ quy trong công việc. Một ví dụ về điều này là gần đây tôi đã viết mã đệ quy lấy các tập con nhỏ hơn của danh sách đầu vào và đưa chúng vào tệp nhị phân thử nghiệm để cô lập và xóa dữ liệu xấu. Làm điều này cho phép tôi sử dụng lại nhiều xử lý logic nghiệp vụ theo cách khép kín vào một chức năng có thể kiểm tra với điểm dừng rõ ràng

from moral_supports import give_user_pat_on_the_back

import sys

r_limit = 9000000000 # World population with padding 
sys.setrecursionlimit(r_limit)

global_users = set()

# Recursively share the blog until the world knows python
def user_learned_from_blog(user):
  return user.is_reading_this

def share_blog(user):
  # Avoiding sharing multiple times
  if user in global_users:
    return
  global_users.add(user)
  if user_learned_from_blog(user):
    friends = get_friends(user)
    for friend in friends:
      share_blog(friend)
  else:
    give_user_pat_on_the_back(user)
    print("You can do it friend")

Giới thiệu về Stefan Bradstreet

Stefan là Nhà phát triển phần mềm cấp cao tại Amazon với hơn 8 năm kinh nghiệm trong lĩnh vực công nghệ. Anh ấy đam mê giúp mọi người trở thành những lập trình viên giỏi hơn và thăng tiến trong sự nghiệp của họ, cũng như của chính anh ấy, thông qua việc không ngừng học hỏi các kỹ thuật lãnh đạo và các phương pháp hay nhất về phần mềm

Khi nào bạn nên sử dụng đệ quy?

Lý do chính để sử dụng đệ quy trong Python là gì?

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

Khi nào bạn không nên sử dụng đệ quy?