Một ví dụ về thế giới vật chất sẽ là đặt hai gương song song đối diện nhau. Bất kỳ đối tượng nào ở giữa chúng sẽ được phản ánh đệ quy
Hàm đệ quy Python
Trong Python, chúng ta biết rằng một hàm có thể gọi các hàm khác. Hàm thậm chí có thể gọi chính nó. Các loại cấu trúc này được gọi là hàm đệ quy
Hình ảnh sau đây cho thấy hoạt động của một hàm đệ quy có tên là recurse
Sau đây là một ví dụ về 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 [ký hiệu là 6. ] là 1*2*3*4*5*6 = 720
Ví dụ về hàm đệ quy
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
The factorial of 3 is 6
Trong ví dụ trên, factorial[] là một hàm đệ quy vì nó gọi chính nó
Khi ta gọi hàm này với số nguyên dương thì nó sẽ gọi đệ quy chính nó bằng cách giảm số
Mỗi hàm nhân một 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 trong 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 thể hiện quy trình từng bước về những gì đang diễn ra
Đệ quy của chúng tôi kết thúc khi số giảm xuống 1. Đây được gọi là điều kiện cơ bản
Mỗi hàm đệ quy phải có một điều kiện cơ bản để dừng đệ quy, nếu không thì hàm sẽ tự gọi nó vô hạn
Trình thông dịch Python giới hạn độ sâu của đệ quy để giúp tránh các đệ quy vô hạn, dẫn đến tràn ngăn xếp
Theo mặc định, độ sâu đệ quy tối đa là 1000. Nếu giới hạn bị vượt qua, kết quả là
The factorial of 3 is 60. Hãy xem xét một điều kiện như vậy
Trong thế giới lập trình đệ quy là một khái niệm cơ bản. Trong hầu hết các cuộc phỏng vấn Python, nó có thể được hỏi. Dù là lập trình viên hay nhà khoa học dữ liệu thì ai cũng nên biết khái niệm này. Không chỉ các thuật toán tìm kiếm và sắp xếp là đệ quy, mà mọi cuộc phỏng vấn Python sẽ bao gồm một số câu hỏi dựa trên đệ quy. Điều này làm cho đệ quy trở thành một khái niệm quan trọng cần sửa đổi trước bất kỳ cuộc phỏng vấn viết mã nào
Ở đây tôi sẽ cố gắng giải thích đệ quy theo cách đơn giản nhất có thể bằng cách chia đệ quy thành các bước
- Đệ quy là gì?
- Tại sao chúng ta sử dụng đệ quy?
- Đệ quy trong Python
- Ví dụ về đệ quy
Đệ quy là gì?
Đệ quy là một khái niệm trong toán học mà chúng ta cũng sử dụng trong lập trình. Đệ quy là quá trình xác định một vấn đề về chính nó. Đây là định nghĩa đơn giản nhất của đệ quy
Trong lập trình, đệ quy là Quá trình trong đó một hàm gọi chính nó một cách trực tiếp hoặc gián tiếp và hàm tương ứng được gọi là hàm đệ quy
Vì vậy, kết luận là đệ quy được xác định cái mới bằng cách sử dụng chính nó
Tại sao chúng ta sử dụng đệ quy?
Hầu hết các vấn đề có thể giải quyết được mà không cần đệ quy. Vì vậy, nói đúng ra, đệ quy thường không cần thiết. Đệ quy được thực hiện để giải quyết các vấn đề có thể được chia thành các vấn đề nhỏ hơn, lặp đi lặp lại. Nó đặc biệt tốt khi làm việc với những thứ có thể có nhiều nhánh và quá phức tạp đối với cách tiếp cận lặp lại
ưu
- Nhanh hơn khi được tối ưu hóa
- ít mã hơn. Bạn có thể viết mã đệ quy nhanh hơn và để gỡ lỗi, bạn có ít mã hơn so với mã lặp
- tuyên bố
- Sắp xếp và tìm kiếm hiệu quả
Nhược điểm
- Độ sâu đệ quy tối đa
- Do nhầm lẫn hoặc vô tình sử dụng đệ quy mà không có điều kiện cơ sở
- Tiêu thụ bộ nhớ nhiều hơn
Đệ quy trong Python
Khi bạn gọi một hàm trong Python, trình thông dịch sẽ tạo một không gian tên cục bộ mới, để các tên được xác định trong hàm đó không xung đột với các tên giống hệt nhau được xác định ở nơi khác
def recurse[]:
x = 5
recurse[]khi recurse
The factorial of 3 is 61 thực hiện lần đầu tiên, nó sẽ tạo không gian tên cục bộ trong python và 10 được gán cho x. Sau cái này recurse
The factorial of 3 is 61 tự gọi đệ quy. Lần thứ hai recurse
The factorial of 3 is 61 chạy, trình thông dịch tạo không gian tên thứ hai và gán
The factorial of 3 is 64 cho
The factorial of 3 is 65 ở đó. Hai phiên bản của tên
The factorial of 3 is 65 này khác biệt với nhau và có thể cùng tồn tại mà không xung đột vì chúng nằm trong các không gian tên riêng biệt
Sau khi chạy recurse
The factorial of 3 is 61 nó sẽ tự gọi đi gọi lại nhưng python nó hiện ra traceback vì chạy hoài không được
RecursionError: maximum recursion depth exceededBởi vì có giới hạn đệ quy theo hệ thống của bạn
Về lý thuyết, nó sẽ chạy mãi mãi nhưng thực tế không có gì là mãi mãi vì giới hạn bộ nhớ. Python không cho phép điều đó xảy ra. Trình thông dịch giới hạn số lần tối đa mà một hàm có thể gọi chính nó theo cách đệ quy và khi đạt đến giới hạn đó, nó sẽ đưa ra một ngoại lệ
RecursionError: maximum recursion depth exceeded0Vì vậy, để ngăn chức năng của chúng tôi chạy mãi mãi, phải có một điều kiện cơ bản
trường hợp cơ sở
Điều kiện cơ sở sẽ giúp kết thúc quá trình đệ quy hoặc dừng chức năng bằng cách gọi đi gọi lại chính nó. Có một hoặc nhiều trường hợp cơ sở có thể giải trực tiếp mà không cần đệ quy thêm
trường hợp đệ quy
Khi trạng thái mong muốn chưa đạt được và hàm chuyển sang một bước đệ quy khác. Mỗi cuộc gọi đệ quy di chuyển giải pháp dần dần đến gần trường hợp cơ sở
Ví dụ về đệ quy
Đếm ngược đến số không
Trong ví dụ trên, nó sẽ yêu cầu người dùng nhập số. Trường hợp cơ sở sẽ là khi n = 0 và đệ quy sẽ dừng ở đó. Trong trường hợp đệ quy, một giá trị nhỏ hơn giá trị hiện tại của
RecursionError: maximum recursion depth exceeded1 được chuyển thành đối số và giống như vậy, đệ quy sẽ tiến gần hơn đến trường hợp cơ sởtính giai thừa
Ví dụ tiếp theo liên quan đến khái niệm toán học về giai thừa. Giai thừa của số nguyên dương n, ký hiệu là n. và được tính như
n! = n*[n-1]*[n-2]...3*2*1Nói cách khác, n. là tích của tất cả các số nguyên từ 1 đến n, kể cả
Có thể có rất nhiều ví dụ về đệ quy nhưng câu hỏi đặt ra là 'Có thực sự cần thiết để triển khai đệ quy không?'. Bởi vì hai mã trên cũng có thể được viết bằng vòng lặp for. Điều thứ hai là tốc độ thực hiện. Có thể có sự khác biệt đáng kể về hiệu suất giữa các giải pháp đệ quy và không đệ quy [lặp đi lặp lại]
Đây là một trong vài ví dụ đơn giản về đệ quy
Tôi đang liệt kê thêm các ví dụ mà bạn có thể thực hành hoặc học đệ quy để đạt được kiến thức chuyên môn. Tôi không giải thích các ví dụ này vì có thể bất kỳ người mới bắt đầu nào đọc bài viết này sẽ bối rối khi nhìn thấy các ví dụ trước về đệ quy trong cấu trúc dữ liệu. Để làm cho bài viết này đơn giản, tôi chỉ viết tên của các ví dụ