Hướng dẫn recursive function examples in python - ví dụ về hàm đệ quy trong python

Trong hướng dẫn này, bạn sẽ học cách tạo một hàm đệ quy (một hàm tự gọi).

Đệ quy là gì?

Đệ quy là quá trình xác định một cái gì đó theo chính nó.

Một ví dụ thế giới vật lý sẽ là đặt hai gương song song đối diện nhau. Bất kỳ đối tượng ở giữa chúng sẽ được phản ánh đệ quy.

---

Chức năng đệ quy Python

Trong Python, chúng ta biết rằng một hàm có thể gọi các chức năng khác. Thậm chí có thể cho chức năng gọi chính nó. Các loại cấu trúc này được gọi là các hàm đệ quy.

Hình ảnh sau đây cho thấy hoạt động của hàm đệ quy gọi là

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

1.

Chức năng đệ quy trong Python

Sau đây là một ví dụ về hàm đệ quy để tìm giai thừa của một số nguyên.

Factorial của một số là sản phẩm của tất cả các số nguyên từ 1 đến số đó. Ví dụ: giai thừa của 6 (ký hiệu là 6!) Là 1*2*3*4*5*6 = 720.

Ví dụ về hàm đệ quy

def factorial(x):
    """This is a recursive function
    to find the factorial of an integer"""

    if x == 1:
        return 1
    else:
        return (x * factorial(x-1))


num = 3
print("The factorial of", num, "is", factorial(num))

Đầu ra

The factorial of 3 is 6

Trong ví dụ trên,

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

2 là một hàm đệ quy như nó tự gọi.

Khi chúng ta gọi hàm này với số nguyên dương, nó sẽ tự gọi mình bằng cách giảm số.

Mỗi hàm nhân số số với giai thừa của số bên dưới nó cho đến khi nó bằng một. Cuộc gọi đệ quy này có thể được giải thích trong các bước sau.

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

Chúng ta hãy xem một hình ảnh hiển thị một quá trình từng bước về những gì đang diễn ra:

Làm việc của một chức năng giai thừa đệ quy

Đệ quy của chúng tôi kết thúc khi số lượng giảm xuống 1. cái này được gọi là điều kiện cơ sở.

Mỗi chức năng đệ quy phải có một điều kiện cơ sở dừng đệ quy hoặc nếu không thì hàm tự gọi chính nó.

Thông dịch viên Python giới hạn độ sâu của đệ quy để giúp tránh các đệ quy vô hạn, dẫn đến tràn chồng.

Theo mặc định, độ sâu tối đa của đệ quy là 1000. Nếu giới hạn được vượt qua, nó sẽ dẫn đến

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

3. Hãy nhìn vào một điều kiện như vậy.

def recursor():
    recursor()
recursor()

Đầu ra

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

---

Trong ví dụ trên, 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 call2 là một hàm đệ quy như nó tự gọi.

1. Khi chúng ta gọi hàm này với số nguyên dương, nó sẽ tự gọi mình bằng cách giảm số.
2. Mỗi hàm nhân số số với giai thừa của số bên dưới nó cho đến khi nó bằng một. Cuộc gọi đệ quy này có thể được giải thích trong các bước sau.
3. Chúng ta hãy xem một hình ảnh hiển thị một quá trình từng bước về những gì đang diễn ra:

---

Làm việc của một chức năng giai thừa đệ quy

1. Đệ quy của chúng tôi kết thúc khi số lượng giảm xuống 1. cái này được gọi là điều kiện cơ sở.
2. Mỗi chức năng đệ quy phải có một điều kiện cơ sở dừng đệ quy hoặc nếu không thì hàm tự gọi chính nó.
3. Thông dịch viên Python giới hạn độ sâu của đệ quy để giúp tránh các đệ quy vô hạn, dẫn đến tràn chồng.

Đệ quy là quá trình của một hàm tự gọi từ trong mã của chính nó. Bạn có thể nghĩ về nó như một cách khác để hoàn thành một cấu trúc vòng lặp. Mô hình đệ quy xuất hiện trong nhiều tình huống trong thế giới thực, và chúng tôi sẽ bao gồm một số ví dụ về đệ quy trong Python ở đây. Một chức năng đệ quy chỉ tiếp tục tự gọi cho đến khi nó hoàn thành vấn đề trong tay. Điều đó mang lại một điểm tốt, và đó là để đảm bảo rằng chức năng đệ quy của bạn thực sự chấm dứt và trả lại tại một số điểm. Nếu không, chức năng đệ quy sẽ chạy mãi mãi, làm cạn kiệt bộ nhớ của bạn và làm hỏng máy tính của bạn. Có một bước trong đó chức năng thực sự kết thúc được gọi là một điều kiện phá vỡ. Mỗi lần được gọi là hàm đệ quy, các giá trị của các đối số từ cuộc gọi trước được lưu trữ trên ngăn xếp cuộc gọi.

Kiểu đệ quy 1: Đếm ngược vào 2

Ở đây chúng tôi có một hàm có tên BackwardsBy2, in các số theo thứ tự ngược lại bằng cách sử dụng các bước 2 bắt đầu bằng một số ban đầu. Điều kiện phá vỡ là nếu số nhỏ hơn hoặc bằng 0. Trong trường hợp đó, chúng tôi chỉ cần in số 0! Nếu điều kiện đó không được đáp ứng, hàm tự gọi bằng số hiện tại - 2. Chúng tôi cũng khởi tạo danh sách và thêm biểu tượng cảm xúc Smiley bằng số hiện tại. Bằng cách đó, khi việc đếm ngược xảy ra, một số lượng biểu tượng cảm xúc tương ứng sẽ xuất hiện cho mỗi lần lặp. Tôi nghĩ rằng bạn sẽ đồng ý, đây là một tính năng quan trọng của ví dụ đệ quy này.

def backwardsby2(num):
    if num <= 0:
        print('Zero!')
        return
    else:
        emojismiles = []
        for i in range(0, num):
            emojismiles += '😃'
        print(num, ' '.join(emojismiles))
        backwardsby2(num - 2)


backwardsby2(9)

9 😃 😃 😃 😃 😃 😃 😃 😃 😃
7 😃 😃 😃 😃 😃 😃 😃
5 😃 😃 😃 😃 😃
3 😃 😃 😃
1 😃
Zero!

Kiểu đệ quy Ví dụ 2: Tháp Hà Nội

Tháp Hà Nội là một câu đố cổ được cho là có nguồn gốc ở Ấn Độ hoặc Việt Nam. Nó liên quan đến việc di chuyển các vòng hoặc đĩa có kích thước khác nhau xung quanh trên ba cực. Mục tiêu trong câu đố này là di chuyển tất cả các vòng trên cực này sang cực khác trong khi giữ nguyên thứ tự của các vòng. Tuy nhiên, bạn phải tuân theo các quy tắc của câu đố, và đây là chỉ có một quyền có thể được di chuyển tại một thời điểm và không có vòng nào có thể được đặt trên đỉnh của một chiếc nhẫn có kích thước nhỏ hơn. Câu đố này có thể được giải quyết bằng cách sử dụng đệ quy trong Python, vì vậy hãy để Lôi thấy điều đó trong hành động!Tower Of Hanoi is an ancient puzzle said to have originated in India or Vietnam. It involves moving various sized rings or disks around on three poles. The goal in this puzzle is to move all of the rings on one pole to another while keeping the order of the rings intact. You must follow the rules of the puzzle however, and this is that only one right can be moved at a time, and no ring may be placed on top of a smaller sized ring. This puzzle can be solved using recursion in Python, so let’s see that in action!

def towerOfHanoi(numrings, from_pole, to_pole, aux_pole):
    if numrings == 1:
        print('Move ring 1 from', from_pole, 'pole to', to_pole, 'pole')
        return
    towerOfHanoi(numrings - 1, from_pole, aux_pole, to_pole)
    print('Move ring', numrings, 'from', from_pole, 'pole to', to_pole, 'pole')
    towerOfHanoi(numrings - 1, aux_pole, to_pole, from_pole)


numrings = 2
towerOfHanoi(numrings, 'Left', 'Right', 'Middle')

Move ring 1 from Left pole to Middle pole
Move ring 2 from Left pole to Right pole
Move ring 1 from Middle pole to Right pole

Đầu ra ở trên cho thấy số lượng các bước liên quan khi chỉ có hai vòng. Chúng tôi có thể chạy lại chương trình trong khi sử dụng ba vòng và bạn sẽ thấy rằng số bước để giải quyết tháp Hà Nội tăng lên. Ngoài ra, bạn có thể kiểm tra từng bước của quy trình trong trực quan hóa.

numrings = 3
towerOfHanoi(numrings, 'Left', 'Right', 'Middle')

The factorial of 3 is 6

0

---

Tháp Hà Nội bắt đầu trạng thái

---

Di chuyển vòng 1 từ cực trái sang cực phải

---

Di chuyển vòng 2 từ cực trái sang cực giữa

---

Di chuyển vòng 1 từ cực bên phải sang cực giữa

---

Di chuyển vòng 3 từ cực trái sang cực phải

---

Di chuyển vòng 1 từ cực giữa sang cột trái

---

Di chuyển vòng 2 từ cực giữa sang cực bên phải

---

Di chuyển vòng 1 từ cực trái sang cực phải

---

Di chuyển vòng 2 từ cực trái sang cực giữa

Di chuyển vòng 1 từ cực bên phải sang cực giữa

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

4 variable is zero. This means we have completed all of the multiplications needed. It is the fact that this function recursively calls itself which provides a looping behavior.

The factorial of 3 is 6

1

The factorial of 3 is 6

2

---

Di chuyển vòng 3 từ cực trái sang cực phải

Di chuyển vòng 1 từ cực giữa sang cột trái

The factorial of 3 is 6

3

The factorial of 3 is 6

4

---

Di chuyển vòng 2 từ cực giữa sang cực bên phải

Recursion Ví dụ 3: Đặt một số thành một nguồn

• Chúng ta có thể sử dụng đệ quy để tạo một hàm tính toán giá trị của một số nhân với chính nó một số lần nhất định. Tất nhiên, bạn đã thấy điều này nhiều lần. Đó là một hoạt động phổ biến trong toán học để đặt một số vào sức mạnh của một số. Ví dụ, hai đến công suất thứ tư là 16, hai công suất thứ năm là 32, v.v. Chúng tôi muốn nhân một đối số một số lần nhất định. Điều đó có nghĩa là chúng tôi cần hai đối số, một cho chính số và một cho sức mạnh mà nó sẽ được đặt thành. Điều kiện phá vỡ là nếu biến

  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

  4 bằng không. Điều này có nghĩa là chúng tôi đã hoàn thành tất cả các phép nhân cần thiết. Đó là thực tế là chức năng này tự gọi là chính nó cung cấp một hành vi vòng lặp.
• Ví dụ đệ quy 4: chức năng giai thừa
• Factorial là quá trình nhân tất cả các số nguyên nhỏ hơn hoặc bằng một số nhất định. Vì vậy, 5! tương đương với 5*4*3*2*1 là 120. Chúng ta có thể sử dụng hàm đệ quy để thực hiện công việc này cho chúng ta. Nó sẽ chỉ mất một đối số, số chúng tôi muốn áp dụng một giai thừa. Đối với điều kiện phá vỡ, nếu đối số đã cho đã đạt đến 0, chúng tôi sẽ trả về giá trị của một. Nếu không, chúng tôi trả lại số lần của số lần và giảm giá trị số.

The factorial of 3 is 6

5

The factorial of 3 is 6

6

---

Kiểu đệ quy Ví dụ 5: Trình tự Fibonacci

Trình tự Fibonacci xảy ra ở khắp mọi nơi trên thế giới và trong tất cả các bản chất. Trình tự 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, v.v. là chuỗi Fibonacci. Mỗi số liên tiếp được tìm thấy bằng cách thêm hai số trước nó. Dưới đây là cách chúng tôi tính toán trình tự Fibonacci trong Python bằng cách sử dụng hàm đệ quy. Nó sử dụng quá trình này.

The factorial of 3 is 6

7

The factorial of 3 is 6

8

---

Nếu số là 0, thì câu trả lời là 0.

Nếu số là 1, thì câu trả lời là 1.

The factorial of 3 is 6

9

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

0

Mặt khác, câu trả lời là tổng của hai số Fibonacci trước đó.

• Kiểu đệ quy 6: tổng số từ 1 đến n
• Chúng ta có thể sử dụng đệ quy để tìm ra tổng số các số từ 1 đến n như 1 + 2 + 3 + 4 +, v.v.
• Recursion Ví dụ 7: Đảo ngược một chuỗi
• Đây là một loại niềm vui. Dưới đây là chức năng đệ quy để đảo ngược một chuỗi và một số chuỗi rất thú vị tạo ra kết quả bất ngờ khi đảo ngược!
• Tìm hiểu thêm về đệ quy
• Recursion vs Loops in Python & nbsp; (Hackernoon)
• Cách hiểu các hàm Python đệ quy & nbsp; (Stackabuse)
• Chức năng đệ quy Python & nbsp; (thepythonguru)

---

Thuật ngữ kỹ thuật chức năng đệ quy & nbsp; (Techterms)

Ví dụ đệ quy & nbsp; (Pythonspot)

Ví dụ về chức năng đệ quy là gì?

Làm thế nào các chức năng đệ quy hoạt động trong Python?

Các loại chức năng đệ quy trong Python là gì?