Đệ quy trong Python là gì?

Đệ quy xảy ra khi một hàm hoặc thuật toán gọi chính nó. Đệ quy là một phương pháp giải quyết vấn đề liên quan đến việc chia nhỏ lặp đi lặp lại một vấn đề thành một ví dụ nhỏ hơn của cùng một vấn đề. Lập trình viên sẽ giải quyết từng lớp của vấn đề cho đến khi đạt được một vấn đề đủ nhỏ để có thể giải quyết một cách dễ dàng. Đệ quy thường thực hiện thông qua một hàm đệ quy.

Chúng ta có thể tìm hiểu khái niệm đệ quy bằng cách sử dụng ví dụ cổ điển về tìm giai thừa của một số. Giai thừa của một số là tích của tất cả các số nguyên lớn hơn 1 và nhỏ hơn hoặc bằng số đó.

Ví dụ: giai thừa của 4 là 4 * 3 * 2 * 1.

Vì vậy, về cơ bản, đối với bất kỳ số nguyên không âm N nào, giai thừa của N = N * giai thừa của (N - 1)

>>> Xem thêm: Docstring trong Python - Tìm hiểu về Docstring trong Pythn

Hàm đệ quy trong Python

Trong Python, chúng ta biết rằng một hàm có thể gọi các hàm khác. Thậm chí có thể cho hàm tự gọi. Các loại cấu trúc này được gọi là các hàm đệ quy. Vì vậy, nếu chúng ta có một hàm để tính giai thừa của một số, giả sử là giai thừa (n) , dựa trên thảo luận ở trên, chúng ta có thể nói,

giai thừa (n) = n * giai thừa (n - 1)

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

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

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

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

>>> Tham khảo: Khóa học lập trình Python

Ví dụ về đệ quy trong Python

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

Giai thừa của 3 là 6

Trong ví dụ trên, factorial() là một hàm đệ quy vì nó gọi chính nó. Khi chúng ta gọi hàm này với một số nguyên dương, nó sẽ gọi một cách đệ quy chính nó bằng cách giảm số lượng.

Mỗi hàm nhân 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 theo 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

Hãy xem một hình ảnh cho thấy quy trình từng bước của những gì đang diễn ra:

Ví dụ về quy trình đệ quy trong Python

Làm việc của một hàm giai thừa đệ quy

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

Mọi hàm đệ quy phải có một điều kiện cơ sở để dừng đệ quy hoặc nếu không hàm gọi chính nó vô hạn.

Trình thông dịch Python giới hạn độ sâu của đệ quy để giúp tránh đệ quy vô hạn, dẫn đến tràn ngăn xếp. 

Theo mặc định, độ sâu tối đa của đệ quy là 1000. Nếu vượt qua giới hạn, nó dẫn đến RecursionError. Hãy xem xét một điều kiện như vậy.

def recursor():

    recursor()

recursor()

Output

Traceback (most recent call last):

  File "<string>", line 3, in <module>

  File "<string>", line 2, in a

  File "<string>", line 2, in a

  File "<string>", line 2, in a

  [Previous line repeated 996 more times]

RecursionError: maximum recursion depth exceeded

Ưu điểm và nhược điểm cả Đệ quy

Ưu điểm của Đệ quy

- Các hàm đệ quy làm cho mã trông sạch sẽ và thanh lịch.

- Một nhiệm vụ phức tạp có thể được chia thành các bài toán con đơn giản hơn bằng cách sử dụng đệ quy.

- Việc tạo trình tự với đệ quy dễ dàng hơn so với việc sử dụng một số phép lặp lồng nhau.

Nhược điểm của Đệ quy

- Đôi khi logic đằng sau đệ quy rất khó theo dõi.

- Cuộc gọi đệ quy rất tốn kém (không hiệu quả) vì chúng chiếm nhiều bộ nhớ và thời gian.

- Các hàm đệ quy rất khó gỡ lỗi.

Kết luận:  Đệ quy là một hàm quan trọng trong Python. Bài viết trên đã giải thích đệ quy trong Python là gì cùng các ví dụ và ưu nhược điểm của đệ quy. Hy vọng bạn có thể áp dụng các kiến thức về đệ quy trong lập trình. Muốn thành thạo Python và các ngôn ngữ lập trình khác. Đừng quên tham khảo các khóa học lập trình tại T3H bạn nhé!

Nguồn: programiz, techvidvan