Hướng dẫn what is recursion depth in python? - độ sâu đệ quy trong python là gì?

Tôi có chức năng đệ quy đuôi này ở đây:

def recursive_function(n, sum):
    if n < 1:
        return sum
    else:
        return recursive_function(n-1, sum+n)

c = 998
print(recursive_function(c, 0))

Nó hoạt động lên đến

sys.setrecursionlimit(1500)

5, sau đó nó chỉ phá vỡ và phun ra một

sys.setrecursionlimit(1500)

6. Đây có phải chỉ là một dòng chảy ngăn xếp? Có cách nào để đi xung quanh nó không?

hỏi ngày 23 tháng 7 năm 2010 lúc 23:04Jul 23, 2010 at 23:04

QuantumSoupQuantumsoupquantumSoup

26.6K9 Huy hiệu vàng41 Huy hiệu bạc57 Huy hiệu Đồng9 gold badges41 silver badges57 bronze badges

14

Đó là một người bảo vệ chống lại một loạt tràn, vâng. Python (hay đúng hơn là việc triển khai CPython) không tối ưu hóa đệ quy đuôi và đệ quy không bị kiểm soát gây ra tràn chồng. Bạn có thể kiểm tra giới hạn đệ quy với

sys.setrecursionlimit(1500)

7:

import sys
print(sys.getrecursionlimit())

và thay đổi giới hạn đệ quy bằng

sys.setrecursionlimit(1500)

8:

sys.setrecursionlimit(1500)

Nhưng làm như vậy là nguy hiểm - giới hạn tiêu chuẩn là một chút bảo thủ, nhưng các khung hình Python có thể khá lớn.

Python không phải là một ngôn ngữ chức năng và đệ quy đuôi không phải là một kỹ thuật đặc biệt hiệu quả. Viết lại thuật toán lặp đi lặp lại, nếu có thể, nói chung là một ý tưởng tốt hơn.

Rob Bednark

24.1K21 Huy hiệu vàng78 Huy hiệu bạc119 Huy hiệu đồng21 gold badges78 silver badges119 bronze badges

Đã trả lời ngày 23 tháng 7 năm 2010 lúc 23:08Jul 23, 2010 at 23:08

Thomas Woutersthomas WoutersThomas Wouters

127K23 Huy hiệu vàng146 Huy hiệu bạc122 Huy hiệu Đồng23 gold badges146 silver badges122 bronze badges

10

Có vẻ như bạn chỉ cần đặt độ sâu đệ quy cao hơn:

import sys
sys.setrecursionlimit(1500)

Đã trả lời ngày 23 tháng 7 năm 2010 lúc 23:07Jul 23, 2010 at 23:07

David Youngdavid YoungDavid Young

4.5532 Huy hiệu vàng20 Huy hiệu bạc18 Huy hiệu Đồng2 gold badges20 silver badges18 bronze badges

2

Nếu bạn thường cần thay đổi giới hạn đệ quy (ví dụ: trong khi giải các câu đố lập trình), bạn có thể xác định một trình quản lý ngữ cảnh đơn giản như thế này:

import sys

class recursionlimit:
    def __init__(self, limit):
        self.limit = limit

    def __enter__(self):
        self.old_limit = sys.getrecursionlimit()
        sys.setrecursionlimit(self.limit)

    def __exit__(self, type, value, tb):
        sys.setrecursionlimit(self.old_limit)

Sau đó, để gọi một chức năng với giới hạn tùy chỉnh mà bạn có thể làm:

with recursionlimit(1500):
    print(fib(1000, 0))

Khi thoát khỏi phần thân của câu lệnh

sys.setrecursionlimit(1500)

9, giới hạn đệ quy sẽ được khôi phục về giá trị mặc định.

P.S. Bạn cũng có thể muốn tăng kích thước ngăn xếp của quy trình Python cho các giá trị lớn của giới hạn đệ quy. Ví dụ, có thể được thực hiện thông qua tệp

import sys
sys.setrecursionlimit(1500)

0 SHOD hoặc

import sys
sys.setrecursionlimit(1500)

1.

Đã trả lời ngày 1 tháng 5 năm 2018 lúc 16:37May 1, 2018 at 16:37

Eugene Yarmasheugene YarmashEugene Yarmash

136K39 Huy hiệu vàng313 Huy hiệu bạc369 Huy hiệu đồng39 gold badges313 silver badges369 bronze badges

2

Đó là để tránh một dòng tràn chồng. Thông dịch viên Python giới hạn độ sâu của đệ quy để giúp bạn tránh các đệ quy vô hạn, dẫn đến tràn chồng. Hãy thử tăng giới hạn đệ quy (

sys.setrecursionlimit(1500)

8) hoặc viết lại mã của bạn mà không cần đệ quy.

Từ tài liệu Python:

import sys
sys.setrecursionlimit(1500)

3

Trả về giá trị hiện tại của giới hạn đệ quy, độ sâu tối đa của ngăn xếp phiên dịch Python. Giới hạn này ngăn chặn đệ quy vô hạn gây ra tràn của ngăn xếp C và làm hỏng trăn. Nó có thể được đặt bởi

import sys
sys.setrecursionlimit(1500)

4.

Đã trả lời ngày 23 tháng 7 năm 2010 lúc 23:08Jul 23, 2010 at 23:08

1

Thomas Woutersthomas Wouters

127K23 Huy hiệu vàng146 Huy hiệu bạc122 Huy hiệu Đồng

Có vẻ như bạn chỉ cần đặt độ sâu đệ quy cao hơn:

Đã trả lời ngày 23 tháng 7 năm 2010 lúc 23:07

David Youngdavid Young

4.5532 Huy hiệu vàng20 Huy hiệu bạc18 Huy hiệu Đồng

Nếu bạn thường cần thay đổi giới hạn đệ quy (ví dụ: trong khi giải các câu đố lập trình), bạn có thể xác định một trình quản lý ngữ cảnh đơn giản như thế này:

Sau đó, để gọi một chức năng với giới hạn tùy chỉnh mà bạn có thể làm:

main.py

import resource
import sys

print resource.getrlimit(resource.RLIMIT_STACK)
print sys.getrecursionlimit()
print

# Will segfault without this line.
resource.setrlimit(resource.RLIMIT_STACK, [0x10000000, resource.RLIM_INFINITY])
sys.setrecursionlimit(0x100000)

def f(i):
    print i
    sys.stdout.flush()
    f(i + 1)
f(0)

Khi thoát khỏi phần thân của câu lệnh

sys.setrecursionlimit(1500)

9, giới hạn đệ quy sẽ được khôi phục về giá trị mặc định.

P.S. Bạn cũng có thể muốn tăng kích thước ngăn xếp của quy trình Python cho các giá trị lớn của giới hạn đệ quy. Ví dụ, có thể được thực hiện thông qua tệp

import sys
sys.setrecursionlimit(1500)

0 SHOD hoặc

import sys
sys.setrecursionlimit(1500)

1.

ulimit -s
ulimit -s 10000

Đã trả lời ngày 1 tháng 5 năm 2018 lúc 16:37

Eugene Yarmasheugene Yarmash

• 136K39 Huy hiệu vàng313 Huy hiệu bạc369 Huy hiệu đồng
• Đó là để tránh một dòng tràn chồng. Thông dịch viên Python giới hạn độ sâu của đệ quy để giúp bạn tránh các đệ quy vô hạn, dẫn đến tràn chồng. Hãy thử tăng giới hạn đệ quy (

  sys.setrecursionlimit(1500)
  

  8) hoặc viết lại mã của bạn mà không cần đệ quy.

Từ tài liệu Python:

Trả về giá trị hiện tại của giới hạn đệ quy, độ sâu tối đa của ngăn xếp phiên dịch Python. Giới hạn này ngăn chặn đệ quy vô hạn gây ra tràn của ngăn xếp C và làm hỏng trăn. Nó có thể được đặt bởi

import sys
sys.setrecursionlimit(1500)

4.Jan 28, 2017 at 23:40

3

import sys
sys.setrecursionlimit(1500)

5 cũng phải được sử dụng để tăng kích thước ngăn xếp và ngăn chặn Segfault

Hạt nhân Linux giới hạn ngăn xếp các quy trình.Jul 23, 2010 at 23:12

Python lưu trữ các biến cục bộ trên ngăn xếp của thông dịch viên, và do đó, đệ quy chiếm không gian ngăn xếp của trình thông dịch.Marcelo Cantos

Nếu thông dịch viên Python cố gắng vượt quá giới hạn ngăn xếp, hạt nhân Linux làm cho nó bị lỗi phân đoạn.38 gold badges322 silver badges362 bronze badges

4

Kích thước giới hạn ngăn xếp được kiểm soát với các cuộc gọi hệ thống

import sys
sys.setrecursionlimit(1500)

6 và

import sys
sys.setrecursionlimit(1500)

7.

def fibonacci(n):
    f = [0,1,1]
    for i in xrange(3,n):
        f.append(f[i-1] + f[i-2])
    return 'The %.0fth fibonacci number is: %.0f' % (n,f[-1])

Python cung cấp quyền truy cập vào các cuộc gọi hệ thống đó thông qua mô -đun

import sys
sys.setrecursionlimit(1500)

8.

sys.setrecursionlimit(1500)

8 đã đề cập, ví dụ: Tại https://stackoverflow.com/a/3323013/895245 chỉ làm tăng giới hạn mà người phiên dịch Python tự áp đặt lên kích thước ngăn xếp của chính nó, nhưng nó không chạm vào giới hạn do nhân Linux áp đặt trên quy trình Python.Sep 6, 2013 at 3:17

Chương trình ví dụ:Daniel

Tất nhiên, nếu bạn tiếp tục tăng

import sys
sys.setrecursionlimit(1500)

7, RAM của bạn cuối cùng sẽ hết, điều này sẽ làm chậm máy tính của bạn để dừng lại do hoán đổi sự điên rồ, hoặc tiêu diệt Python qua kẻ giết người.5 gold badges26 silver badges35 bronze badges

6

Từ bash, bạn có thể thấy và đặt giới hạn ngăn xếp (tính bằng kb) với:

Đã trả lời ngày 14 tháng 10 năm 2014 lúc 18:14Oct 14, 2014 at 18:14

TylertylerTyler

Huy hiệu đồng 1911 Bạc6 Huy hiệu Đồng1 silver badge6 bronze badges

3

Tất nhiên các số Fibonacci có thể được tính toán trong O (N) bằng cách áp dụng công thức Binet:

from math import floor, sqrt

def fib(n):                                                     
    return int(floor(((1+sqrt(5))**n-(1-sqrt(5))**n)/(2**n*sqrt(5))+0.5))

Như các nhà bình luận lưu ý, nó không phải là O (1) mà là O (N) vì

import sys

class recursionlimit:
    def __init__(self, limit):
        self.limit = limit

    def __enter__(self):
        self.old_limit = sys.getrecursionlimit()
        sys.setrecursionlimit(self.limit)

    def __exit__(self, type, value, tb):
        sys.setrecursionlimit(self.old_limit)

2. Ngoài ra, một sự khác biệt là bạn chỉ nhận được một giá trị, trong khi với đệ quy, bạn nhận được tất cả các giá trị của

import sys

class recursionlimit:
    def __init__(self, limit):
        self.limit = limit

    def __enter__(self):
        self.old_limit = sys.getrecursionlimit()
        sys.setrecursionlimit(self.limit)

    def __exit__(self, type, value, tb):
        sys.setrecursionlimit(self.old_limit)

3 theo giá trị đó.

Đã trả lời ngày 8 tháng 10 năm 2015 lúc 6:19Oct 8, 2015 at 6:19

rwstrwstrwst

2.4462 Huy hiệu vàng28 Huy hiệu bạc35 Huy hiệu Đồng2 gold badges28 silver badges35 bronze badges

9

Nếu bạn muốn chỉ nhận được một vài số Fibonacci, bạn có thể sử dụng phương thức ma trận.

import sys
print(sys.getrecursionlimit())

0

Nó nhanh khi Numpy sử dụng thuật toán số mũ nhanh. Bạn nhận được câu trả lời trong o (log n). Và nó tốt hơn công thức của Binet vì nó chỉ sử dụng số nguyên. Nhưng nếu bạn muốn tất cả các số fibonacci lên đến n, thì tốt hơn là nên thực hiện nó bằng cách ghi nhớ.

Đã trả lời ngày 17 tháng 2 năm 2018 lúc 15:57Feb 17, 2018 at 15:57

BEBIDEKBEBIDEKbebidek

5643 Huy hiệu bạc8 Huy hiệu Đồng3 silver badges8 bronze badges

1

Chúng ta có thể làm điều đó bằng cách sử dụng phương pháp trang trí

import sys

class recursionlimit:
    def __init__(self, limit):
        self.limit = limit

    def __enter__(self):
        self.old_limit = sys.getrecursionlimit()
        sys.setrecursionlimit(self.limit)

    def __exit__(self, type, value, tb):
        sys.setrecursionlimit(self.old_limit)

4 và

import sys
sys.setrecursionlimit(1500)

4:

import sys
print(sys.getrecursionlimit())

1

Đầu ra

import sys
print(sys.getrecursionlimit())

2

Nguồn

functools lru_cache

Đã trả lời ngày 26 tháng 10 năm 2019 lúc 15:26Oct 26, 2019 at 15:26

EmmaemmaEmma

27K10 Huy hiệu vàng42 Huy hiệu bạc67 Huy hiệu Đồng10 gold badges42 silver badges67 bronze badges

2

Đệ quy: độ sâu đệ quy tối đa vượt quá

Dung dịch :

Đầu tiên, nó tốt hơn khi biết khi bạn thực hiện hàm đệ quy trong Python trên một đầu vào lớn (> 10^4), bạn có thể gặp phải độ sâu đệ quy tối đa vượt quá lỗi vượt quá lỗi.

Mô -đun SYS trong Python có hàm getRecursionLimit () có thể hiển thị giới hạn đệ quy trong phiên bản Python của bạn.

import sys
print(sys.getrecursionlimit())

3

Mặc định trong một số phiên bản của Python là 1000 và trong một số khác là 1500

Bạn có thể thay đổi giới hạn này nhưng nó rất quan trọng để biết nếu bạn tăng rất nhiều, bạn sẽ gặp lỗi tràn bộ nhớ.

Vì vậy, hãy cẩn thận trước khi tăng nó. Bạn có thể sử dụng SetRecursionLimit () để tăng giới hạn này trong Python.

import sys
print(sys.getrecursionlimit())

4

Vui lòng theo liên kết này để biết thêm thông tin về điều gì đó vì vấn đề này:

https://elvand.com/quick-sort-binary-search/

Đã trả lời ngày 17 tháng 3 năm 2021 lúc 16:33Mar 17, 2021 at 16:33

Như @Alex đã đề xuất, bạn có thể sử dụng hàm máy phát để thực hiện tuần tự này thay vì đệ quy.

Đây là tương đương với mã trong câu hỏi của bạn:

import sys
print(sys.getrecursionlimit())

5

Đã trả lời ngày 12 tháng 7 năm 2016 lúc 16:58Jul 12, 2016 at 16:58

Martineaumartineaumartineau

Huy hiệu vàng 116K2525 gold badges161 silver badges288 bronze badges

EDIT: 6 năm sau tôi nhận ra "máy phát điện sử dụng" của mình là flippant và không trả lời câu hỏi. Lời xin lỗi của tôi.

Tôi đoán câu hỏi đầu tiên của tôi sẽ là: Bạn có thực sự cần thay đổi giới hạn đệ quy không? Nếu không, thì có lẽ tôi hoặc bất kỳ câu trả lời nào khác không liên quan đến việc thay đổi giới hạn đệ quy sẽ được áp dụng. Mặt khác, như đã lưu ý, ghi đè giới hạn đệ quy bằng cách sử dụng

import sys

class recursionlimit:
    def __init__(self, limit):
        self.limit = limit

    def __enter__(self):
        self.old_limit = sys.getrecursionlimit()
        sys.setrecursionlimit(self.limit)

    def __exit__(self, type, value, tb):
        sys.setrecursionlimit(self.old_limit)

6.

Sử dụng máy phát điện?

import sys
print(sys.getrecursionlimit())

6

Trên

import sys

class recursionlimit:
    def __init__(self, limit):
        self.limit = limit

    def __enter__(self):
        self.old_limit = sys.getrecursionlimit()
        sys.setrecursionlimit(self.limit)

    def __exit__(self, type, value, tb):
        sys.setrecursionlimit(self.old_limit)

7 chức năng được điều chỉnh từ giới thiệu với các trình tạo python.

Martineau

Huy hiệu vàng 116K2525 gold badges161 silver badges288 bronze badges

EDIT: 6 năm sau tôi nhận ra "máy phát điện sử dụng" của mình là flippant và không trả lời câu hỏi. Lời xin lỗi của tôi.Jul 30, 2015 at 18:32

Tôi đoán câu hỏi đầu tiên của tôi sẽ là: Bạn có thực sự cần thay đổi giới hạn đệ quy không? Nếu không, thì có lẽ tôi hoặc bất kỳ câu trả lời nào khác không liên quan đến việc thay đổi giới hạn đệ quy sẽ được áp dụng. Mặt khác, như đã lưu ý, ghi đè giới hạn đệ quy bằng cách sử dụng

import sys

class recursionlimit:
    def __init__(self, limit):
        self.limit = limit

    def __enter__(self):
        self.old_limit = sys.getrecursionlimit()
        sys.setrecursionlimit(self.limit)

    def __exit__(self, type, value, tb):
        sys.setrecursionlimit(self.old_limit)

6.alex

Sử dụng máy phát điện?2 silver badges6 bronze badges

3

Trên

import sys

class recursionlimit:
    def __init__(self, limit):
        self.limit = limit

    def __enter__(self):
        self.old_limit = sys.getrecursionlimit()
        sys.setrecursionlimit(self.limit)

    def __exit__(self, type, value, tb):
        sys.setrecursionlimit(self.old_limit)

7 chức năng được điều chỉnh từ giới thiệu với các trình tạo python.

import sys
print(sys.getrecursionlimit())

7

MartineauApr 13, 2016 at 8:56

Đã trả lời ngày 30 tháng 7 năm 2015 lúc 18:32Harun ERGUL

Alexalex5 gold badges53 silver badges61 bronze badges

2272 Huy hiệu bạc6 Huy hiệu Đồng

import sys
print(sys.getrecursionlimit())

8

Nhiều người khuyên rằng việc tăng giới hạn đệ quy là một giải pháp tốt tuy nhiên không phải vì sẽ luôn có giới hạn. Thay vào đó sử dụng một giải pháp lặp.

Đã trả lời ngày 13 tháng 4 năm 2016 lúc 8:56Mar 12, 2019 at 13:59

import sys
print(sys.getrecursionlimit())

9

Harun Ergulharun Ergul

5,5045 huy hiệu vàng53 Huy hiệu bạc61 Huy hiệu đồng18 gold badges139 silver badges209 bronze badges

Tôi muốn cho bạn một ví dụ để sử dụng ghi nhớ để tính toán Fibonacci vì điều này sẽ cho phép bạn tính toán số lượng lớn hơn đáng kể bằng cách sử dụng đệ quy:May 7, 2019 at 5:35

1

Điều này vẫn còn đệ quy, nhưng sử dụng một hashtable đơn giản cho phép tái sử dụng các số Fibonacci được tính toán trước đó thay vì thực hiện lại.

sys.setrecursionlimit(1500)

0

Đã trả lời ngày 12 tháng 3 năm 2019 lúc 13:59Nov 12, 2019 at 16:32

EYLLLANESCxariez

227K18 Huy hiệu vàng139 Huy hiệu bạc209 Huy hiệu đồng1 gold badge5 silver badges17 bronze badges

Đã trả lời ngày 7 tháng 5 năm 2019 lúc 5:35

sys.setrecursionlimit(1500)

1

Chúng tôi cũng có thể sử dụng một biến thể của cách tiếp cận từ dưới lên của lập trình động

sys.setrecursionlimit(1500)

2

Đã trả lời ngày 12 tháng 11 năm 2019 lúc 16:32

sys.setrecursionlimit(1500)

3

output:

sys.setrecursionlimit(1500)

4

Xariezxariez

5091 Huy hiệu vàng5 Huy hiệu bạc17 Huy hiệu đồngDec 14, 2020 at 14:33

wiesiu_pwiesiu_pwiesiu_p

Tôi không chắc là tôi đang lặp lại ai đó nhưng một thời gian trước, một số linh hồn tốt đã viết Y-coperator cho chức năng được gọi là đệ quy như:5 silver badges6 bronze badges

Độ sâu đệ quy là gì?

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

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