search

In 1 đến 10 bằng đệ quy trong python

1 năms trước
Trả lời: 0
Lượt xem: 35

Nếu bạn đã quen thuộc với các hàm trong Python, thì bạn sẽ biết rằng việc một hàm này gọi một hàm khác là điều khá phổ biến. Trong Python, một hàm cũng có thể gọi chính nó. Một hàm gọi chính nó được gọi là đệ quy và kỹ thuật sử dụng hàm đệ quy được gọi là đệ quy

Show

Nó có vẻ đặc biệt đối với một chức năng để gọi chính nó, nhưng nhiều loại vấn đề lập trình được thể hiện tốt nhất bằng cách đệ quy. Khi bạn gặp phải một vấn đề như vậy, đệ quy là một công cụ không thể thiếu để bạn có trong bộ công cụ của mình

Đến cuối hướng dẫn này, bạn sẽ hiểu

  • Ý nghĩa của việc một hàm gọi chính nó một cách đệ quy
  • Cách thiết kế các hàm Python hỗ trợ đệ quy
  • Những yếu tố cần xem xét khi lựa chọn có hay không giải quyết vấn đề theo cách đệ quy
  • Cách triển khai hàm đệ quy trong Python

Sau đó, bạn sẽ nghiên cứu một số vấn đề lập trình Python sử dụng đệ quy và so sánh giải pháp đệ quy với giải pháp không đệ quy có thể so sánh được

Tiền thưởng miễn phí. Nhận một chương mẫu từ Python Basics. Giới thiệu thực tế về Python 3 để xem cách bạn có thể đi từ trình độ mới bắt đầu lên trình độ trung cấp trong Python với một chương trình giảng dạy hoàn chỉnh, cập nhật về Python 3. 9

Đệ quy là gì?

Từ đệ quy xuất phát từ từ tiếng Latin recurrere, có nghĩa là chạy hoặc đẩy nhanh trở lại, quay trở lại, hoàn nguyên hoặc lặp lại. Dưới đây là một số định nghĩa trực tuyến về đệ quy

  • Từ điển. com. Hành động hoặc quá trình quay trở lại hoặc chạy trở lại
  • từ điển mở. Hành động xác định một đối tượng (thường là một chức năng) theo chính đối tượng đó
  • từ điển miễn phí. Một phương pháp xác định một chuỗi các đối tượng, chẳng hạn như một biểu thức, hàm hoặc tập hợp, trong đó một số đối tượng ban đầu được cho trước và mỗi đối tượng kế tiếp được xác định theo các đối tượng trước đó

Định nghĩa đệ quy là định nghĩa trong đó thuật ngữ được xác định xuất hiện trong chính định nghĩa đó. Các tình huống tự giới thiệu thường xuất hiện trong cuộc sống thực, ngay cả khi chúng không được nhận ra ngay lập tức như vậy. Ví dụ: giả sử bạn muốn mô tả nhóm người tạo nên tổ tiên của bạn. Bạn có thể mô tả chúng theo cách này

In 1 đến 10 bằng đệ quy trong python

Lưu ý cách khái niệm đang được định nghĩa, tổ tiên, xuất hiện trong định nghĩa của chính nó. Đây là một định nghĩa đệ quy

Trong lập trình, đệ quy có một ý nghĩa rất chính xác. Nó đề cập đến một kỹ thuật mã hóa trong đó một chức năng gọi chính nó

Loại bỏ các quảng cáo

Tại sao sử dụng đệ quy?

Hầu hết các vấn đề lập trình đều có thể giải được mà không cần đệ quy. Vì vậy, nói đúng ra, đệ quy thường không cần thiết

Tuy nhiên, một số tình huống đặc biệt phù hợp với định nghĩa tự quy chiếu—ví dụ: định nghĩa về tổ tiên được trình bày ở trên. Nếu bạn đang nghĩ ra một thuật toán để xử lý trường hợp như vậy theo chương trình, thì một giải pháp đệ quy có thể sẽ rõ ràng và ngắn gọn hơn

Truyền tải cấu trúc dữ liệu dạng cây là một ví dụ điển hình khác. Vì đây là các cấu trúc lồng nhau nên chúng dễ dàng phù hợp với định nghĩa đệ quy. Một thuật toán không đệ quy để đi qua một cấu trúc lồng nhau có thể hơi rắc rối, trong khi một giải pháp đệ quy sẽ tương đối thanh lịch. Một ví dụ về điều này xuất hiện sau trong hướng dẫn này

Mặt khác, đệ quy không dành cho mọi tình huống. Dưới đây là một số yếu tố khác để xem xét

  • Đối với một số vấn đề, một giải pháp đệ quy, mặc dù có thể, sẽ khó xử hơn là thanh lịch
  • Việc triển khai đệ quy thường tiêu tốn nhiều bộ nhớ hơn so với các triển khai không đệ quy
  • Trong một số trường hợp, sử dụng đệ quy có thể dẫn đến thời gian thực hiện chậm hơn

Thông thường, khả năng đọc mã sẽ là yếu tố quyết định lớn nhất. Nhưng nó phụ thuộc vào hoàn cảnh. Các ví dụ được trình bày dưới đây sẽ giúp bạn cảm nhận được khi nào bạn nên chọn đệ quy

Đệ quy trong Python

Khi bạn gọi một hàm trong Python, trình thông dịch sẽ tạo một không gian tên cục bộ mới để các tên được xác định trong hàm đó không xung đột với các tên giống hệt nhau được xác định ở nơi khác. Một chức năng có thể gọi một chức năng khác và ngay cả khi cả hai đều xác định các đối tượng có cùng tên, tất cả đều hoạt động tốt vì các đối tượng đó tồn tại trong các không gian tên riêng biệt

Điều này cũng đúng nếu nhiều phiên bản của cùng một chức năng đang chạy đồng thời. Ví dụ, xét định nghĩa sau

def function():
    x = 10
    function()

Khi 

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000
4 thực thi lần đầu tiên, Python tạo một không gian tên và gán cho 
>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000
5 giá trị 
>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000
6 trong không gian tên đó. Sau đó, 
>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000
4 tự gọi đệ quy. Lần thứ hai 
>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000
4 chạy, trình thông dịch tạo một không gian tên thứ hai và gán 
>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000
6 cho 
>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000
5 ở đó. Hai phiên bản tên 
>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000
5 này khác biệt với nhau và có thể cùng tồn tại mà không xung đột vì chúng nằm trong các không gian tên riêng biệt

Thật không may, việc chạy 

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000
4 khi nó đứng tạo ra một kết quả kém truyền cảm hứng, như dấu vết sau đây cho thấy

>>> 

>>> function()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

Như đã viết, về lý thuyết, 

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000
4 sẽ diễn ra mãi mãi, tự gọi đi gọi lại mà không có bất kỳ cuộc gọi nào quay trở lại. Trong thực tế, tất nhiên, không có gì là thực sự mãi mãi. Máy tính của bạn chỉ có rất nhiều bộ nhớ và cuối cùng nó sẽ hết

Python không cho phép điều đó xảy ra. Trình thông dịch giới hạn số lần tối đa mà một hàm có thể gọi chính nó theo cách đệ quy và khi nó đạt đến giới hạn đó, nó sẽ đưa ra một ngoại lệ 

>>> def countdown(n):
..     print(n)
..     if n == 0:
..         return             # Terminate recursion
..     else:
..         countdown(n - 1)   # Recursive call
...

>>> countdown(5)
5
4
3
2
1
0
4, như bạn thấy ở trên

lưu ý kỹ thuật. Bạn có thể tìm hiểu giới hạn đệ quy của Python là gì với một hàm từ mô-đun 

>>> def countdown(n):
..     print(n)
..     if n == 0:
..         return             # Terminate recursion
..     else:
..         countdown(n - 1)   # Recursive call
...

>>> countdown(5)
5
4
3
2
1
0
5 có tên là 
>>> def countdown(n):
..     print(n)
..     if n == 0:
..         return             # Terminate recursion
..     else:
..         countdown(n - 1)   # Recursive call
...

>>> countdown(5)
5
4
3
2
1
0
6

>>> 

>>> from sys import getrecursionlimit
>>> getrecursionlimit()
1000

Bạn cũng có thể thay đổi nó với 

>>> def countdown(n):
..     print(n)
..     if n == 0:
..         return             # Terminate recursion
..     else:
..         countdown(n - 1)   # Recursive call
...

>>> countdown(5)
5
4
3
2
1
0
7

>>> 

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000

Bạn có thể đặt nó ở mức khá lớn, nhưng bạn không thể đặt nó ở mức vô hạn

Không có nhiều công dụng đối với một chức năng gọi chính nó một cách bừa bãi mà không có kết thúc. Nó gợi nhớ đến các hướng dẫn mà đôi khi bạn tìm thấy trên chai dầu gội đầu. "Lót, rửa sạch, lặp lại. ” Nếu bạn làm theo những hướng dẫn này theo đúng nghĩa đen, bạn sẽ gội đầu mãi mãi

Lỗ hổng hợp lý này rõ ràng đã xảy ra với một số nhà sản xuất dầu gội đầu, bởi vì một số chai dầu gội thay vì ghi “Tạo bọt, xả, lặp lại khi cần thiết. ” Điều đó cung cấp một điều kiện chấm dứt cho các hướng dẫn. Có lẽ, cuối cùng bạn sẽ cảm thấy tóc của mình đủ sạch để cân nhắc việc lặp lại thêm lần nữa là không cần thiết. Gội đầu sau đó có thể dừng lại

Tương tự, một chức năng gọi chính nó một cách đệ quy phải có một kế hoạch để cuối cùng dừng lại. Các hàm đệ quy thường tuân theo mẫu này

  • Có một hoặc nhiều trường hợp cơ sở có thể giải trực tiếp mà không cần đệ quy thêm
  • Mỗi cuộc gọi đệ quy di chuyển giải pháp dần dần đến gần trường hợp cơ sở

Bây giờ bạn đã sẵn sàng để xem nó hoạt động như thế nào với một số ví dụ

Loại bỏ các quảng cáo

Bắt đầu. Đếm ngược đến số không

Ví dụ đầu tiên là một hàm có tên là 

>>> def countdown(n):
..     print(n)
..     if n == 0:
..         return             # Terminate recursion
..     else:
..         countdown(n - 1)   # Recursive call
...

>>> countdown(5)
5
4
3
2
1
0
8, lấy một số dương làm đối số và in các số từ đối số đã chỉ định xuống 0

>>> 

>>> def countdown(n):
..     print(n)
..     if n == 0:
..         return             # Terminate recursion
..     else:
..         countdown(n - 1)   # Recursive call
...

>>> countdown(5)
5
4
3
2
1
0

Lưu ý cách 

>>> def countdown(n):
..     print(n)
..     if n == 0:
..         return             # Terminate recursion
..     else:
..         countdown(n - 1)   # Recursive call
...

>>> countdown(5)
5
4
3
2
1
0
8 phù hợp với mô hình cho thuật toán đệ quy được mô tả ở trên

  • Trường hợp cơ sở xảy ra khi 
    def countdown(n):
    print(n)
    if n > 0:
        countdown(n - 1)
    0 bằng 0, tại đó đệ quy dừng lại
  • Trong lời gọi đệ quy, đối số nhỏ hơn một giá trị hiện tại của 
    def countdown(n):
    print(n)
    if n > 0:
        countdown(n - 1)
    0, vì vậy mỗi lần đệ quy sẽ tiến gần hơn đến trường hợp cơ sở

Ghi chú. Để đơn giản, 

>>> def countdown(n):
..     print(n)
..     if n == 0:
..         return             # Terminate recursion
..     else:
..         countdown(n - 1)   # Recursive call
...

>>> countdown(5)
5
4
3
2
1
0
8 không kiểm tra tính hợp lệ của đối số. Nếu 
def countdown(n):
    print(n)
    if n > 0:
        countdown(n - 1)
0 không phải là số nguyên hoặc âm, bạn sẽ nhận được ngoại lệ 
>>> def countdown(n):
..     print(n)
..     if n == 0:
..         return             # Terminate recursion
..     else:
..         countdown(n - 1)   # Recursive call
...

>>> countdown(5)
5
4
3
2
1
0
4 vì trường hợp cơ sở không bao giờ đạt được

Phiên bản của 

>>> def countdown(n):
..     print(n)
..     if n == 0:
..         return             # Terminate recursion
..     else:
..         countdown(n - 1)   # Recursive call
...

>>> countdown(5)
5
4
3
2
1
0
8 được hiển thị ở trên làm nổi bật rõ ràng trường hợp cơ sở và lệnh gọi đệ quy, nhưng có một cách ngắn gọn hơn để diễn đạt nó

def countdown(n):
    print(n)
    if n > 0:
        countdown(n - 1)

Đây là một triển khai không đệ quy có thể có để so sánh

>>> 

>>> def countdown(n):
..     while n >= 0:
..         print(n)
..         n -= 1
...

>>> countdown(5)
5
4
3
2
1
0

Đây là trường hợp mà giải pháp không đệ quy ít nhất cũng rõ ràng và trực quan như giải pháp đệ quy, và có lẽ còn hơn thế nữa

Tính giai thừa

Ví dụ tiếp theo liên quan đến khái niệm toán học về giai thừa. Giai thừa của số nguyên dương n, ký hiệu là n. , được định nghĩa như sau

In 1 đến 10 bằng đệ quy trong python

Nói cách khác, n. là tích của tất cả các số nguyên từ 1 đến n, kể cả

Giai thừa tự nó phù hợp với định nghĩa đệ quy đến nỗi các văn bản lập trình hầu như luôn bao gồm nó như một trong những ví dụ đầu tiên. Bạn có thể diễn đạt định nghĩa của n. đệ quy như thế này

In 1 đến 10 bằng đệ quy trong python

Như với ví dụ hiển thị ở trên, có những trường hợp cơ bản có thể giải quyết được mà không cần đệ quy. Các trường hợp phức tạp hơn là rút gọn, nghĩa là chúng rút gọn thành một trong các trường hợp cơ bản

  • Các trường hợp cơ bản (n = 0 hoặc n = 1) có thể giải được mà không cần đệ quy
  • Đối với các giá trị của n lớn hơn 1, n. được xác định theo (n - 1). , vì vậy giải pháp đệ quy dần dần tiếp cận trường hợp cơ sở

Ví dụ, tính toán đệ quy của 4. trông như thế này

In 1 đến 10 bằng đệ quy trong python
Phép tính đệ quy của 4

Các tính toán của 4. , 3. , và 2. tạm dừng cho đến khi thuật toán đạt đến trường hợp cơ sở trong đó n = 1. Tại thời điểm đó, 1. có thể tính toán được mà không cần đệ quy thêm và các phép tính trì hoãn chạy đến khi hoàn thành

Loại bỏ các quảng cáo

Xác định hàm giai thừa Python

Đây là một hàm Python đệ quy để tính giai thừa. Lưu ý mức độ ngắn gọn của nó và mức độ phản ánh định nghĩa được hiển thị ở trên

>>> 

>>> def factorial(n):
..     return 1 if n <= 1 else n * factorial(n - 1)
...

>>> factorial(4)
24

Một chút tô điểm cho chức năng này với một số câu lệnh 

def countdown(n):
    print(n)
    if n > 0:
        countdown(n - 1)
6 giúp hiểu rõ hơn về trình tự gọi và trả về

>>> 

>>> def factorial(n):
..     print(f"factorial() called with n = {n}")
..     return_value = 1 if n <= 1 else n * factorial(n -1)
..     print(f"-> factorial({n}) returns {return_value}")
..     return return_value
...

>>> factorial(4)
factorial() called with n = 4
factorial() called with n = 3
factorial() called with n = 2
factorial() called with n = 1
-> factorial(1) returns 1
-> factorial(2) returns 2
-> factorial(3) returns 6
-> factorial(4) returns 24
24

Lưu ý cách tất cả các cuộc gọi đệ quy xếp chồng lên nhau. Hàm được gọi với 

def countdown(n):
    print(n)
    if n > 0:
        countdown(n - 1)
0 = 
def countdown(n):
    print(n)
    if n > 0:
        countdown(n - 1)
8, 
def countdown(n):
    print(n)
    if n > 0:
        countdown(n - 1)
9, 
>>> def countdown(n):
..     while n >= 0:
..         print(n)
..         n -= 1
...

>>> countdown(5)
5
4
3
2
1
0
0 và 
>>> def countdown(n):
..     while n >= 0:
..         print(n)
..         n -= 1
...

>>> countdown(5)
5
4
3
2
1
0
1 trước khi bất kỳ lệnh gọi nào trả về. Cuối cùng, khi 
def countdown(n):
    print(n)
    if n > 0:
        countdown(n - 1)
0 là 
>>> def countdown(n):
..     while n >= 0:
..         print(n)
..         n -= 1
...

>>> countdown(5)
5
4
3
2
1
0
1, vấn đề có thể được giải quyết mà không cần đệ quy nữa. Sau đó, mỗi lệnh gọi đệ quy được xếp chồng lên nhau sẽ thoát ra ngoài, trả về 
>>> def countdown(n):
..     while n >= 0:
..         print(n)
..         n -= 1
...

>>> countdown(5)
5
4
3
2
1
0
1, 
>>> def countdown(n):
..     while n >= 0:
..         print(n)
..         n -= 1
...

>>> countdown(5)
5
4
3
2
1
0
0, 
>>> def countdown(n):
..     while n >= 0:
..         print(n)
..         n -= 1
...

>>> countdown(5)
5
4
3
2
1
0
6 và cuối cùng là 
>>> def countdown(n):
..     while n >= 0:
..         print(n)
..         n -= 1
...

>>> countdown(5)
5
4
3
2
1
0
7 từ lệnh gọi ngoài cùng

Đệ quy không cần thiết ở đây. Bạn có thể triển khai lặp đi lặp lại 

>>> def countdown(n):
..     while n >= 0:
..         print(n)
..         n -= 1
...

>>> countdown(5)
5
4
3
2
1
0
8 bằng cách sử dụng vòng lặp 
>>> def countdown(n):
..     while n >= 0:
..         print(n)
..         n -= 1
...

>>> countdown(5)
5
4
3
2
1
0
9

>>> 

>>> def factorial(n):
..     return_value = 1
..     for i in range(2, n + 1):
..         return_value *= i
..     return return_value
...

>>> factorial(4)
24

Bạn cũng có thể triển khai giai thừa bằng cách sử dụng 

>>> def factorial(n):
..     return 1 if n <= 1 else n * factorial(n - 1)
...

>>> factorial(4)
24
0 của Python, mà bạn có thể nhập từ mô-đun 
>>> def factorial(n):
..     return 1 if n <= 1 else n * factorial(n - 1)
...

>>> factorial(4)
24
1

>>> 

>>> function()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
0

Một lần nữa, điều này cho thấy rằng nếu một vấn đề có thể giải quyết được bằng đệ quy, thì cũng có khả năng sẽ có một số giải pháp không đệ quy khả thi. Thông thường, bạn sẽ chọn dựa trên cái nào dẫn đến mã trực quan và dễ đọc nhất

Một yếu tố khác cần xem xét là tốc độ thực thi. Có thể có sự khác biệt đáng kể về hiệu suất giữa các giải pháp đệ quy và không đệ quy. Trong phần tiếp theo, bạn sẽ khám phá thêm một chút về những khác biệt này

So sánh tốc độ triển khai giai thừa

Để đánh giá thời gian thực hiện, bạn có thể sử dụng một chức năng được gọi từ một mô-đun cũng được gọi là 

>>> def factorial(n):
..     return 1 if n <= 1 else n * factorial(n - 1)
...

>>> factorial(4)
24
3. Chức năng này hỗ trợ một số định dạng khác nhau, nhưng bạn sẽ sử dụng định dạng sau trong hướng dẫn này

>>> function()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
1

>>> def factorial(n):
..     return 1 if n <= 1 else n * factorial(n - 1)
...

>>> factorial(4)
24
2 đầu tiên thực hiện các lệnh có trong 
>>> def factorial(n):
..     return 1 if n <= 1 else n * factorial(n - 1)
...

>>> factorial(4)
24
5 đã chỉ định. Sau đó, nó thực thi 
>>> def factorial(n):
..     return 1 if n <= 1 else n * factorial(n - 1)
...

>>> factorial(4)
24
6 số đã cho của 
>>> def factorial(n):
..     return 1 if n <= 1 else n * factorial(n - 1)
...

>>> factorial(4)
24
7 và báo cáo thời gian thực hiện tích lũy tính bằng giây

>>> 

>>> function()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
2

Ở đây, tham số 

>>> def factorial(n):
..     return 1 if n <= 1 else n * factorial(n - 1)
...

>>> factorial(4)
24
8 gán cho 
>>> def factorial(n):
..     return 1 if n <= 1 else n * factorial(n - 1)
...

>>> factorial(4)
24
9 giá trị 
>>> def factorial(n):
..     print(f"factorial() called with n = {n}")
..     return_value = 1 if n <= 1 else n * factorial(n -1)
..     print(f"-> factorial({n}) returns {return_value}")
..     return return_value
...

>>> factorial(4)
factorial() called with n = 4
factorial() called with n = 3
factorial() called with n = 2
factorial() called with n = 1
-> factorial(1) returns 1
-> factorial(2) returns 2
-> factorial(3) returns 6
-> factorial(4) returns 24
24
0. Sau đó, 
>>> def factorial(n):
..     return 1 if n <= 1 else n * factorial(n - 1)
...

>>> factorial(4)
24
2 in 
>>> def factorial(n):
..     return 1 if n <= 1 else n * factorial(n - 1)
...

>>> factorial(4)
24
9 một trăm lần. Tổng thời gian thực hiện chỉ hơn 3/100 giây

Các ví dụ hiển thị bên dưới sử dụng 

>>> def factorial(n):
..     return 1 if n <= 1 else n * factorial(n - 1)
...

>>> factorial(4)
24
2 để so sánh các triển khai đệ quy, lặp lại và 
>>> def factorial(n):
..     return 1 if n <= 1 else n * factorial(n - 1)
...

>>> factorial(4)
24
0 của giai thừa từ bên trên. Trong mỗi trường hợp, 
>>> def factorial(n):
..     print(f"factorial() called with n = {n}")
..     return_value = 1 if n <= 1 else n * factorial(n -1)
..     print(f"-> factorial({n}) returns {return_value}")
..     return return_value
...

>>> factorial(4)
factorial() called with n = 4
factorial() called with n = 3
factorial() called with n = 2
factorial() called with n = 1
-> factorial(1) returns 1
-> factorial(2) returns 2
-> factorial(3) returns 6
-> factorial(4) returns 24
24
5 chứa một chuỗi thiết lập xác định hàm 
>>> def countdown(n):
..     while n >= 0:
..         print(n)
..         n -= 1
...

>>> countdown(5)
5
4
3
2
1
0
8 có liên quan. 
>>> def factorial(n):
..     return 1 if n <= 1 else n * factorial(n - 1)
...

>>> factorial(4)
24
2 sau đó thực thi 
>>> def factorial(n):
..     print(f"factorial() called with n = {n}")
..     return_value = 1 if n <= 1 else n * factorial(n -1)
..     print(f"-> factorial({n}) returns {return_value}")
..     return return_value
...

>>> factorial(4)
factorial() called with n = 4
factorial() called with n = 3
factorial() called with n = 2
factorial() called with n = 1
-> factorial(1) returns 1
-> factorial(2) returns 2
-> factorial(3) returns 6
-> factorial(4) returns 24
24
8 tổng cộng mười triệu lần và báo cáo việc thực hiện tổng hợp

Đầu tiên, đây là phiên bản đệ quy

>>> 

>>> function()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
3

Tiếp theo là thực hiện lặp đi lặp lại

>>> 

>>> function()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
4

Cuối cùng, đây là phiên bản sử dụng 

>>> def factorial(n):
..     return 1 if n <= 1 else n * factorial(n - 1)
...

>>> factorial(4)
24
0

>>> 

>>> function()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
5

Trong trường hợp này, việc triển khai lặp lại là nhanh nhất, mặc dù giải pháp đệ quy không thua xa. Phương pháp sử dụng 

>>> def factorial(n):
..     return 1 if n <= 1 else n * factorial(n - 1)
...

>>> factorial(4)
24
0 là chậm nhất. Số dặm của bạn có thể sẽ thay đổi nếu bạn thử các ví dụ này trên máy của chính mình. Bạn chắc chắn sẽ không nhận được cùng thời gian và thậm chí bạn có thể không nhận được cùng thứ hạng

Nó có quan trọng không?

Nếu bạn sẽ gọi một chức năng nhiều lần, bạn có thể cần tính đến tốc độ thực thi khi chọn cách triển khai. Mặt khác, nếu chức năng sẽ chạy tương đối không thường xuyên, thì sự khác biệt về thời gian thực hiện có thể sẽ không đáng kể. Trong trường hợp đó, tốt hơn hết bạn nên chọn cách triển khai có vẻ thể hiện giải pháp cho vấn đề một cách rõ ràng nhất

Đối với giai thừa, thời gian được ghi ở trên cho thấy việc triển khai đệ quy là một lựa chọn hợp lý

Thành thật mà nói, nếu bạn đang viết mã bằng Python, bạn hoàn toàn không cần triển khai hàm giai thừa. Nó đã có sẵn trong mô-đun 

>>> def factorial(n):
..     return_value = 1
..     for i in range(2, n + 1):
..         return_value *= i
..     return return_value
...

>>> factorial(4)
24
2 tiêu chuẩn

>>> 

>>> function()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
6

Có lẽ bạn sẽ quan tâm để biết điều này hoạt động như thế nào trong bài kiểm tra thời gian

>>> 

>>> function()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
7

Ồ. 

>>> def factorial(n):
..     return_value = 1
..     for i in range(2, n + 1):
..         return_value *= i
..     return return_value
...

>>> factorial(4)
24
3 hoạt động tốt hơn so với cách triển khai tốt nhất trong số ba cách triển khai khác được trình bày ở trên gần gấp 10 lần

lưu ý kỹ thuật. Thực tế là 

>>> def factorial(n):
..     return_value = 1
..     for i in range(2, n + 1):
..         return_value *= i
..     return return_value
...

>>> factorial(4)
24
3 nhanh hơn rất nhiều có lẽ không liên quan gì đến việc nó có được triển khai đệ quy hay không. Nhiều khả năng là do hàm được triển khai bằng C chứ không phải Python. Để đọc thêm về Python và C, hãy xem các tài nguyên này

  • Ràng buộc Python. Gọi C hoặc C++ từ Python
  • Xây dựng Mô-đun mở rộng Python C
  • C cho lập trình viên Python
  • Hướng dẫn của bạn về mã nguồn CPython
  • Sách nội bộ CPython

Một chức năng được triển khai trong C hầu như sẽ luôn nhanh hơn một chức năng tương ứng được triển khai trong Python thuần túy

Loại bỏ các quảng cáo

Duyệt một danh sách lồng nhau

Ví dụ tiếp theo liên quan đến việc truy cập từng mục trong cấu trúc danh sách lồng nhau. Hãy xem xét Python sau

>>> function()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
8

Như sơ đồ sau đây cho thấy, 

>>> def factorial(n):
..     return_value = 1
..     for i in range(2, n + 1):
..         return_value *= i
..     return return_value
...

>>> factorial(4)
24
5 chứa hai danh sách con. Bản thân danh sách con đầu tiên chứa một danh sách con khác

In 1 đến 10 bằng đệ quy trong python

Giả sử bạn muốn đếm số phần tử lá trong danh sách này—các đối tượng 

>>> def factorial(n):
..     return_value = 1
..     for i in range(2, n + 1):
..         return_value *= i
..     return return_value
...

>>> factorial(4)
24
6 cấp thấp nhất—như thể bạn đã làm phẳng danh sách. Các phần tử lá là 
>>> def factorial(n):
..     return_value = 1
..     for i in range(2, n + 1):
..         return_value *= i
..     return return_value
...

>>> factorial(4)
24
7, 
>>> def factorial(n):
..     return_value = 1
..     for i in range(2, n + 1):
..         return_value *= i
..     return return_value
...

>>> factorial(4)
24
8, 
>>> def factorial(n):
..     return_value = 1
..     for i in range(2, n + 1):
..         return_value *= i
..     return return_value
...

>>> factorial(4)
24
9, 
>>> function()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
00, 
>>> function()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
01, 
>>> function()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
02, 
>>> function()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
03, 
>>> function()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
04, 
>>> function()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
05, và 
>>> function()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
06, vì vậy câu trả lời phải là 
>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000
6

Chỉ gọi 

>>> function()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
08 trong danh sách không đưa ra câu trả lời chính xác

>>> 

>>> function()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
9

>>> function()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
08 đếm các đối tượng ở cấp cao nhất của 
>>> def factorial(n):
..     return_value = 1
..     for i in range(2, n + 1):
..         return_value *= i
..     return return_value
...

>>> factorial(4)
24
5, đó là ba phần tử lá 
>>> def factorial(n):
..     return_value = 1
..     for i in range(2, n + 1):
..         return_value *= i
..     return return_value
...

>>> factorial(4)
24
7, 
>>> function()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
03, và 
>>> function()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
06 và hai danh sách con 
>>> function()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
14 và 
>>> function()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
15

>>> 

>>> from sys import getrecursionlimit
>>> getrecursionlimit()
1000
0

Những gì bạn cần ở đây là một chức năng duyệt qua toàn bộ cấu trúc danh sách, bao gồm cả danh sách con. Thuật toán diễn ra như thế này

  1. Đi qua danh sách, kiểm tra lần lượt từng mục
  2. Nếu bạn tìm thấy một phần tử lá, sau đó thêm nó vào số lượng tích lũy
  3. Nếu gặp sublist thì làm như sau
    • Thả xuống danh sách phụ đó và tương tự đi qua nó
    • Sau khi bạn đã sử dụng hết danh sách phụ, hãy quay lại, thêm các phần tử từ danh sách phụ vào tổng số tích lũy và tiếp tục duyệt qua danh sách gốc mà bạn đã dừng lại

Lưu ý bản chất tự giới thiệu của mô tả này. Đi qua danh sách. Nếu bạn gặp một danh sách phụ, thì hãy đi qua danh sách đó một cách tương tự. Tình huống này yêu cầu đệ quy

Duyệt qua danh sách lồng nhau theo cách đệ quy

Đệ quy phù hợp với vấn đề này rất độc đáo. Để giải quyết nó, bạn cần có khả năng xác định xem một mục danh sách nhất định có phải là mục lá hay không. Để làm được điều đó, bạn có thể sử dụng hàm Python tích hợp

Trong trường hợp của danh sách 

>>> def factorial(n):
..     return_value = 1
..     for i in range(2, n + 1):
..         return_value *= i
..     return return_value
...

>>> factorial(4)
24
5, nếu một mục là một thể hiện của loại 
>>> function()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
18, thì đó là một danh sách con. Mặt khác, nó là một mục lá

>>> 

>>> from sys import getrecursionlimit
>>> getrecursionlimit()
1000
1

Bây giờ bạn đã có sẵn các công cụ để triển khai một hàm đếm các phần tử lá trong danh sách, chiếm các danh sách con theo cách đệ quy

>>> from sys import getrecursionlimit
>>> getrecursionlimit()
1000
2

Nếu bạn chạy 

>>> function()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
19 trên một số danh sách, bao gồm danh sách 
>>> def factorial(n):
..     return_value = 1
..     for i in range(2, n + 1):
..         return_value *= i
..     return return_value
...

>>> factorial(4)
24
5 được xác định ở trên, bạn sẽ nhận được điều này

>>> 

>>> from sys import getrecursionlimit
>>> getrecursionlimit()
1000
3

Như với ví dụ giai thừa, việc thêm một số câu lệnh 

def countdown(n):
    print(n)
    if n > 0:
        countdown(n - 1)
6 giúp chứng minh chuỗi các cuộc gọi đệ quy và giá trị trả về

>>> from sys import getrecursionlimit
>>> getrecursionlimit()
1000
4

Đây là một bản tóm tắt về những gì đang xảy ra trong ví dụ trên

  • Dòng 9. 
    >>> function()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
    22 là 
    >>> function()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
    23, vì vậy 
    >>> function()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
    19 đã tìm thấy một danh sách phụ
  • Dòng 11. Hàm tự gọi đệ quy để đếm các mục trong danh sách con, sau đó thêm kết quả vào tổng tích lũy
  • Dòng 12. 
    >>> function()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
    22 là 
    >>> function()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
    26, vì vậy 
    >>> function()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
    19 đã gặp phải mục lá
  • Dòng 14. Hàm tăng tổng tích lũy lên một để tính cho mục lá

Ghi chú. Để đơn giản hóa, việc triển khai này giả định danh sách được chuyển đến 

>>> function()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
19 chỉ chứa các mục lá hoặc danh sách con, không chứa bất kỳ loại đối tượng tổng hợp nào khác như từ điển hoặc

Đầu ra từ 

>>> function()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
19 khi nó được thực thi trên danh sách 
>>> def factorial(n):
..     return_value = 1
..     for i in range(2, n + 1):
..         return_value *= i
..     return return_value
...

>>> factorial(4)
24
5 bây giờ trông như thế này

>>> 

>>> from sys import getrecursionlimit
>>> getrecursionlimit()
1000
5

Mỗi khi cuộc gọi đến ____10_______19 kết thúc, nó sẽ trả về số lượng phần tử lá mà nó đã kiểm tra trong danh sách được truyền cho nó. Cuộc gọi cấp cao nhất trả về 

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000
6, vì lẽ ra

Loại bỏ các quảng cáo

Duyệt một danh sách lồng nhau không đệ quy

Giống như các ví dụ khác được hiển thị cho đến nay, việc duyệt qua danh sách này không yêu cầu đệ quy. Bạn cũng có thể hoàn thành nó lặp đi lặp lại. Đây là một khả năng

>>> from sys import getrecursionlimit
>>> getrecursionlimit()
1000
6

Nếu bạn chạy phiên bản không đệ quy này của 

>>> function()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
19 trên cùng một danh sách như được hiển thị trước đó, bạn sẽ nhận được kết quả tương tự

>>> 

>>> from sys import getrecursionlimit
>>> getrecursionlimit()
1000
3

Chiến lược được sử dụng ở đây sử dụng một ngăn xếp để xử lý các danh sách con lồng nhau. Khi phiên bản này của 

>>> function()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
19 gặp một danh sách phụ, nó sẽ đẩy danh sách đang được xử lý và chỉ mục hiện tại trong danh sách đó lên một ngăn xếp. Khi nó đã đếm danh sách con, hàm sẽ bật danh sách mẹ và chỉ mục khỏi ngăn xếp để nó có thể tiếp tục đếm ở nơi nó dừng lại

Trên thực tế, về cơ bản, điều tương tự cũng xảy ra trong quá trình triển khai đệ quy. Khi bạn gọi một hàm theo cách đệ quy, Python sẽ lưu trạng thái của phiên bản đang thực thi trên một ngăn xếp để cuộc gọi đệ quy có thể chạy. Khi cuộc gọi đệ quy kết thúc, trạng thái được bật ra khỏi ngăn xếp để phiên bản bị gián đoạn có thể tiếp tục. Đó là cùng một khái niệm, nhưng với giải pháp đệ quy, Python đang thực hiện công việc tiết kiệm trạng thái cho bạn

Lưu ý mức độ ngắn gọn và dễ đọc của mã đệ quy khi so sánh với phiên bản không đệ quy

In 1 đến 10 bằng đệ quy trong python
Truyền tải danh sách lồng nhau đệ quy và không đệ quy

Đây là trường hợp sử dụng đệ quy chắc chắn là một lợi thế

Phát hiện Palindromes

Việc lựa chọn có sử dụng đệ quy để giải quyết vấn đề hay không phụ thuộc phần lớn vào bản chất của vấn đề. Ví dụ, thừa số tự nhiên chuyển thành cách thực hiện đệ quy, nhưng giải pháp lặp lại cũng khá đơn giản. Trong trường hợp đó, nó được cho là một sự tung lên

Vấn đề duyệt danh sách là một câu chuyện khác. Trong trường hợp đó, giải pháp đệ quy rất tao nhã, trong khi giải pháp không đệ quy là cồng kềnh nhất

Đối với vấn đề tiếp theo, sử dụng đệ quy được cho là ngớ ngẩn

Palindrome là một từ đọc ngược giống như đọc xuôi. Ví dụ bao gồm các từ sau

  • Xe đua
  • Cấp độ
  • Chèo xuồng
  • người hồi sinh
  • công dân

Nếu được yêu cầu nghĩ ra một thuật toán để xác định xem một chuỗi có phải là đối xứng hay không, có lẽ bạn sẽ nghĩ ra thứ gì đó như “Đảo ngược chuỗi và xem nó có giống với chuỗi ban đầu không. ” Bạn không thể nhận được nhiều đơn giản hơn thế

Thậm chí hữu ích hơn, cú pháp cắt lát 

>>> function()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
35 của Python để đảo ngược chuỗi cung cấp một cách thuận tiện để mã hóa nó

>>> 

>>> from sys import getrecursionlimit
>>> getrecursionlimit()
1000
8

Điều này là rõ ràng và ngắn gọn. Hầu như không cần tìm kiếm giải pháp thay thế. Nhưng để giải trí, hãy xem xét định nghĩa đệ quy này của một bảng màu

  • trường hợp cơ sở. Một chuỗi rỗng và một chuỗi bao gồm một ký tự đơn lẻ vốn dĩ là palindromic
  • đệ quy rút gọn. Một chuỗi có độ dài bằng hai hoặc lớn hơn là một đối xứng nếu nó thỏa mãn cả hai tiêu chí này
    1. Ký tự đầu và cuối giống nhau
    2. Chuỗi con giữa ký tự đầu tiên và ký tự cuối cùng là một bảng màu

Cắt lát cũng là bạn của bạn ở đây. Đối với một chuỗi 

>>> function()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
36, lập chỉ mục và cắt cho các chuỗi con sau

  • Ký tự đầu tiên là 
    >>> function()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
    37
  • Ký tự cuối cùng là 
    >>> function()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
    38
  • Chuỗi con giữa ký tự đầu tiên và ký tự cuối cùng là 
    >>> function()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
    39

Vì vậy, bạn có thể định nghĩa đệ quy 

>>> function()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
40 như thế này

>>> 

>>> from sys import getrecursionlimit
>>> getrecursionlimit()
1000
9

Đó là một bài tập thú vị để suy nghĩ theo cách đệ quy, ngay cả khi nó không đặc biệt cần thiết

Loại bỏ các quảng cáo

Sắp xếp với Quicksort

Ví dụ cuối cùng được trình bày, giống như duyệt danh sách lồng nhau, là một ví dụ điển hình về một vấn đề gợi ý một cách tiếp cận đệ quy một cách rất tự nhiên. Đây là một thuật toán sắp xếp hiệu quả được phát triển bởi nhà khoa học máy tính người Anh Tony Hoare vào năm 1959

Quicksort là thuật toán chia để trị. Giả sử bạn có một danh sách các đối tượng để sắp xếp. Bạn bắt đầu bằng cách chọn một mục trong danh sách, được gọi là mục trục. Đây có thể là bất kỳ mục nào trong danh sách. Sau đó, bạn phân vùng danh sách thành hai danh sách con dựa trên mục trục và sắp xếp đệ quy các danh sách con

Các bước của thuật toán như sau

  • Chọn mục trục
  • Phân vùng danh sách thành hai danh sách con
    1. Những mặt hàng nhỏ hơn mặt hàng trục
    2. Những mục lớn hơn mục trục
  • Sắp xếp nhanh các danh sách con theo cách đệ quy

Mỗi phân vùng tạo ra các danh sách con nhỏ hơn, vì vậy thuật toán được rút gọn. Các trường hợp cơ sở xảy ra khi các danh sách con trống hoặc có một phần tử, vì chúng vốn đã được sắp xếp

Chọn mục Pivot

Thuật toán Quicksort sẽ hoạt động bất kể mục nào trong danh sách là mục trục. Nhưng một số lựa chọn tốt hơn những lựa chọn khác. Hãy nhớ rằng khi phân vùng, hai danh sách con được tạo. một với các mục nhỏ hơn mục trục và một với các mục lớn hơn mục trục. Lý tưởng nhất là hai danh sách con có độ dài gần bằng nhau

Hãy tưởng tượng rằng danh sách ban đầu của bạn để sắp xếp có tám mục. Nếu mỗi phân vùng dẫn đến các danh sách con có độ dài gần bằng nhau, thì bạn có thể tiếp cận các trường hợp cơ bản trong ba bước

In 1 đến 10 bằng đệ quy trong python
Phân vùng tối ưu, danh sách tám mục

Ở đầu kia của quang phổ, nếu sự lựa chọn mục trục của bạn đặc biệt không may mắn, thì mỗi phân vùng sẽ dẫn đến một danh sách con chứa tất cả các mục ban đầu ngoại trừ mục trục và một danh sách con khác trống. Trong trường hợp đó, phải mất bảy bước để rút gọn danh sách thành các trường hợp cơ bản

In 1 đến 10 bằng đệ quy trong python
Phân vùng dưới mức tối ưu, Danh sách tám mục

Thuật toán Quicksort sẽ hiệu quả hơn trong trường hợp đầu tiên. Nhưng bạn cần biết trước một số điều về bản chất của dữ liệu bạn đang sắp xếp để chọn các mục trục tối ưu một cách có hệ thống. Trong mọi trường hợp, không có sự lựa chọn nào là tốt nhất cho mọi trường hợp. Vì vậy, nếu bạn đang viết một hàm Quicksort để xử lý trường hợp chung, thì việc lựa chọn mục trục có phần tùy ý

Mục đầu tiên trong danh sách là một lựa chọn phổ biến, cũng như mục cuối cùng. Chúng sẽ hoạt động tốt nếu dữ liệu trong danh sách được phân phối khá ngẫu nhiên. Tuy nhiên, nếu dữ liệu đã được sắp xếp hoặc thậm chí gần như vậy, thì những dữ liệu này sẽ dẫn đến phân vùng dưới mức tối ưu như được hiển thị ở trên. Để tránh điều này, một số thuật toán Quicksort chọn mục ở giữa trong danh sách làm mục trục

Một tùy chọn khác là tìm trung vị của các mục đầu tiên, cuối cùng và ở giữa trong danh sách và sử dụng mục đó làm mục xoay vòng. Đây là chiến lược được sử dụng trong mã mẫu bên dưới

Thực hiện phân vùng

Khi bạn đã chọn mục trục, bước tiếp theo là phân vùng danh sách. Một lần nữa, mục tiêu là tạo hai danh sách phụ, một danh sách chứa các mục nhỏ hơn mục trục và danh sách còn lại chứa các mục lớn hơn

Bạn có thể thực hiện điều này trực tiếp tại chỗ. Nói cách khác, bằng cách hoán đổi các mục, bạn có thể xáo trộn các mục trong danh sách xung quanh cho đến khi mục trục nằm ở giữa, tất cả các mục nhỏ hơn ở bên trái và tất cả các mục lớn hơn ở bên phải. Sau đó, khi bạn sắp xếp nhanh các danh sách con theo cách đệ quy, bạn sẽ chuyển các phần của danh sách sang bên trái và bên phải của mục trục

Ngoài ra, bạn có thể sử dụng khả năng thao tác danh sách của Python để tạo danh sách mới thay vì thao tác trên danh sách ban đầu tại chỗ. Đây là cách tiếp cận được thực hiện trong đoạn mã dưới đây. Thuật toán như sau

  • Chọn mục trục bằng phương pháp trung bình của ba được mô tả ở trên
  • Sử dụng mục trục, tạo ba danh sách phụ
    1. Các mục trong danh sách ban đầu nhỏ hơn mục trục
    2. Bản thân mục trục
    3. Các mục trong danh sách ban đầu lớn hơn mục trục
  • Danh sách Quicksort đệ quy 1 và 3
  • Nối cả ba danh sách lại với nhau

Lưu ý rằng điều này liên quan đến việc tạo danh sách con thứ ba chứa chính mục trục. Một lợi thế của phương pháp này là nó xử lý trơn tru trường hợp mục trục xuất hiện trong danh sách nhiều lần. Trong trường hợp đó, danh sách 2 sẽ có nhiều hơn một phần tử

Loại bỏ các quảng cáo

Sử dụng Triển khai Quicksort

Bây giờ nền tảng đã sẵn sàng, bạn đã sẵn sàng chuyển sang thuật toán Quicksort. Đây là mã Python

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000
0

Đây là những gì mỗi phần của 

>>> function()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
41 đang làm

  • Dòng 4. Các trường hợp cơ bản khi danh sách trống hoặc chỉ có một phần tử
  • Dòng 7 đến 13. Tính toán mục trục theo phương pháp trung bình của ba
  • Dòng 14 đến 18. Tạo ba danh sách phân vùng
  • Dòng 20 đến 24. Sắp xếp đệ quy và sắp xếp lại danh sách phân vùng

Ghi chú. Ví dụ này có ưu điểm là ngắn gọn và tương đối dễ đọc. Tuy nhiên, đó không phải là cách triển khai hiệu quả nhất. Cụ thể, việc tạo danh sách phân vùng trên các dòng 14 đến 18 liên quan đến việc lặp qua danh sách ba lần riêng biệt, điều này không tối ưu từ quan điểm về thời gian thực hiện

Dưới đây là một số ví dụ về 

>>> function()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
41 đang hoạt động

>>> 

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000
1

Đối với mục đích thử nghiệm, bạn có thể xác định một hàm ngắn để tạo danh sách các số ngẫu nhiên giữa 

>>> def countdown(n):
..     while n >= 0:
..         print(n)
..         n -= 1
...

>>> countdown(5)
5
4
3
2
1
0
1 và 
>>> function()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
44

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000
2

Bây giờ bạn có thể sử dụng 

>>> function()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
45 để kiểm tra 
>>> function()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
41

>>> 

>>> from sys import setrecursionlimit
>>> setrecursionlimit(2000)
>>> getrecursionlimit()
2000
3

Để hiểu rõ hơn về cách thức hoạt động của 

>>> function()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
41, hãy xem sơ đồ bên dưới. Điều này cho thấy trình tự đệ quy khi sắp xếp danh sách mười hai phần tử

In 1 đến 10 bằng đệ quy trong python
Thuật toán Quicksort, Danh sách 12 phần tử

Trong bước đầu tiên, các giá trị danh sách đầu tiên, giữa và cuối cùng lần lượt là 

>>> function()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
48, 
>>> function()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
49 và 
>>> function()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
50. Giá trị trung bình là 
>>> function()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
48, do đó giá trị đó trở thành mục xoay vòng. Phân vùng đầu tiên sau đó bao gồm các danh sách con sau

Các mục trong danh sách con

>>> function()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
52Các mục nhỏ hơn mục xoay vòng
>>> function()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
53Bản thân mục xoay vòng
>>> function()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
54Các mục lớn hơn mục xoay vòng

Mỗi danh sách con sau đó được phân vùng đệ quy theo cùng một cách cho đến khi tất cả các danh sách con chứa một phần tử hoặc trống. Khi các cuộc gọi đệ quy trở lại, các danh sách được sắp xếp lại theo thứ tự được sắp xếp. Lưu ý rằng trong bước thứ hai đến bước cuối cùng ở bên trái, mục xoay vòng 

>>> function()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  File "<stdin>", line 3, in function
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
55 xuất hiện trong danh sách hai lần, do đó, danh sách mục xoay vòng có hai phần tử

Phần kết luận

Điều đó kết thúc hành trình của bạn thông qua đệ quy, một kỹ thuật lập trình trong đó một hàm gọi chính nó. Đệ quy không phải lúc nào cũng phù hợp với mọi nhiệm vụ. Nhưng một số vấn đề lập trình gần như kêu cứu. Trong những tình huống đó, đó là một kỹ thuật tuyệt vời để bạn tùy ý sử dụng

Trong hướng dẫn này, bạn đã học

  • Ý nghĩa của việc một hàm gọi chính nó một cách đệ quy
  • Cách thiết kế các hàm Python hỗ trợ đệ quy
  • Những yếu tố cần xem xét khi lựa chọn có hay không giải quyết vấn đề theo cách đệ quy
  • Cách triển khai hàm đệ quy trong Python

Bạn cũng đã xem một số ví dụ về thuật toán đệ quy và so sánh chúng với các giải pháp không đệ quy tương ứng

Bây giờ bạn sẽ ở một vị trí thuận lợi để nhận ra khi nào đệ quy được yêu cầu và sẵn sàng sử dụng nó một cách tự tin khi cần thiết. Nếu bạn muốn khám phá thêm về đệ quy trong Python, hãy xem Tư duy đệ quy trong Python

Đánh dấu là đã hoàn thành

🐍 Thủ thuật Python 💌

Nhận một Thủ thuật Python ngắn và hấp dẫn được gửi đến hộp thư đến của bạn vài ngày một lần. Không có thư rác bao giờ. Hủy đăng ký bất cứ lúc nào. Được quản lý bởi nhóm Real Python

In 1 đến 10 bằng đệ quy trong python

Gửi cho tôi thủ thuật Python »

Giới thiệu về John Sturtz

In 1 đến 10 bằng đệ quy trong python
In 1 đến 10 bằng đệ quy trong python

John là một Pythonista cuồng nhiệt và là thành viên của nhóm hướng dẫn Real Python

» Thông tin thêm về John

Mỗi hướng dẫn tại Real Python được tạo bởi một nhóm các nhà phát triển để nó đáp ứng các tiêu chuẩn chất lượng cao của chúng tôi. Các thành viên trong nhóm đã làm việc trong hướng dẫn này là

In 1 đến 10 bằng đệ quy trong python

Aldren

In 1 đến 10 bằng đệ quy trong python

Bartosz

In 1 đến 10 bằng đệ quy trong python

Joanna

In 1 đến 10 bằng đệ quy trong python

Gia-cốp

Bậc thầy Kỹ năng Python trong thế giới thực Với quyền truy cập không giới hạn vào Python thực

Tham gia với chúng tôi và có quyền truy cập vào hàng nghìn hướng dẫn, khóa học video thực hành và cộng đồng các Pythonistas chuyên gia

Nâng cao kỹ năng Python của bạn »

Chuyên gia Kỹ năng Python trong thế giới thực
Với quyền truy cập không giới hạn vào Python thực

Tham gia với chúng tôi và có quyền truy cập vào hàng ngàn hướng dẫn, khóa học video thực hành và cộng đồng Pythonistas chuyên gia

Nâng cao kỹ năng Python của bạn »

Bạn nghĩ sao?

Đánh giá bài viết này

Tweet Chia sẻ Chia sẻ Email

Bài học số 1 hoặc điều yêu thích mà bạn đã học được là gì?

Mẹo bình luận. Những nhận xét hữu ích nhất là những nhận xét được viết với mục đích học hỏi hoặc giúp đỡ các sinh viên khác. và nhận câu trả lời cho các câu hỏi phổ biến trong cổng thông tin hỗ trợ của chúng tôi

Làm cách nào để in 1 đến 10 bằng cách sử dụng đệ quy trong Python?

countdown(n-1) #đây là đệ quy (gọi chính nó). print(n) #in các số. đếm ngược(10) # đối số chức năng. .
Bạn không phải trả lại bất cứ thứ gì từ hàm đệ quy chỉ in các giá trị
Để in theo thứ tự tăng dần, câu lệnh in phải được đặt sau lệnh gọi đệ quy

Làm cách nào để in 1 đến n bằng đệ quy?

Ví dụ .
# python3 chương trình in 1 đến n bằng đệ quy
def printNumber(n)
# kiểm tra xem n có lớn hơn 0 không
nếu n > 0
# gọi đệ quy hàm printNumber
inNumber(n - 1)
#in n

Làm cách nào để in 1 đến 10 bằng đệ quy trong C?

Hàm display() bên trong . Trong khối khác, chúng tôi viết điều kiện cơ sở, nghĩa là trả lại điều khiển cho hàm gọi nếu num bằng 0. Điều này in các số tự nhiên từ 1 đến giới hạn đầu vào của người dùng

Làm cách nào để in từ 1 đến 10 bằng cách sử dụng đệ quy trong Java?

Chương trình Java in N số tự nhiên đầu tiên bằng cách sử dụng đệ quy .
nhập java. sử dụng. Máy quét;
hạng phổ thông Tự nhiên
public static void main(String[] args)
số nguyên;
Máy quét s = Máy quét mới(Hệ thống. Trong);
Hệ thống. ngoài. print("Nhập số bất kỳ. ");

programming python

Bài Viết Liên Quan

Chữ hoa trong Python là gì?
Chữ hoa trong Python là gì?

Đọc và viết bằng Python là gì?
Đọc và viết bằng Python là gì?

Cách lấy mảng ngày trong JavaScript?
Cách lấy mảng ngày trong JavaScript?

Viết chương trình in ra tất cả các ước của một số n (với n được nhập từ bàn phím)
Viết chương trình in ra tất cả các ước của một số n (với n được nhập từ bàn phím)

Bao nhiêu nước có chung biển Đông?
Bao nhiêu nước có chung biển Đông?

Chuỗi nguyên tử python
Chuỗi nguyên tử python

Làm cách nào để lưu trữ ngày trong MySQL bằng php?
Làm cách nào để lưu trữ ngày trong MySQL bằng php?

HTML thay đổi màu sắc của văn bản dựa trên giá trị
HTML thay đổi màu sắc của văn bản dựa trên giá trị

Cách in nhiều file Excel cùng lúc
Cách in nhiều file Excel cùng lúc

Khu B tuyển dụng 2023
Khu B tuyển dụng 2023

MỚI CẬP NHẬP

Bầu đức là gì của cường đôla năm 2024
6 phúts trước . bởi StaleFunction
Viết đoạn văn về phim bằng tiếng anh năm 2024
21 phúts trước . bởi ImpassiveNervousness
Văn bản là gì lớp 6 năm 2024
36 phúts trước . bởi DiscerniblePolling
Download đề thi vào lớp 10 môn toán năm 2024
48 phúts trước . bởi SickCompetition
Sách giải sách bài tập toán lớp 8 tập 1 năm 2024
1 giờs trước . bởi AppropriateNervousness
Bagi văn kể lai tâm trạng của ông hai năm 2024
1 giờs trước . bởi Blue-chipCriminality
Đường trung bình của hình thang bài 28 năm 2024
1 giờs trước . bởi ShrewdAccessibility
Cư xử đúng mực là gì năm 2024
1 giờs trước . bởi PitchedSelf-control
Tuyển đánh văn bản thuê tại nhà 2023 năm 2024
2 giờs trước . bởi UnconsciousOverseer
Trẻ ra mồ hôi trộm là thiếu chất gì năm 2024
2 giờs trước . bởi Nine-year-oldRegularity

Xem Nhiều

Chúng ta cùng cảnh ngộ nghĩa tiếng anh là gì năm 2024
5 ngàys trước . bởi CoronaryClerk
Chứng khoán có dấu sao nghĩa là gì năm 2024
5 ngàys trước . bởi GrainyDwelling
Top 20 view của bts twice và black pink youtube năm 2024
1 tuầns trước . bởi SolicitousArchitecture
On the weekend là thì gì năm 2024
3 ngàys trước . bởi FierceCovering
Co số điện thoại di động nào 9 đó năm 2024
1 ngàys trước . bởi SilverTo-day
Himax premium lub ts40 là gì năm 2024
1 ngàys trước . bởi DeepeningMirth
81 2 nguyễn văn giai quận 1 f dakao năm 2024
1 ngàys trước . bởi First-rateMedics
Lỗi font tiếng việt send sms from web to phone năm 2024
1 tuầns trước . bởi InauguralClutches
Các phương pháp dạy học tích cực môn hóa học năm 2024
4 ngàys trước . bởi HastyClearing
Giấy cam kết tiếng anh là gì năm 2024
4 ngàys trước . bởi CountlessAdjustment

Chúng tôi

Điều khoản

Trợ giúp

Mạng xã hội

Bản quyền © 2024 Inc.