Khi một hàm gọi chính nó, nó được gọi là hàm đệ quy. Trong hướng dẫn này, chúng ta sẽ học cách viết hàm đệ quy Python
Đệ quy trong Python là gì?
Khi một hàm được định nghĩa theo cách nó gọi chính nó, nó được gọi là hàm đệ quy. Hiện tượng này được gọi là đệ quy. Python hỗ trợ các hàm đệ quy
Chúng ta có thực sự cần Hàm đệ quy không?
Đệ quy rất giống với một vòng lặp trong đó hàm được gọi trong mỗi lần lặp. Đó là lý do tại sao chúng ta luôn có thể sử dụng các vòng lặp để thay thế cho hàm đệ quy Python
Tuy nhiên, một số lập trình viên thích đệ quy hơn vòng lặp. Đó chủ yếu là vấn đề lựa chọn và bạn có thể tự do sử dụng vòng lặp hoặc đệ quy
Python cho vòng lặp
Ví dụ về hàm đệ quy trong Python
Hãy xem xét một vài ví dụ về hàm đệ quy trong Python
1. Giai thừa của một số nguyên
Giai thừa của một số nguyên được tính bằng cách nhân các số nguyên từ 1 đến số đó. Ví dụ, giai thừa của 10 sẽ là 1*2*3…. *10
Hãy xem cách chúng ta có thể viết hàm giai thừa bằng vòng lặp for
def factorial[n]: result = 1 for i in range[1, n + 1]: result = result * i return result print[f'Factorial of 10 = {factorial[10]}'] print[f'Factorial of 5 = {factorial[5]}']
Hãy xem cách chúng ta có thể thay đổi hàm giai thừa[] để sử dụng đệ quy
def factorial[n]: if n == 1: return 1 else: return n * factorial[n - 1] print[f'Factorial of 10 = {factorial[10]}'] print[f'Factorial of 5 = {factorial[5]}']
Hình ảnh dưới đây cho thấy việc thực thi hàm đệ quy
2. Dãy Fibonacci
Dãy Fibonacci là dãy số mà mỗi số là tổng của hai số liền trước. Ví dụ – 1, 1, 2, 3, 5, 8, 13, 21, v.v.
Hãy xem một hàm trả về chuỗi số Fibonacci bằng cách sử dụng các vòng lặp
def fibonacci[n]: """ Returns Fibonacci Number at nth position using loop""" if n == 0: return 0 if n == 1: return 1 i1 = 0 i2 = 1 num = 1 for x in range[1, n]: num = i1 + i2 i1 = i2 i2 = num return num for i in range[10]: print[fibonacci[i], end=" "] # Output: 0 1 1 2 3 5 8 13 21 34
Đây là cách triển khai hàm fibonacci[] sử dụng đệ quy
def fibonacci[n]: """ Returns Fibonacci Number at nth position using recursion""" if n == 0: return 0 elif n == 1: return 1 else: return fibonacci[n - 1] + fibonacci[n - 2] for i in range[10]: print[fibonacci[i], end=" "] # Output: 0 1 1 2 3 5 8 13 21 34
Ở đây mã hàm đệ quy nhỏ hơn và dễ hiểu. Vì vậy, sử dụng đệ quy, trong trường hợp này, có ý nghĩa
Trường hợp cơ sở trong đệ quy là gì?
Trong khi xác định hàm đệ quy, phải có ít nhất một trường hợp cơ sở mà chúng ta biết kết quả. Sau đó, mọi lệnh gọi hàm đệ quy liên tiếp phải đưa nó đến gần trường hợp cơ sở hơn. Điều này là cần thiết để cuối cùng các cuộc gọi đệ quy kết thúc. Nếu không, chức năng sẽ không bao giờ kết thúc và chúng tôi sẽ thoát khỏi lỗi bộ nhớ
Bạn có thể kiểm tra hành vi này trong cả hai ví dụ trên. Các đối số gọi hàm đệ quy đang tiến gần hơn đến trường hợp cơ sở
Ưu điểm của đệ quy
- Đôi khi đệ quy làm giảm số lượng dòng mã
- Mã đệ quy có vẻ đơn giản
- Nếu chúng ta biết trường hợp cơ sở, thì việc sử dụng đệ quy trong một hàm sẽ dễ dàng hơn
Nhược điểm của đệ quy
- Nếu không được triển khai đúng cách, chức năng sẽ không bao giờ kết thúc
- Hiểu đệ quy khó hiểu hơn khi so sánh với các vòng lặp
Đệ quy hay Vòng lặp?
Đó là vấn đề lựa chọn cá nhân. Tôi luôn thích vòng lặp hơn đệ quy. Tôi chưa thấy ví dụ nào mà chúng ta không thể sử dụng vòng lặp và chỉ phải sử dụng đệ quy
Cả vòng lặp và đệ quy đều là những khái niệm lập trình chúng ta sử dụng để giải quyết vấn đề. Cái này có thể phù hợp với một tình huống hơn cái kia, vì vậy biết khi nào nên sử dụng cái nào trong hai cái là rất quan trọng
Đối với mục đích của ảnh này, các đoạn mã mẫu sẽ được viết bằng Python
một vòng lặp là gì?
Vòng lặp là một lệnh yêu cầu máy tính thực hiện lặp đi lặp lại một lệnh, thường dựa trên một điều kiện. Chúng tôi có ba loại vòng lặp chính
def fibonacci[n]: """ Returns Fibonacci Number at nth position using recursion""" if n == 0: return 0 elif n == 1: return 1 else: return fibonacci[n - 1] + fibonacci[n - 2] for i in range[10]: print[fibonacci[i], end=" "] # Output: 0 1 1 2 3 5 8 13 21 34
7 vòng lặpdef fibonacci[n]: """ Returns Fibonacci Number at nth position using recursion""" if n == 0: return 0 elif n == 1: return 1 else: return fibonacci[n - 1] + fibonacci[n - 2] for i in range[10]: print[fibonacci[i], end=" "] # Output: 0 1 1 2 3 5 8 13 21 34
8 vòng lặpdef fibonacci[n]: """ Returns Fibonacci Number at nth position using recursion""" if n == 0: return 0 elif n == 1: return 1 else: return fibonacci[n - 1] + fibonacci[n - 2] for i in range[10]: print[fibonacci[i], end=" "] # Output: 0 1 1 2 3 5 8 13 21 34
9 vòng lặp
Cái sau không có sẵn trong Python và chỉ khác một chút so với các vòng lặp
def fibonacci[n]: """ Returns Fibonacci Number at nth position using recursion""" if n == 0: return 0 elif n == 1: return 1 else: return fibonacci[n - 1] + fibonacci[n - 2] for i in range[10]: print[fibonacci[i], end=" "] # Output: 0 1 1 2 3 5 8 13 21 348 thông thường
Vòng lặp
number = 0
while [number < 10]:
print[number]
1
number = 0
while [number < 10]:
print[number]
Các vòng lặp
number = 0
while [number < 10]:
print[number]
1 thường được sử dụng để lặp qua một số lượng hữu hạn các mục và thực hiện một hành động trên một mục tại một khoảng thời gian cụ thể trong vòng lặp, e. g. , lặp qua danh sách tên và in chúngTrong ví dụ bên dưới, chúng tôi lặp lại danh sách tên hữu hạn và in từng tên ra thiết bị đầu cuối
names = ["Kyle", "John", "Doe", "Sam"]
for name in names:
print[name]
number = 0
while [number < 10]:
print[number]
3 vòng lặp
number = 0
while [number < 10]:
print[number]
Các vòng lặp
number = 0
while [number < 10]:
print[number]
3 liên tục thực thi trong khi một điều kiện cụ thể là đúng và sẽ chỉ tạm dừng/dừng khi gặp câu lệnh ngắt hoặc điều kiện ban đầu trở thành sai
number = 0
while [number < 10]:
print[number]
Đoạn mã trên chứa một vòng lặp
def fibonacci[n]: """ Returns Fibonacci Number at nth position using recursion""" if n == 0: return 0 elif n == 1: return 1 else: return fibonacci[n - 1] + fibonacci[n - 2] for i in range[10]: print[fibonacci[i], end=" "] # Output: 0 1 1 2 3 5 8 13 21 348 thực thi vô hạn vì
number = 0
while [number < 10]:
print[number]
6 luôn bằng 0. Hãy khắc phục điều này bằng cách tăng giá trị của
number = 0
while [number < 10]:
print[number]
6 trên mỗi lần lặp lạidef factorial[n]: if n == 1: return 1 else: return n * factorial[n - 1] print[f'Factorial of 10 = {factorial[10]}'] print[f'Factorial of 5 = {factorial[5]}']2
Bây giờ, mã này sẽ thực thi 9 lần
Chúng tôi có một biến
number = 0
while [number < 10]:
print[number]
6 với giá trị ban đầu là
number = 0
while [number < 10]:
print[number]
9Điều kiện của vòng lặp chỉ là
def factorial[n]: if n == 1: return 1 else: return n * factorial[n - 1] print[f'Factorial of 10 = {factorial[10]}'] print[f'Factorial of 5 = {factorial[5]}']20 chỉ khi giá trị của
number = 0
while [number < 10]:
print[number]
6 nhỏ hơn 10. Chúng tôi thêm 1 vào giá trị của
number = 0
while [number < 10]:
print[number]
6 sau mỗi lần lặp lạiVòng lặp bắt đầu bằng cách kiểm tra xem giá trị của
number = 0
while [number < 10]:
print[number]
6 có nhỏ hơn 10 hay không, điều này ban đầu là đúngBởi vì điều này là đúng, nên vòng lặp thực thi phần thân của nó, in ra giá trị của
number = 0
while [number < 10]:
print[number]
6 và thêm 1 vào giá trị đó. Giá trị của
number = 0
while [number < 10]:
print[number]
6 bây giờ bằng 1 và kiểm tra lặp lại. 1 nhỏ hơn 10, vì vậy phần thân thực thi lại và 1 được thêm vào giá trị của
number = 0
while [number < 10]:
print[number]
6Quá trình này tiếp tục cho đến khi giá trị của
number = 0
while [number < 10]:
print[number]
6 đạt 9. Vòng lặp kiểm tra xem 9 < 10 có đúng không và thực thi phần thân của nó, sau đó thêm 1 vào
number = 0
while [number < 10]:
print[number]
6, làm cho giá trị của nó là def factorial[n]: if n == 1: return 1 else: return n * factorial[n - 1] print[f'Factorial of 10 = {factorial[10]}'] print[f'Factorial of 5 = {factorial[5]}']29. Vòng lặp tiếp tục kiểm tra xem
number = 0
while [number < 10]:
print[number]
6 < 10; def fibonacci[n]:
""" Returns Fibonacci Number at nth position using loop"""
if n == 0:
return 0
if n == 1:
return 1
i1 = 0
i2 = 1
num = 1
for x in range[1, n]:
num = i1 + i2
i1 = i2
i2 = num
return num
for i in range[10]:
print[fibonacci[i], end=" "]
# Output: 0 1 1 2 3 5 8 13 21 34
62 vòng lặp
Vòng lặp
def fibonacci[n]: """ Returns Fibonacci Number at nth position using loop""" if n == 0: return 0 if n == 1: return 1 i1 = 0 i2 = 1 num = 1 for x in range[1, n]: num = i1 + i2 i1 = i2 i2 = num return num for i in range[10]: print[fibonacci[i], end=" "] # Output: 0 1 1 2 3 5 8 13 21 3462 tương tự như vòng lặp
def fibonacci[n]: """ Returns Fibonacci Number at nth position using recursion""" if n == 0: return 0 elif n == 1: return 1 else: return fibonacci[n - 1] + fibonacci[n - 2] for i in range[10]: print[fibonacci[i], end=" "] # Output: 0 1 1 2 3 5 8 13 21 348 bình thường với một chút xoắn. Trong trường hợp này, vòng lặp sẽ luôn thực hiện ít nhất một lần trước khi nó bắt đầu kiểm tra xem điều kiện có được thỏa mãn hay không
Như tôi đã đề cập trước đó, chúng tôi không có vòng lặp
def fibonacci[n]: """ Returns Fibonacci Number at nth position using loop""" if n == 0: return 0 if n == 1: return 1 i1 = 0 i2 = 1 num = 1 for x in range[1, n]: num = i1 + i2 i1 = i2 i2 = num return num for i in range[10]: print[fibonacci[i], end=" "] # Output: 0 1 1 2 3 5 8 13 21 3465 trong Python. Dưới đây là cấu trúc của một vòng lặp
def fibonacci[n]: """ Returns Fibonacci Number at nth position using loop""" if n == 0: return 0 if n == 1: return 1 i1 = 0 i2 = 1 num = 1 for x in range[1, n]: num = i1 + i2 i1 = i2 i2 = num return num for i in range[10]: print[fibonacci[i], end=" "] # Output: 0 1 1 2 3 5 8 13 21 3465 điển hình
def fibonacci[n]: """ Returns Fibonacci Number at nth position using loop""" if n == 0: return 0 if n == 1: return 1 i1 = 0 i2 = 1 num = 1 for x in range[1, n]: num = i1 + i2 i1 = i2 i2 = num return num for i in range[10]: print[fibonacci[i], end=" "] # Output: 0 1 1 2 3 5 8 13 21 346
Vòng lặp này bắt đầu bằng cách in 2 và tăng
number = 0
while [number < 10]:
print[number]
6 lên một trước khi nó kiểm tra điều kiện. Do đó, vòng lặp sẽ in 2 9 lầnđệ quy
Đệ quy hơi giống với vòng lặp. Đệ quy là tình huống mà một hàm gọi chính nó trong phần thân của nó trong khi thực thi. Dưới đây là một ví dụ về hàm arecursive functiona tự thực thi trong phần thân của nó
def fibonacci[n]: """ Returns Fibonacci Number at nth position using recursion""" if n == 0: return 0 elif n == 1: return 1 else: return fibonacci[n - 1] + fibonacci[n - 2] for i in range[10]: print[fibonacci[i], end=" "] # Output: 0 1 1 2 3 5 8 13 21 343
Nếu bạn thực thi đoạn mã trên, cuối cùng nó sẽ tăng một số
def fibonacci[n]: """ Returns Fibonacci Number at nth position using loop""" if n == 0: return 0 if n == 1: return 1 i1 = 0 i2 = 1 num = 1 for x in range[1, n]: num = i1 + i2 i1 = i2 i2 = num return num for i in range[10]: print[fibonacci[i], end=" "] # Output: 0 1 1 2 3 5 8 13 21 3468 cho biết độ sâu đệ quy tối đa đã bị vượt quá. Bạn có thể sử dụng một hàm đệ quy khi cần giải một bài toán chuỗi phức tạp bằng cách chia nhỏ nó ra và giải các trường hợp nhỏ hơn của nó. Một ví dụ phổ biến là tính giai thừa hoặc chuỗi Fibonacci
Vòng lặp so với đệ quy
Hãy sử dụng tình huống sau đây làm ví dụ. Giả sử chúng tôi muốn có thể tính giai thừa của một số được cung cấp cho chúng tôi. Giai thừa của một số được cho bằng cách tìm tích của số đó và số lân cận lùi 1 bước của nó lặp đi lặp lại cho đến khi chúng ta đạt 1
Không có giai thừa cho số âm
Giai thừa của 5 được cho bởi 5x4x3x2x1, bằng 120
Giai thừa của 0 được đồng ý là 1
Hãy viết một hàm sẽ giải quyết vấn đề cho chúng ta
def fibonacci[n]: """ Returns Fibonacci Number at nth position using recursion""" if n == 0: return 0 elif n == 1: return 1 else: return fibonacci[n - 1] + fibonacci[n - 2] for i in range[10]: print[fibonacci[i], end=" "] # Output: 0 1 1 2 3 5 8 13 21 345
Trong hàm này, chúng ta sử dụng vòng lặp
def fibonacci[n]: """ Returns Fibonacci Number at nth position using recursion""" if n == 0: return 0 elif n == 1: return 1 else: return fibonacci[n - 1] + fibonacci[n - 2] for i in range[10]: print[fibonacci[i], end=" "] # Output: 0 1 1 2 3 5 8 13 21 348 để tính giai thừa của một số. Hàm này có thể trông hơi choáng ngợp, nhưng với đệ quy, chúng ta có thể tiết kiệm dòng và khả năng đọc bằng cách chia nhỏ vấn đề
def fibonacci[n]: """ Returns Fibonacci Number at nth position using recursion""" if n == 0: return 0 elif n == 1: return 1 else: return fibonacci[n - 1] + fibonacci[n - 2] for i in range[10]: print[fibonacci[i], end=" "] # Output: 0 1 1 2 3 5 8 13 21 346
Hàm trên là hàm đệ quy tính giai thừa của một số. Nếu chúng ta so sánh cả hai chức năng, thì chức năng sau dễ đọc và dễ hiểu hơn
Sự khác nhau giữa vòng lặp và đệ quy
Đệ quy không cần thỏa mãn điều kiện mới chạy được
Đệ quy có giới hạn để thực hiện nó. Điều này chủ yếu là do các chức năng được lưu trữ trên Bộ nhớ ngăn xếp, có kích thước tối đa. Hàm đệ quy sẽ liên tục gọi chính nó, đẩy các giá trị và phiên bản mới của hàm vào ngăn xếp, điều này cuối cùng có thể dẫn đến lỗi Tràn ngăn xếp
Để so sánh, các vòng lặp được lưu trữ trong bộ nhớ động, nơi các biến có thể được tạo vô thời hạn
Việc thực hiện một hàm đệ quy tương đối chậm hơn so với các vòng lặp
Đệ quy thường dễ đọc hơn vòng lặp
Đệ quy đắt hơn, tính toán khôn ngoan hơn so với các vòng lặp, nhưng có thể được tăng tốc bằng cách ghi nhớ
Bạn có thể sử dụng vòng lặp for trong Python đệ quy không?
Đệ quy rất giống với một vòng lặp trong đó hàm được gọi trong mỗi lần lặp. Đó là lý do tại sao chúng ta luôn có thể sử dụng vòng lặp để thay thế cho hàm đệ quy Python .Bạn có thể sử dụng vòng lặp for trong đệ quy không?
Bạn chắc chắn có thể sử dụng vòng lặp trong hàm đệ quy . Điều khiến một hàm trở nên đệ quy chỉ là thực tế là hàm đó tự gọi chính nó tại một số điểm trong đường dẫn thực thi của nó. Tuy nhiên, bạn nên có một số điều kiện để ngăn các cuộc gọi đệ quy vô hạn mà chức năng của bạn không thể trả về. Lưu câu trả lời này.Cái nào tốt hơn cho vòng lặp hoặc đệ quy?
Nếu vấn đề ban đầu phức tạp và lặp đi lặp lại, thì chúng ta sử dụng phương pháp chia để trị và sau đó giải quyết vấn đề đó. Vì vậy, trong trường hợp này, chúng tôi thích sử dụng đệ quy hơn là lặpĐệ quy có nhanh hơn phép lặp trong Python không?
Lặp nhanh hơn và hiệu quả hơn đệ quy . Việc tối ưu hóa các mã lặp lại dễ dàng hơn và chúng thường có độ phức tạp về thời gian đa thức. Chúng được sử dụng để lặp lại các phần tử có trong cấu trúc dữ liệu như mảng, tập hợp, bản đồ, v.v.