Tại sao Python có độ sâu đệ quy tối đa?

Question

Python có độ sâu đệ quy tối đa, nhưng không có độ sâu lặp tối đa. Tại sao đệ quy bị hạn chế? Nó sẽ không tự nhiên hơn để đối xử với đệ quy như lặp lại, và không hạn chế số lượng các cuộc gọi đệ quy?

Hãy để tôi chỉ nói rằng nguồn của vấn đề này đến từ việc cố gắng triển khai luồng (xem this question để biết thêm chi tiết về luồng). Ví dụ: giả sử chúng tôi muốn viết một luồng để tạo ra các số tự nhiên:

def stream_accum(s, n): # force the stream to a list of length n 
    def loop(s, acc): 
     if len(acc) == n: 
      return acc 
     hd, tl = s() 
     return loop(tl, acc + [hd]) 
    return loop(s, []) 


def nats(): 
    def loop(n): 
     return n, lambda: loop(n+1) 
    return loop(1) 

Định nghĩa đệ quy của luồng khá hấp dẫn. Tuy nhiên, tôi đoán phương pháp tiếp cận pythonic tốt hơn/nhiều hơn sẽ là sử dụng máy phát điện.

Answer 1

Thực tế có một vài vấn đề ở đây.

Đầu tiên, như là NPE's answer giải thích một cách độc đáo, Python không loại bỏ các cuộc gọi đuôi, vì vậy nhiều chức năng cho phép đệ quy không giới hạn, ví dụ, Scheme bị giới hạn trong Python.

Thứ hai, như được giải thích bởi NPE, các cuộc gọi không thể loại bỏ chiếm dung lượng trên ngăn xếp cuộc gọi. Và, ngay cả trong các ngôn ngữ làm TCE, có rất nhiều hàm đệ quy không thể được xử lý như lặp lại. (Hãy xem xét hàm Fibonacci ngây thơ mà gọi đệ quy gọi chính nó hai lần.)

Nhưng tại sao cuộc gọi ngăn xếp một tài nguyên hữu hạn ở vị trí đầu tiên? Khung stack Python có thể ít nhất về nguyên tắc được thực hiện trên heap và liên kết với nhau (xem Stackless cho một bằng chứng tồn tại của nguyên tắc đó), và trong một không gian bộ nhớ 64-bit, có chỗ cho toàn bộ hơn 1000 khung stack. (Trong thực tế, ngay cả các C stack trên hầu như bất kỳ nền tảng hiện đại có thể tổ chức toàn bộ hơn 1000 cuộc gọi thông dịch Python đệ quy.)

Một phần lý do là lịch sử: cổ phiếu Python thông dịch viên sử dụng C cố định để gọi chính nó đệ quy bất cứ khi nào bạn thực hiện một cuộc gọi đệ quy, và nó ban đầu được thiết kế cho nền tảng 32 bit (và thậm chí là 24 hoặc 20 bit) trong đó ngăn xếp C là khá nhỏ.

Nhưng điều đó có thể đã bị thay đổi và Python 3.0 sẽ là một nơi hoàn hảo để thay đổi nó. Vì vậy, tại sao họ không? Bởi vì họ đã đưa ra quyết định thiết kế ngôn ngữ có ý thức. Trong mã Pythonic, đệ quy thường rất nông (ví dụ, mã như os.walk đi qua cấu trúc cây nông); nếu chức năng của bạn đạt đến độ sâu bất cứ nơi nào gần 1000, nó có nhiều khả năng là một lỗi hơn là cố ý. Vì vậy, giới hạn ở lại. Tất nhiên đây là một chút thông tư - nếu họ loại bỏ giới hạn (và, đặc biệt, nếu họ loại bỏ các cuộc gọi đuôi), đệ quy sâu hơn sẽ trở nên thành ngữ hơn. Nhưng đó là một điểm - Guido không muốn một ngôn ngữ mà đệ quy sâu sắc là thành ngữ. (Và hầu hết cộng đồng Python đồng ý.)

Answer 2

Đệ quy yêu cầu không gian trên call stack, bị giới hạn về kích thước. Mã được sử dụng quá nhiều mức đệ quy sẽ đưa ra lỗi gọi là stack overflow (cũng được làm nổi tiếng bởi some obscure website). Python dường như giới hạn điều này (một chút tùy ý) đến 1000 cấp độ hoặc hơn, nhưng điều này can be increased bằng cách thiết lập sys.setrecursionlimit.

Lặp lại sử dụng thứ gì đó giống như vòng lặp for, được thực hiện bằng cách tăng một số bộ đếm và điều kiện thiết lập instruction pointer trở lại đầu của vòng lặp. Đây là hằng số trong bộ nhớ.

Answer 3

Đây không phải là duy nhất đối với Python và phải thực hiện với từng không gian gọi trên call stack và kích thước của ngăn xếp bị giới hạn.

Lặp lại một mình không tiêu thụ không gian ngăn xếp và do đó không tuân theo giới hạn này.

Không phải mọi cuộc gọi đệ quy đều cần tiêu thụ không gian ngăn xếp. Ví dụ: một số ngôn ngữ có thể tự động chuyển đổi tail recursion thành lặp lại. Tuy nhiên, CPython chọn không làm điều đó (Does Python optimize tail recursion?).

Bạn có thể tăng độ sâu tối đa của ngăn xếp cuộc gọi Python bằng cách gọi sys.setrecursionlimit.