Cách sử dụng đệ quy Python
Đệ quy Python là một chủ đề đáng sợ đối với người mới bắt đầu. Hãy xóa tan lầm tưởng rằng đệ quy là khó khăn bằng cách xác định nó. Đệ quy là một phương pháp lập trình trong đó một hàm gọi chính nó.
Điều đó nghe có vẻ đơn giản, phải không? Khi bạn hiểu rõ, đệ quy không phải là một khái niệm khó.
Trong hướng dẫn Python này, chúng ta sẽ nói về đệ quy và cách nó hoạt động. Chúng tôi sẽ giới thiệu cho các bạn một ví dụ về phép đệ quy sử dụng các hàm giai thừa để giúp bạn bắt đầu với phương pháp lập trình này.
Đệ quy là gì?
Đệ quy là nơi bạn xác định một cái gì đó theo nghĩa của chính nó.
Một hàm đệ quy giải quyết vấn đề bằng cách gọi lại chính nó. Hành vi này được hỗ trợ trong hầu hết các ngôn ngữ lập trình chính, chẳng hạn như Python. Chúng là một phần quan trọng của khoa học máy tính và khoa học dữ liệu.
Đệ quy rất hữu ích khi có thể tìm ra giải pháp cho một vấn đề bằng cách chia nó thành các bài toán nhỏ hơn mà tất cả đều sử dụng cùng một công thức. Những loại vấn đề này thường được gọi là “thuật toán đệ quy”. Chìa khóa để giải quyết chúng là ở cái tên!
Lặp lại so với Đệ quy
Có hai cách để giải một thuật toán:lặp lại hoặc đệ quy.
Các giải pháp lặp đi lặp lại cho các thuật toán được coi là “mạnh mẽ nhưng xấu xí”. Họ hoàn thành công việc, nhưng họ không thực hiện chính xác theo cách thanh lịch nhất. Để hiểu đúng các thuật toán đệ quy, chúng ta cần xem xét các hàm lặp.
81% người tham gia cho biết họ cảm thấy tự tin hơn về triển vọng công việc công nghệ của mình sau khi tham gia một cuộc thi đào tạo. Kết hợp với bootcamp ngay hôm nay.
Sinh viên tốt nghiệp bootcamp trung bình đã dành ít hơn sáu tháng để chuyển đổi nghề nghiệp, từ khi bắt đầu bootcamp đến khi tìm được công việc đầu tiên của họ.
Một hàm lặp là một hàm giải quyết vấn đề bằng cách sử dụng một vòng lặp. Nó sẽ thực thi mã bên trong một vòng lặp cho đến khi vòng lặp đó hoàn tất. Hàm đệ quy là một hàm chia nhỏ vấn đề thành các phần nhỏ hơn và giải quyết từng phần bằng cách gọi chính nó.
Factorials:Ví dụ lặp lại
Các thừa số là một cách tốt để chứng minh tư duy đệ quy và lặp lại. Trong toán học, giai thừa là tổng của một số và mọi số trước nó được nhân với nhau.
Giai thừa của 5 bằng 5 * 4 * 3 * 2 * 1. Giai thừa của 2 bằng 2 * 1.
Để tính giai thừa, chúng ta có thể viết một hàm lặp:
def factorial(number): total = 1 for n in range(1, number + 1): total = total * n return total
Hàm này sử dụng vòng lặp for để lặp qua tất cả các số trong phạm vi 1 và số chúng ta đã chỉ định cộng với 1. Đối với mỗi lần lặp, số mà vòng lặp đang lặp lại được nhân với tổng. Hãy gọi hàm của chúng ta để tìm giai thừa:
answer = factorial(4) print(answer)
Mã của chúng tôi trả về:24. Để đi đến giải pháp này, mã của chúng tôi chạy:
- 1 * 1 =1
- 2 * 2 =4
- 4 * 3 =8
- 8 * 4 =24
Như bạn có thể thấy, mã của chúng tôi nhân 4 với tất cả các số thấp hơn nó và sau đó là chính nó.
Mã này có chức năng. Hạn chế duy nhất là nó không thanh lịch như nó có thể. Đó là lúc các hàm đệ quy trở nên hữu ích.
Factorials:Ví dụ đệ quy
Hãy viết một hàm đệ quy tính giai thừa. Mở một tệp Python mới và dán vào mã sau:
def factorial(number): if number == 1: return 1 else: return (number * factorial(number - 1))
Đoạn mã này sử dụng phương pháp đệ quy. Khi hàm này được chạy, câu lệnh "if" được thực thi. Câu lệnh này kiểm tra xem số được truyền đến hàm có bằng 1. Nếu đúng, hàm của chúng ta trả về 1. Nếu không, giai thừa của số sẽ được tính.
Phép tính này hoạt động bằng cách nhân số được truyền vào hàm với giai thừa của số trước đó. Hàm này được gọi lặp đi lặp lại cho đến khi “số” bằng 1. Mỗi lần gọi hàm, giá trị của “số” sẽ giảm đi 1.
Hãy thử mã của chúng tôi với số 4:
answer = factorial(4) print(answer)
Câu trả lời 24 được trả lại. Câu trả lời của chúng tôi là đúng; nó giống như ví dụ cuối cùng của chúng tôi. Chúng tôi đã tìm ra giải pháp cho vấn đề này một cách đệ quy thay vì lặp lại.
Bạn vẫn cần giúp đỡ một chút? Hãy xem qua một ví dụ khác về đệ quy.
Đệ quy với dãy Fibonacci
Dãy fibonacci là một dãy toán học trong đó mỗi số là tổng của hai số trước đó. Chuỗi này bắt đầu bằng:0, 1, 1, 2, 3, 5, 8, 13, v.v.
Dãy này cộng hai số để tìm số tiếp theo. Điều này làm cho nó lý tưởng cho đệ quy.
Mở tệp Python và dán mã này vào:
def fibonacci(number): if number <= 1: return number else: return(fibonacci(number - 1) + fibonacci(number - 2))
Mã này sẽ tính tổng của hai số đứng trước trong danh sách, miễn là “số” nhiều hơn 1. Nếu không, “số được trả về”. Bây giờ, hãy gọi hàm của chúng ta:
executions = 5
print("Fibonacci Sequence:")
for number in range(executions):
print(fibonacci(number))
Biến thực thi theo dõi có bao nhiêu số trong dãy fibonacci mà chúng ta muốn tính toán. Chúng tôi sử dụng điều này để tạo một vòng lặp for gọi fibonacci() của chúng tôi hàm cho mỗi số trong phạm vi 1 và giá trị của "lần thực thi".
Trước khi vòng lặp for của chúng tôi bắt đầu, chúng tôi in “Fibonacci Sequence:” vào bảng điều khiển. Trong ví dụ này, vòng lặp “for” của chúng tôi thực thi:
fibonacci(1) fibonacci(2) fibonacci(3) fibonacci(4) fibonacci(5)
Hãy cùng nhau chạy mã của chúng ta và xem điều gì sẽ xảy ra:
Fibonacci Sequence: 0 1 1 2 3
Mã của chúng tôi tính toán năm số đầu tiên trong dãy fibonacci. Chúng tôi có thể tính toán nhiều con số hơn bằng cách tăng giá trị của "lần thực thi".
Độ sâu đệ quy và điều kiện cơ sở
Một hàm đệ quy phải có một điều kiện cơ sở. Đây là điều kiện dừng đệ quy khi một trường hợp cơ sở cụ thể được đáp ứng. Nếu không có một hàm cơ sở, một vòng lặp vô hạn sẽ được tạo.
Theo mặc định, một hàm đệ quy có thể tự thực thi không quá 1.000 lần. Khi đạt đến giới hạn này, một lỗi như sau sẽ xuất hiện:
RecursionError: maximum recursion depth exceeded
Đây là điều kiện cơ bản cho chương trình fibonacci của chúng tôi:
... if number <= 1: return number …
Điều kiện này kiểm tra xem giá trị của "số" bên trong chương trình fibonacci của chúng tôi bằng hoặc nhỏ hơn 1. Nếu đúng, giá trị của "số" được trả về; nếu không, hàm đệ quy bắt đầu.
Tại sao tôi nên sử dụng đệ quy?
Lợi ích của việc sử dụng đệ quy thay vì các hàm lặp là gì? Về mặt kỹ thuật, cả hai phương pháp đều có thể đạt được cùng một kết quả. Lợi ích của đệ quy là nó dễ đọc hơn.
Khi bạn nhìn thấy một hàm đệ quy, rõ ràng là câu trả lời cho một vấn đề nằm ở việc chia nó thành các phần nhỏ hơn. Trong khi các vòng lặp lặp đi lặp lại đôi khi có thể nhanh hơn, các hàm đệ quy thường được ưu tiên hơn do tính dễ đọc của chúng.
Bởi vì các hàm đệ quy dễ đọc hơn, chúng cũng dễ bảo trì và gỡ lỗi hơn. Điều này đặc biệt hữu ích khi bạn đang viết các thuật toán phức tạp có thể khó hiểu.
Kết luận
Một hàm đệ quy là một hàm gọi chính nó để tìm lời giải cho một vấn đề.
Các hàm đệ quy chia nhỏ một vấn đề thành nhiều phần và giải quyết một phần của vấn đề mỗi lần lặp. Các hàm đệ quy thường được sử dụng để tính thừa số và các số trong dãy fibonacci. Chúng cũng được sử dụng trong một số thuật toán.
Bây giờ bạn đã sẵn sàng để bắt đầu làm việc với các hàm đệ quy trong Python.