1. Hàm đệ quy là gì?

Nói về toán học thì đệ quy là thuật toán giải quyết bài toán bằng cách gọi lại chính thuật toán đó, thao tác này sẽ thực hiện liên tục cho đến khi gặp điều kiện dừng.

Đệ quy được thể hiện tốt khi áp dụng với hàm trong Python. Hàm đệ quy là chương trình sẽ gọi lại chính hàm đó và ngưng gọi khi gặp điều kiện dừng. Nếu quay lại kiến thức về vòng lặp thì bản chất đây cũng là một loại vòng lặp đặc biệt phải không các bạn.

Hãy làm một ví dụ đơn giản đó là tính giai thừa của một số. Ví dụ giai thừa của 6 thì sẽ là 1*2*3*4*5*6 = 720.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# An example of a recursive function to
# find the factorial of a number
def calc_factorial(x):
    """This is a recursive function
    to find the factorial of an integer"""
    if x == 1:
        return 1
    else:
        return (x * calc_factorial(x-1))
num = 4
print("The factorial of", num, "is", calc_factorial(num))  

Bạn hãy để ý bên trong phần thân của hàm calc_factorial nhé, điều kiện để dừng đệ quy là x == 1, ngược lại chương trình sẽ thực hiện lặp đệ quy bởi đoạn code return (x * calc_factorial(x-1)).

Quy trình hoạt động của nó như sau:

1
2
3
4
5
calc_factorial(4)              # 1st call with 4
4 * calc_factorial(3)          # 2nd call with 3
4 * 3 * calc_factorial(2)      # 3rd call with 2
4 * 3 * 2 * calc_factorial(1)  # 4th call with 1
4 * 3 * 2 * 1                  # return from 4th call as number=1

Lần gọi đệ quy cuối cùng vì giá trị tham số x truyền vào là 1 nên sẽ không thực hiện đệ quy nữa, sau đó trả kết quả là 24.

2. Ưu điểm và nhược điểm của đệ quy

Sau đây là một vài ưu điểm và nhược điểm của đệ quy trong lập trình Python.

Ưu điểm:

  • Các hàm đệ quy làm cho mã trông sạch sẽ
  • Một tác vụ phức tạp có thể được chia thành các vấn đề phụ đơn giản hơn bằng cách sử dụng đệ quy.
  • Tạo trình tự dễ dàng với đệ quy hơn là sử dụng một số lần lặp lồng nhau.

Nhược điểm:

  • Đôi khi logic đằng sau đệ quy rất khó theo dõi.
  • Chi phí gọi đệ quy rất tốn kém (không hiệu quả) vì chúng chiếm rất nhiều bộ nhớ và thời gian.
  • Các hàm đệ quy khó gỡ lỗi.

3. Lời kết

Khi đi làm thực tế thì người ta rất ít khi chọn giải pháp đệ quy, trừ khi bắt buộc, bởi mất khá nhiều tài nguyên về bộ nhớ và thời gian để chạy một ứng dụng đệ quy, điều này là không tốt cho những ứng dụng trong thực tế. Bạn thử nghĩ xem nếu một website hoạt động quá chậm thì sẽ giảm đi phần trải nghiệm của người dùng một cách nghiêm trọng.

Có khá nhiều loại đệ quy như đệ quy tuyến tính, đệ quy hỗ tương, .. nhưng mình không đề cập đến trong bài viết, bạn tự tìm hiểu nhé.

Theo:https://freetuts.net

 

 

Được quan tâm nhiều nhất

  • Apple Watch Series 4 Teardown

  • iPhone 11 Pro Max Teardown - Tiny Motherboard & BIG Battery!

  • Apple Watch Series 5 Teardown - Always on Display Explained

Bạn thấy bài viết này thế nào?
5/5 - (1 bình chọn)

Thích bài viết

1 thích

Chia sẻ ngay!

phuongle

Thành viên từ: 10/12/2019

Điểm uy tín: 8,324

SMod: 1,288 hướng dẫn đã chia sẻ

Team

Lập Trình Thành viên của Lập Trình

1 Thành viên

1,288 bài viết

Thêm bình luận

Bình luận bằng tài khoản Facebook

Săn Sale Ngay Trên Shopee - Giảm giá đến 500K Đóng
Amharic Amharic Arabic Arabic Bengali Bengali Chinese (Simplified) Chinese (Simplified) Chinese (Traditional) Chinese (Traditional) English English Filipino Filipino French French German German Hausa Hausa Hindi Hindi Indonesian Indonesian Italian Italian Japanese Japanese Korean Korean Persian Persian Portuguese Portuguese Russian Russian Serbian Serbian Spanish Spanish Thai Thai Turkish Turkish Urdu Urdu Vietnamese Vietnamese