Các phương thức có thể được đệ quy trong Python không?

Một hàm gọi chính nó là một hàm đệ quy. Phương pháp này được sử dụng khi một vấn đề nào đó được xác định theo chính nó. Mặc dù điều này liên quan đến việc lặp đi lặp lại, nhưng việc sử dụng cách tiếp cận lặp lại để giải quyết vấn đề như vậy có thể rất tẻ nhạt. Cách tiếp cận đệ quy cung cấp một giải pháp rất ngắn gọn cho một vấn đề có vẻ phức tạp. Nó trông quyến rũ nhưng có thể khó hiểu

Ví dụ phổ biến nhất của đệ quy là tính giai thừa. Về mặt toán học, giai thừa được định nghĩa là. N. = n * (n-1)

Chúng ta sử dụng chính giai thừa để xác định giai thừa. Do đó, đây là trường hợp thích hợp để viết hàm đệ quy. Hãy để chúng tôi mở rộng định nghĩa trên để tính giá trị giai thừa của 5

5! = 5 X 4!
     5 X4 X 3!
     5 X4 X 3 X 2!
     5 X4 X 3 X  2 X 1!
     5 X4 X 3 X  2 X 1
   = 120

Mặc dù chúng ta có thể thực hiện phép tính này bằng vòng lặp, nhưng chức năng đệ quy của nó liên quan đến việc gọi nó liên tục bằng cách giảm số cho đến khi đạt 1. Sau đây là một hàm đệ quy để tính giai thừa

Thí dụ. Hàm đệ quy

def factorial(n):    
    if n == 1:
        print(n)
        return 1    
    else:
        print (n,'*', end=' ')
        return n * factorial(n-1)

Hàm đệ quy trên có thể được gọi như dưới đây

Khi hàm giai thừa được gọi với 5 làm đối số, các lệnh gọi liên tiếp đến cùng một hàm được đặt, đồng thời giảm giá trị của 5. Các hàm bắt đầu quay lại lệnh gọi trước đó sau khi đối số đạt đến 1. Giá trị trả về của lệnh gọi đầu tiên là tích lũy của các giá trị trả về của tất cả các lệnh gọi

Đệ quy là một phương pháp lập trình, trong đó một hàm gọi chính nó một hoặc nhiều lần trong phần thân của nó. Thông thường, nó trả về giá trị trả về của lệnh gọi hàm này. Nếu một định nghĩa hàm tuân theo đệ quy, chúng ta gọi hàm này là hàm đệ quy

Hàm đệ quy phải kết thúc để được sử dụng trong chương trình. Nó kết thúc, nếu với mỗi lần gọi đệ quy, giải pháp của vấn đề trở nên nhỏ hơn và chuyển sang trường hợp cơ sở, trong đó vấn đề có thể được giải quyết mà không cần đệ quy thêm. Một đệ quy có thể dẫn đến một vòng lặp vô hạn, nếu trường hợp cơ sở không được đáp ứng trong các cuộc gọi

Thí dụ

Đoạn mã sau trả về tổng của n số tự nhiên đầu tiên bằng cách sử dụng hàm đệ quy python

def sum_n(n):
    if n== 0:
        return 0
    else:
        return n + sum_n(n-1)

Điều này in tổng của 100 số tự nhiên đầu tiên và 500 số tự nhiên đầu tiên

print(sum_n(100))
print(sum_n(500))

đầu ra

C:/Users/TutorialsPoint1/~.py
5050
125250

Tóm lược. 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)

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

Trong hàm

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

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

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

def factorial(n):    
    if n == 1:
        print(n)
        return 1    
    else:
        print (n,'*', end=' ')
        return n * factorial(n-1)

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

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

def factorial(n):    
    if n == 1:
        print(n)
        return 1    
    else:
        print (n,'*', end=' ')
        return n * factorial(n-1)

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

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

def factorial(n):    
    if n == 1:
        print(n)
        return 1    
    else:
        print (n,'*', end=' ')
        return n * factorial(n-1)

…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, hãy gọi cho

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

  8 để hiển thị số 3
• Thứ hai, gọi

  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

  def factorial(n):    
      if n == 1:
          print(n)
          return 1    
      else:
          print (n,'*', end=' ')
          return n * factorial(n-1)
  

  00 để 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)

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

Để 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)

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

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

def sum_n(n):
    if n== 0:
        return 0
    else:
        return n + sum_n(n-1)

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

def sum_n(n):
    if n== 0:
        return 0
    else:
        return n + sum_n(n-1)

Lý do là

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

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 sum_n(n):
    if n== 0:
        return 0
    else:
        return n + sum_n(n-1)

đầu ra

def factorial(n):    
    if n == 1:
        print(n)
        return 1    
    else:
        print (n,'*', end=' ')
        return n * factorial(n-1)

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

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

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

Phương pháp có thể được đệ quy?

Tại sao Python không tốt cho đệ quy?

Các phương thức đệ quy có nhanh hơn các vòng lặp không?

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