Hướng dẫn what is function and recursion in python? - hàm và đệ quy trong python là gì?

Bây giờ bạn nên ở một vị trí tốt để nhận ra khi đệ quy được kêu gọi và sẵn sàng sử dụng nó một cách tự tin khi nó cần! Nếu bạn muốn khám phá thêm về đệ quy trong Python, thì hãy xem suy nghĩ đệ quy trong Python.

Sự khác biệt giữa chức năng và đệ quy trong Python là gì?recursion comes from the Latin word recurrere, meaning to run or hasten back, return, revert, or recur. Here are some online definitions of recursion:

• Nếu bạn quen thuộc với các chức năng trong Python, thì bạn sẽ biết rằng việc gọi một hàm khác là khá phổ biến. Trong Python, một chức năng cũng có thể tự gọi! Một chức năng tự gọi được cho là đệ quy và kỹ thuật sử dụng một hàm đệ quy được gọi là đệ quy.: The act or process of returning or running back
• Một chức năng trong Python là gì?: The act of defining an object (usually a function) in terms of that object itself
• Một hàm là một khối mã chỉ chạy khi nó được gọi. Bạn có thể truyền dữ liệu, được gọi là tham số, thành một hàm. Một chức năng có thể trả về dữ liệu như là kết quả.: A method of defining a sequence of objects, such as an expression, function, or set, where some number of initial objects are given and each successive object is defined in terms of the preceding objects

Đệ quy và chức năng có giống nhau không?recursive definition is one in which the defined term appears in the definition itself. Self-referential situations often crop up in real life, even if they aren’t immediately recognizable as such. For example, suppose you wanted to describe the set of people that make up your ancestors. You could describe them this way:

Lưu ý cách khái niệm đang được xác định, tổ tiên, thể hiện theo định nghĩa riêng của nó. Đây là một định nghĩa đệ quy.ancestors, shows up in its own definition. This is a recursive definition.

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 hàm tự gọi.

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

Hầu hết các vấn đề lập trình là có thể giải quyết 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 cho vay một định nghĩa tự giới thiệu, ví dụ, định nghĩa của tổ tiên được hiển thị ở trên. Nếu bạn đang nghĩ ra một thuật toán để xử lý một trường hợp như vậy theo chương trình, một giải pháp đệ quy có thể sẽ sạch hơn và súc tích hơn.self-referential definition—for example, the definition of ancestors shown above. If you were devising an algorithm to handle such a case programmatically, a recursive solution would likely be cleaner and more concise.

Truyền tải các cấu trúc dữ liệu giống như cây là một ví dụ tốt khác. Bởi vì đây là những cấu trúc lồng nhau, chúng dễ dàng phù hợp với một định nghĩa đệ quy. Một thuật toán không nhận được để đi qua một cấu trúc lồng nhau có khả năng là một chút lộn xộn, 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 này trong hướng dẫn này.

Mặt khác, đệ quy là không phải 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 thụ nhiều bộ nhớ hơn so với không nhận được.
• 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 của 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 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 đó don don va chạm 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.namespaces.

Điều tương tự sẽ đúng nếu nhiều phiên bản của cùng một hàm đang chạy đồng thời. Ví dụ, hãy xem xét định nghĩa sau:

def function():
    x = 10
    function()

Khi

def recursor():
    recursor()
recursor()

Traceback (most recent call last):
  File "", line 3, in 
  File "", line 2, in a
  File "", line 2, in a
  File "", line 2, in a
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

Traceback (most recent call last):
  File "", line 3, in 
  File "", line 2, in a
  File "", line 2, in a
  File "", line 2, in a
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

def recursor():
    recursor()
recursor()

def recursor():
    recursor()
recursor()

Traceback (most recent call last):
  File "", line 3, in 
  File "", line 2, in a
  File "", line 2, in a
  File "", line 2, in a
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

Traceback (most recent call last):
  File "", line 3, in 
  File "", line 2, in a
  File "", line 2, in a
  File "", line 2, in a
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

Traceback (most recent call last):
  File "", line 3, in 
  File "", line 2, in a
  File "", line 2, in a
  File "", line 2, in a
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

Thật không may, chạy

def recursor():
    recursor()
recursor()

>>>

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

Như đã viết,

def recursor():
    recursor()
recursor()

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ộ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ẽ tăng ngoại lệ

def recursor():
    recursor()
recursor()

Có rất nhiều việc sử dụng cho một chức năng để tự gọi một cách bừa bãi một cách đệ quy mà không cần kết thúc. Nó gợi nhớ đến những hướng dẫn mà đôi khi bạn tìm thấy trên các chai dầu gội đầu: Lather Lather, Rửa sạch, lặp lại. Nếu bạn phải làm theo những hướng dẫn này theo nghĩa đen, bạn sẽ gội đầu mãi mãi!

Lỗ hổng logic 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ào đó nói là Lather, rửa sạch, lặp lại khi cần thiết. 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 mái tóc của mình đủ sạch để xem xét các lần lặp lại bổ sung không cần thiết. Dầu gội sau đó có thể dừng lại.

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

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

Bây giờ bạn đã sẵn sàng để xem cách này hoạt động với một số ví dụ.

Bắt đầu: Đếm xuống 0

Ví dụ đầu tiên là một hàm gọi là

def function():
    x = 10
    function()

>>>

>>> 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

Như đã viết,

def recursor():
    recursor()
recursor()

• 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ộ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ẽ tăng ngoại lệ

  def recursor():
      recursor()
  recursor()

  8, như bạn thấy ở trên.
• Có rất nhiều việc sử dụng cho một chức năng để tự gọi một cách bừa bãi một cách đệ quy mà không cần kết thúc. Nó gợi nhớ đến những hướng dẫn mà đôi khi bạn tìm thấy trên các chai dầu gội đầu: Lather Lather, Rửa sạch, lặp lại. Nếu bạn phải làm theo những hướng dẫn này theo nghĩa đen, bạn sẽ gội đầu mãi mãi!

Phiên bản của

def function():
    x = 10
    function()

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

Ở đây, một lần thực hiện không nhận được để so sánh:

>>>

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

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

Đây là một trường hợp trong đó giải pháp không nhận được ít nhất là rõ ràng và trực quan như loại đệ quy, và có lẽ nhiều hơn như vậy.

Tính toán giai thừa

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

Nói cách khác, n! là sản phẩm của tất cả các số nguyên từ 1 đến N, bao gồm.

Factorial cho vay để định nghĩa đệ quy rằng các văn bản lập trình gần như luôn luôn bao gồm nó như một trong những ví dụ đầu tiên. Bạn có thể thể hiện định nghĩa của N! đệ quy như thế này:

Như với ví dụ được hiển thị ở trên, có những trường hợp cơ sở có thể giải quyết được mà không có đệ quy. Các trường hợp phức tạp hơn là rút gọn, có nghĩa là chúng giảm xuống một trong các trường hợp cơ sở:reductive, meaning that they reduce to one of the base cases:

• Các trường hợp cơ sở (n = 0 hoặc n = 1) có thể giải quyết được mà không có đệ quy.
• Đối với các giá trị của n lớn hơn 1, n! được định nghĩa theo nghĩa (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! Có vẻ như thế này:

Các tính toán của 4 !, 3 !, và 2! Đình chỉ 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 mà không cần đệ quy thêm, và các tính toán hoãn lại để hoàn thành.

The factorial of 3 is 6

The factorial of 3 is 6

The factorial of 3 is 6

The factorial of 3 is 6

The factorial of 3 is 6

The factorial of 3 is 6

The factorial of 3 is 6

The factorial of 3 is 6

The factorial of 3 is 6

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

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

The factorial of 3 is 6

factorial(3)          # 1st call with 3
3 * factorial(2)      # 2nd call with 2
3 * 2 * factorial(1)  # 3rd call with 1
3 * 2 * 1             # return from 3rd call as number=1
3 * 2                 # return from 2nd call
6                     # return from 1st call

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

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

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

Đi qua một danh sách lồng nhau

factorial(3)          # 1st call with 3
3 * factorial(2)      # 2nd call with 2
3 * 2 * factorial(1)  # 3rd call with 1
3 * 2 * 1             # return from 3rd call as number=1
3 * 2                 # return from 2nd call
6                     # return from 1st call

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 danh sách Python sau:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

The factorial of 3 is 6

The factorial of 3 is 6

The factorial of 3 is 6

The factorial of 3 is 6

The factorial of 3 is 6

Traceback (most recent call last):
  File "", line 3, in 
  File "", line 2, in a
  File "", line 2, in a
  File "", line 2, in a
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

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

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

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

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

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

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

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

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

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

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

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

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

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

The factorial of 3 is 6

The factorial of 3 is 6

The factorial of 3 is 6

The factorial of 3 is 6

The factorial of 3 is 6

Traceback (most recent call last):
  File "", line 3, in 
  File "", line 2, in a
  File "", line 2, in a
  File "", line 2, in a
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

Chỉ cần gọi

The factorial of 3 is 6

>>>

factorial(3)          # 1st call with 3
3 * factorial(2)      # 2nd call with 2
3 * 2 * factorial(1)  # 3rd call with 1
3 * 2 * 1             # return from 3rd call as number=1
3 * 2                 # return from 2nd call
6                     # return from 1st call

Có lẽ bạn có thể quan tâm đến việc biết điều này thực hiện như thế nào trong bài kiểm tra thời gian:

1. Ồ!

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

   2 hoạt động tốt hơn so với tốt nhất trong ba triển khai khác được hiển thị ở trên bởi khoảng 10 là 10.
2. Một hàm được triển khai trong C sẽ hầu như luôn luôn nhanh hơn một hàm tương ứng được triển khai trong Python thuần túy.
3. Đi qua 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 danh sách Python sau:
   • Như sơ đồ sau đây cho thấy,

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

     3 chứa hai người phụ. Bản thân những người phụ đầu tiên trong số những người phụ này chứa một người phụ trợ khác:

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

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

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

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

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

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

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

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

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

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

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

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

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

The factorial of 3 is 6

The factorial of 3 is 6

The factorial of 3 is 6

The factorial of 3 is 6

The factorial of 3 is 6

Traceback (most recent call last):
  File "", line 3, in 
  File "", line 2, in a
  File "", line 2, in a
  File "", line 2, in a
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

The factorial of 3 is 6

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

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

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

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

The factorial of 3 is 6

The factorial of 3 is 6

The factorial of 3 is 6

The factorial of 3 is 6

factorial(3)          # 1st call with 3
3 * factorial(2)      # 2nd call with 2
3 * 2 * factorial(1)  # 3rd call with 1
3 * 2 * 1             # return from 3rd call as number=1
3 * 2                 # return from 2nd call
6                     # return from 1st call

factorial(3)          # 1st call with 3
3 * factorial(2)      # 2nd call with 2
3 * 2 * factorial(1)  # 3rd call with 1
3 * 2 * 1             # return from 3rd call as number=1
3 * 2                 # return from 2nd call
6                     # return from 1st call

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

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

factorial(3)          # 1st call with 3
3 * factorial(2)      # 2nd call with 2
3 * 2 * factorial(1)  # 3rd call with 1
3 * 2 * 1             # return from 3rd call as number=1
3 * 2                 # return from 2nd call
6                     # return from 1st call

factorial(3)          # 1st call with 3
3 * factorial(2)      # 2nd call with 2
3 * 2 * factorial(1)  # 3rd call with 1
3 * 2 * 1             # return from 3rd call as number=1
3 * 2                 # return from 2nd call
6                     # return from 1st call

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

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

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

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

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

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

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

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

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

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

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

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

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

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

The factorial of 3 is 6

The factorial of 3 is 6

The factorial of 3 is 6

The factorial of 3 is 6

The factorial of 3 is 6

Traceback (most recent call last):
  File "", line 3, in 
  File "", line 2, in a
  File "", line 2, in a
  File "", line 2, in a
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

factorial(3)          # 1st call with 3
3 * factorial(2)      # 2nd call with 2
3 * 2 * factorial(1)  # 3rd call with 1
3 * 2 * 1             # return from 3rd call as number=1
3 * 2                 # return from 2nd call
6                     # return from 1st call

The factorial of 3 is 6

The factorial of 3 is 606 đếm các đối tượng ở cấp cao nhất của >>> def countdown(n): ... while n >= 0: ... print(n) ... n -= 1 ... >>> countdown(5) 5 4 3 2 1 0 3, là ba phần tử lá >>> def countdown(n): ... while n >= 0: ... print(n) ... n -= 1 ... >>> countdown(5) 5 4 3 2 1 0 5, The factorial of 3 is 601 và The factorial of 3 is 604 và hai người phụ The factorial of 3 is 612 và The factorial of 3 is 613:

Những gì bạn cần ở đây là một chức năng đi qua toàn bộ cấu trúc danh sách, bao gồm các nhóm phụ. Thuật toán đi một cái gì đó như thế này:

factorial(3)          # 1st call with 3
3 * factorial(2)      # 2nd call with 2
3 * 2 * factorial(1)  # 3rd call with 1
3 * 2 * 1             # return from 3rd call as number=1
3 * 2                 # return from 2nd call
6                     # return from 1st call

8

Đi qua danh sách, lần lượt kiểm tra từng mục.

>>>

factorial(3)          # 1st call with 3
3 * factorial(2)      # 2nd call with 2
3 * 2 * factorial(1)  # 3rd call with 1
3 * 2 * 1             # return from 3rd call as number=1
3 * 2                 # return from 2nd call
6                     # return from 1st call

5

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.

Trong thực tế, về cơ bản điều tương tự cũng xảy ra trong việc thực hiện đệ quy là tốt. Khi bạn gọi một chức năng đệ quy, Python sẽ lưu trạng thái của thể hiện thực thi trên ngăn xếp để cuộc gọi đệ quy có thể chạy. Khi kết thúc cuộc gọi đệ quy, trạng thái được bật từ ngăn xếp để thể hiện bị gián đoạn có thể tiếp tục. Nó 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 nhà nước cho bạn.

Lưu ý mức độ ngắn gọn và có thể đọc được mã đệ quy khi so sánh với phiên bản không nhận được:

Đệ quy so với danh sách lồng nhau không được ghi lại

Đây là một 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ó nên sử dụng đệ quy để giải quyết vấn đề phụ thuộc vào phần lớn bản chất của vấn đề. Factorial, ví dụ, tự nhiên chuyển sang thực hiện đệ quy, nhưng giải pháp lặp cũng khá đơn giản. Trong trường hợp đó, nó được cho là một người ném lên.

Các vấn đề danh sách truyền tải là một câu chuyện khác. Trong trường hợp đó, giải pháp đệ quy là rất thanh lịch, trong khi loại không tái tạo là cồng kềnh ở mức tốt nhất.

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

Một palindrom là một từ đọc cùng nhau về phía trước như nó là về phía trước. Các ví dụ bao gồm các từ sau:palindrome is a word that reads the same backward as it does forward. Examples include the following words:

• Xe đua
• Mức độ
• Chèo xuồng
• Reviver
• 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à palindromic hay không, có lẽ bạn sẽ nghĩ ra một cái gì đó như đảo ngược chuỗi và xem nó có giống như bản gốc không. Bạn có thể nhận được đơn giản hơn thế.

Thậm chí hữu ích hơn, Python từ

The factorial of 3 is 6

>>>

def recursor():
    recursor()
recursor()

Điều này là rõ ràng và súc tích. Có hầu như không cần phải tìm kiếm một giải pháp thay thế. Nhưng chỉ để cho vui, hãy xem xét định nghĩa đệ quy này của một palindrom:

• Các trường hợp cơ sở: Một chuỗi trống và một chuỗi bao gồm một ký tự duy nhất là palindromic. An empty string and a string consisting of a single character are inherently palindromic.
• Đệ quy khử: Một chuỗi có độ dài hai hoặc lớn hơn là một palindrom nếu nó thỏa mãn cả hai tiêu chí sau: A string of length two or greater is a palindrome if it satisfies both of these criteria:
  1. Các ký tự đầu tiên và cuối cùng là như nhau.
  2. Chất nền giữa các ký tự đầu tiên và cuối cùng là một palindrom.

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

The factorial of 3 is 6

• Nhân vật đầu tiên là

  The factorial of 3 is 6

  34.
• Nhân vật cuối cùng là

  The factorial of 3 is 6

  35.
• Chất nền giữa các ký tự đầu tiên và cuối cùng là

  The factorial of 3 is 6

  36.

Vì vậy, bạn có thể xác định

The factorial of 3 is 6

>>>

def recursor():
    recursor()
recursor()

Điều này là rõ ràng và súc tích. Có hầu như không cần phải tìm kiếm một giải pháp thay thế. Nhưng chỉ để cho vui, hãy xem xét định nghĩa đệ quy này của một palindrom:

Các trường hợp cơ sở: Một chuỗi trống và một chuỗi bao gồm một ký tự duy nhất là palindromic.

Đệ quy khử: Một chuỗi có độ dài hai hoặc lớn hơn là một palindrom nếu nó thỏa mãn cả hai tiêu chí sau:

Các ký tự đầu tiên và cuối cùng là như nhau.pivot item. This can be any item in the list. You then partition the list into two sublists based on the pivot item and recursively sort the sublists.

Chất nền giữa các ký tự đầu tiên và cuối cùng là một palindrom.

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

  The factorial of 3 is 6

  33, việc lập chỉ mục và cắt, hãy cung cấp cho các nền tảng sau:
• Nhân vật đầu tiên là

  The factorial of 3 is 6

  34.
  1. Nhân vật cuối cùng là

     The factorial of 3 is 6

     35.
  2. Chất nền giữa các ký tự đầu tiên và cuối cùng là

     The factorial of 3 is 6

     36.
• Vì vậy, bạn có thể xác định

  The factorial of 3 is 6

  37 đệ quy như thế này:

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

Sắp xếp với Quicksort

Ví dụ cuối cùng được trình bày, giống như danh sách lồng nhau, là một ví dụ điển hình về một vấn đề rất tự nhiên gợi ý một cách tiếp cận đệ quy. Thuật toán Quicksort 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à một thuật toán phân chia và chinh phục. 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 Pivot. Đây có thể là bất kỳ mục trong danh sách. Sau đó, bạn phân vùng danh sách thành hai người phụ dựa trên mục Pivot và sắp xếp các nhóm phụ.

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

Chọn mục Pivot.

Phân vùng danh sách thành hai người phụ:

Những mặt hàng ít hơn mục Pivot

Mục đầu tiên trong danh sách là một lựa chọn phổ biến, 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ì chúng 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 Pivot.

Một lựa 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 nó làm mục Pivot. Đây là chiến lược được sử dụng trong mã mẫu dưới đây.

Sử dụng triển khai Quicksort

Bây giờ nền tảng đã được đặt ra, bạn đã sẵn sàng chuyển sang thuật toán Quicksort. Ở đây, mã Python:

def recursor():
    recursor()
recursor()

2

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

The factorial of 3 is 6

38 đang làm:

• Dòng 4: Các trường hợp cơ sở trong đó danh sách trống hoặc chỉ có một phần tử duy nhất The base cases where the list is either empty or has only a single element
• Dòng 7 đến 13: Tính toán mục Pivot bằng phương pháp trung bình ba Calculation of the pivot item by the median-of-three method
• Dòng 14 đến 18: Tạo ra ba danh sách phân vùng Creation of the three partition lists
• Các dòng 20 đến 24: Sắp xếp đệ quy và lắp lại danh sách phân vùng Recursive sorting and reassembly of the partition lists

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

The factorial of 3 is 6

38 trong hành động:

>>>

def recursor():
    recursor()
recursor()

3

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

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

0 và

The factorial of 3 is 6

41:

def recursor():
    recursor()
recursor()

4

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

The factorial of 3 is 6

42 để kiểm tra

The factorial of 3 is 6

38:

>>>

def recursor():
    recursor()
recursor()

5

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

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

0 và

The factorial of 3 is 6

41:

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

The factorial of 3 is 6

42 để kiểm tra

The factorial of 3 is 6

38:

Để hiểu thêm về cách

The factorial of 3 is 6

38 hoạt động, hãy xem sơ đồ dưới đây. Điều này cho thấy chuỗi đệ quy khi sắp xếp danh sách mười hai phần tử:

Thuật toán Quicksort, danh sách mười hai 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à The factorial of 3 is 6 45, The factorial of 3 is 6 46 và The factorial of 3 is 6 47. Trung bình là The factorial of 3 is 6 45, do đó trở thành mục trục. Phân vùng đầu tiên sau đó bao gồm các nhóm phụ sau:
Người phụ nữ	vật phẩm
The factorial of 3 is 6 49	Các mục ít hơn mục Pivot
The factorial of 3 is 6 50	Mục Pivot

The factorial of 3 is 6

51

Các mục lớn hơn mục xoay

Mỗi người phụ sau đó được phân vùng đệ quy theo cùng một cách cho đến khi tất cả các nhóm phụ 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 lắp lại theo thứ tự được sắp xếp. Lưu ý rằng trong bước thứ hai đến cuối cùng bên trái, mục Pivot

The factorial of 3 is 6

Sự 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 chức năng tự gọi. Đệ quy isn bằng bất kỳ phương tiện nào phù hợp cho mọi nhiệm vụ. Nhưng một số vấn đề lập trình hầu như khóc vì nó. Trong những tình huống đó, nó là một kỹ thuật tuyệt vời để có được sự xử lý của bạn.recursively
• Trong hướng dẫn này, bạn đã học được:design of Python functions supports recursion
• Ý nghĩa của một chức năng để tự gọi mình là đệ quyfactors to consider when choosing whether or not to solve a problem recursively
• Cách thiết kế các chức năng Python hỗ trợ đệ quyimplement a recursive function in Python

Những yếu tố nào cần xem xét khi chọn liệu có nên giải quyết vấn đề hay không

Cách thực hiện chức năng đệ quy trong Python