Ý nghĩa đệ quy trong Python là gì?

Bản tóm tắt. trong hướng dẫn này, bạn sẽ tìm hiểu về các hàm đệ quy Python và cách sử dụng chúng để đơn giản hóa mã của bạn

Giới thiệu về hàm đệ quy

Một hàm đệ quy là một hàm gọi chính nó cho đến khi nó không

Hàm

def fn():
    # ...
    if condition:
        # stop calling itself
    else:
        fn()
    # ...
Code language: Python (python)

3 sau đây là hàm đệ quy vì nó có lời gọi đến chính nó

def fn():
    # ...
    fn()
    # ...
Code language: Python (python)

Trong hàm

def fn():
    # ...
    if condition:
        # stop calling itself
    else:
        fn()
    # ...
Code language: Python (python)

3,

def fn():
    # ...
    if condition:
        # stop calling itself
    else:
        fn()
    # ...
Code language: Python (python)

5 có nghĩa là mã khác

Ngoài ra, một hàm đệ quy cần có một điều kiện để ngừng gọi chính nó. Vì vậy, bạn cần thêm một câu lệnh if như thế này

def fn():
    # ...
    if condition:
        # stop calling itself
    else:
        fn()
    # ...
Code language: Python (python)

Thông thường, bạn sử dụng hàm đệ quy để chia một bài toán lớn khó giải thành các bài toán nhỏ dễ giải hơn

Trong lập trình, bạn sẽ thường thấy các hàm đệ quy được sử dụng trong cấu trúc dữ liệu và thuật toán như cây, đồ thị và tìm kiếm nhị phân

Ví dụ hàm đệ quy Python

Hãy lấy một số ví dụ về việc sử dụng các hàm đệ quy Python

1) Một ví dụ về hàm đệ quy đơn giản trong Python

Giả sử bạn cần phát triển chức năng đếm ngược đếm ngược từ một số cụ thể về 0

Ví dụ: nếu bạn gọi hàm đếm ngược từ 3, nó sẽ hiển thị đầu ra sau

3
2
1
Code language: Python (python)

Phần sau định nghĩa hàm

def fn():
    # ...
    if condition:
        # stop calling itself
    else:
        fn()
    # ...
Code language: Python (python)

6

def count_down(start):
    """ Count down from a number  """
    print(start)
Code language: Python (python)

Nếu bạn gọi hàm

def fn():
    # ...
    if condition:
        # stop calling itself
    else:
        fn()
    # ...
Code language: Python (python)

6 ngay bây giờ

count_down(3)



Code language: Python (python)

…nó sẽ chỉ hiển thị số 3

Để hiển thị các số 3, 2 và 1, bạn cần phải

• Đầu tiên, gọi số _______ 8 để hiển thị số 3
• Thứ hai, gọi số

  def fn():
      # ...
      if condition:
          # stop calling itself
      else:
          fn()
      # ...
  Code language: Python (python)

  9 để hiển thị số 2
• Cuối cùng, gọi

  3
  2
  1
  Code language: Python (python)

  0 để hiển thị số 1

Để làm như vậy, bên trong hàm

def fn():
    # ...
    if condition:
        # stop calling itself
    else:
        fn()
    # ...
Code language: Python (python)

6, bạn sẽ cần xác định logic để gọi hàm

def fn():
    # ...
    if condition:
        # stop calling itself
    else:
        fn()
    # ...
Code language: Python (python)

6 với đối số 2 và 1

Để làm điều đó, bạn cần thực hiện đệ quy hàm

def fn():
    # ...
    if condition:
        # stop calling itself
    else:
        fn()
    # ...
Code language: Python (python)

6

Phần sau đây định nghĩa một hàm

def fn():
    # ...
    if condition:
        # stop calling itself
    else:
        fn()
    # ...
Code language: Python (python)

6 đệ quy và gọi nó bằng cách chuyển số 3

def count_down(start):
    """ Count down from a number  """
    print(start)
    count_down(start-1)


count_down(3)
Code language: Python (python)

Nếu bạn thực hiện chương trình, bạn sẽ thấy lỗi sau

RecursionError: maximum recursion depth exceeded while calling a Python object
Code language: Python (python)

Lý do là

def fn():
    # ...
    if condition:
        # stop calling itself
    else:
        fn()
    # ...
Code language: Python (python)

6 tự gọi vô thời hạn cho đến khi hệ thống dừng nó

Vì bạn cần ngừng đếm ngược khi số về 0. Để làm như vậy, bạn thêm một điều kiện như thế này

def count_down(start):
    """ Count down from a number  """
    print(start)

    # call the count_down if the next
    # number is greater than 0
    next = start - 1
    if next > 0:
        count_down(next)


count_down(3)
Code language: Python (python)

đầu ra

3
2
1
Code language: Python (python)

Trong ví dụ này, hàm

def fn():
    # ...
    if condition:
        # stop calling itself
    else:
        fn()
    # ...
Code language: Python (python)

6 chỉ gọi chính nó khi số tiếp theo lớn hơn 0. Nói cách khác, nếu số tiếp theo bằng 0, nó sẽ ngừng gọi chính nó

2) Sử dụng hàm đệ quy để tính tổng của một dãy số

Giả sử rằng bạn cần tính tổng của một dãy e. g. , từ 1 đến 100. Một cách đơn giản để làm điều này là sử dụng vòng lặp for với hàm range()

Một ví dụ về đệ quy trong Python là gì?

Ý nghĩa đệ quy trong mã hóa là gì?

Điều gì xảy ra khi một hàm được gọi đệ quy?