Tôi có nên tránh đệ quy trong python không?

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

Không còn nghi ngờ gì nữa, đệ quy là một công cụ tuyệt vời và là một cách tự nhiên để diễn đạt nhiều thuật toán theo cách dễ hiểu. Nhưng mọi điều tốt đẹp đều phải trả giá, và bài đăng này nói về những ưu và nhược điểm của việc sử dụng đệ quy, cho bạn biết khi nào thì nên sử dụng và khi nào thì không.

Trước tiên chúng ta hãy thảo luận về các bước được thực hiện khi một chức năng được gọi

1. Không gian được tạo trên ngăn xếp cho các đối số của hàm và các biến cục bộ
2. Các đối số của hàm được sao chép vào không gian này
3. Mã chức năng thực thi
4. Stack đi đến vị trí trước đó của nó

Làm tất cả những điều này mất nhiều thời gian hơn một chút so với lặp qua một vòng lặp nhưng vấn đề thực sự với đệ quy là bước đầu tiên. Mỗi khi một cuộc gọi đệ quy được thực hiện, một không gian ngăn xếp được phân bổ để lưu trữ các biến cục bộ và do đó, chương trình có thể gây ra sự cố tràn ngăn xếp nếu số lượng cuộc gọi đệ quy lớn

Hãy viết hàm đệ quy để tính giai thừa của một số

fac(int n)
  if (n == 0 OR n == 1)
    return 1
  else
    return a*fac(a-1)

Tính 1000. với chương trình này sẽ sử dụng 1000 khung ngăn xếp

fac(int n)
  i = 1;
  while n>1
    i = i*n
    n = n-1
  return

Nhưng giải pháp lặp sẽ chủ yếu chỉ sử dụng một khung ngăn xếp

Hãy lấy một ví dụ về tính toán chuỗi Fibonacci

fib(int n)
  if (n == 0 OR n == 1)
    return 1
  else
    return fib(n-1)+fib(n-2)

Đây là cách tự nhiên để viết chuỗi Fibonacci vì theo định nghĩa, số Fibonacci là 1 nếu 'n' là 0 hoặc 1. Khác nó là f(n-1)+f(n-2) và đoạn mã trên thể hiện điều này theo cách tự nhiên nhất. Nhưng vấn đề chính với điều này là cùng một giá trị sẽ được tính toán lặp đi lặp lại để tính toán một số hạng Fibonacci và điều này sẽ mất nhiều thời gian hơn và quan trọng hơn là nhiều không gian ngăn xếp hơn. Ví dụ: hãy tính fib(5) bằng thuật toán đã cho ở trên

Bạn có thể thấy rằng fib(5) dẫn đến việc tính toán fib(4) và fib(3). Và fib(4) dẫn đến việc tính fib(3) và fib(2). Vì vậy, cho đến bước này, chỉ fib(3) được tính hai lần. Tương tự, fib(2) được tính nhiều lần trong ví dụ này

Vì vậy, mặc dù đệ quy đại diện cho thuật toán theo cách tự nhiên, nhưng nó rất kém hiệu quả trong trường hợp này

Do đó, đệ quy có thể gây tràn bộ nhớ nếu không gian ngăn xếp của bạn lớn và cũng không hiệu quả trong trường hợp cùng một giá trị được tính đi tính lại. Vì vậy, hãy sử dụng phép lặp hoặc phép đệ quy tùy theo tác vụ bạn muốn thực hiện. Nếu yêu cầu đơn giản và tràn bộ nhớ không phải là vấn đề lớn thì hãy sử dụng đệ quy nếu không thì sử dụng phép lặp

Bạn có nên sử dụng đệ quy trong Python không?

Tôi có nên tránh sử dụng đệ quy?

Khi nào bạn nên ngừng đệ quy?