Đệ quy trực tiếp trong Python là gì?
Một hàm được gọi là đệ quy đuôi, nếu không có thao tác nào đang chờ xử lý khi hàm đệ quy trả về trình gọi của nó Show
Để làm cho nó đệ quy đuôi, thông tin về các tác vụ đang chờ xử lý phải được theo dõi
Nếu bạn quan sát, 'fact2' có cú pháp tương tự như fact ban đầu. Bây giờ, 'thực tế' trong trường hợp đệ quy đuôi không có các phép tính/hoạt động đang chờ xử lý để thực hiện khi trả về từ các lệnh gọi hàm đệ quy Đệ quy tuyến tính và câyTùy thuộc vào cấu trúc, các cuộc gọi hàm đệ quy thực hiện hoặc phát triển, nó có thể là tuyến tính hoặc phi tuyến tính Khi nào không sử dụng đệ quy?Về cơ bản, bất kỳ vấn đề nào có thể được giải quyết bằng đệ quy cũng có thể được giải quyết bằng phép lặp. Mặc dù đối với một số ứng dụng nhất định như Tháp Hà Nội, một số vấn đề về trí tuệ nhân tạo, v.v., đệ quy được sử dụng vì nó xác định vấn đề một cách tự nhiên, nhưng vẫn có những thời điểm nhất định không nên sử dụng đệ quy Đệ quy trong Python hoặc bất kỳ ngôn ngữ lập trình nào khác là một quá trình trong đó một hàm gọi chính nó một hoặc nhiều lần trong phần thân của nó. Nó có thể gọi chính nó trực tiếp hoặc gián tiếp Nếu bất kỳ định nghĩa hàm nào đáp ứng điều kiện của đệ quy, chúng tôi gọi nó là hàm đệ quy Hàm đệ quy là hàm gọi hoặc gọi chính nó ít nhất một lần trong phần thân của nó. Thông thường, giá trị trả về là giá trị trả về của lệnh gọi hàm Hàm đệ quy về cơ bản là một chuỗi các hàm gọi đến cùng một hàm. Nó hoạt động giống như vòng lặp, có hoặc không có điều kiện kết thúc. Nó gọi chính nó, trực tiếp hoặc gián tiếp, thông qua một chức năng khác Một ví dụ nổi tiếng thường được sử dụng để mô tả đệ quy trong Python hoặc các ngôn ngữ lập trình khác là phép tính giai thừa (giai thừa cho giá trị 6 là 6 * 5 * 4 * 3 * 2 * 1) Đệ quy trong Python là một kỹ thuật cơ bản và rất hiệu quả của lập trình máy tính được sử dụng để giải quyết một loại vấn đề lập trình phức tạp cụ thể. Nó phù hợp nhất khi chúng ta cần gọi lặp đi lặp lại cùng một phương thức với các tham số khác nhau Đệ quy cung cấp một số lợi thế cho các lập trình viên, chẳng hạn như để phát triển mã sạch và ngắn và cũng giúp lập trình viên tránh các vòng lặp Đôi khi, khái niệm đệ quy có thể hơi khó hiểu đối với người mới bắt đầu. Nhưng, sự thật là chúng ta có thể dễ dàng giải quyết nhiều vấn đề lập trình phức tạp với sự trợ giúp của kỹ thuật đệ quy Một số bài toán tính toán như tháp Hà Nội, DFS, duyệt cây, quay lui, v.v. mà các kỹ thuật khác có thể giải quyết được giải quyết tốt hơn bằng đệ quy Cú pháp đệ quy trong PythonTrong Python, chúng ta có thể chia cú pháp đệ quy thành hai loại
Đệ quy trực tiếp . Nó xảy ra khi một chức năng gọi chính nó trực tiếp từ bên trong cơ thể của chính nó. Cú pháp cơ bản để khai báo một hàm đệ quy trong Python tự gọi trực tiếp như sau. def recursiveFunction(param): # function code recursiveFunction(param) # recursive call. recursiveFunction(arg) # function calling with passing argument values. Trong cú pháp trên, recursiveFunction() là một hàm đệ quy đang gọi chính nó bên trong hàm. Nhìn vào hình bên dưới minh họa hoạt động đơn giản của đệ quy trong Python Hãy lấy một ví dụ đơn giản dựa trên đệ quy trực tiếp def recursiveFunction(): print('Hello') recursiveFunction() # recursive call. recursiveFunction() # calling function. Output: Hello Hello . . . Đệ quy gián tiếp . Đệ quy này xảy ra khi một hàm gọi một hàm khác, đổi lại hàm này sẽ gọi lại hàm đó. Ví dụ khi hàm A gọi hàm B khác và hàm B gọi hàm A thì ta gọi đó là cách gọi gián tiếp. Cú pháp cơ bản để khai báo một hàm đệ quy gọi chính nó một cách gián tiếp nhiều lần như sau. def A_function(parameter): # function code. B_function(parameter) def B_function(parameter): # function code. A_function(parameter) Hãy lấy một mã ví dụ đơn giản dựa trên lệnh gọi đệ quy gián tiếp def A_function(): print('A') B_function() # recursive call. def B_function(): print('B') A_function() # recursive call. A_function() # function calling. Output: A B A B . . . . Như bạn sẽ thấy khi thực thi đoạn mã đệ quy trên trên bàn điều khiển, đoạn mã này đang thực thi vô thời hạn. Cuối cùng, trình thông dịch Python tạo ra lỗi (RecursionError. vượt quá độ sâu đệ quy tối đa trong khi gọi một đối tượng Python). Để khắc phục vấn đề này, chúng ta cần chấm dứt đệ quy. Hãy hiểu nó Làm cách nào để dừng đệ quy trong Python?Khi định nghĩa hàm đệ quy trong Python hoặc các ngôn ngữ lập trình khác, cần chỉ định điều kiện kết thúc. Nếu chúng tôi đặt điều kiện kết thúc trong đệ quy, điều đó có nghĩa là mã đang hoạt động bình thường. Nếu chúng ta không đặt điều kiện như vậy, thì có thể xảy ra lệnh gọi “hàm” vô hạn Vì lý do này, chúng ta cần chỉ định một điều kiện để kết thúc đệ quy. Điều kiện này được gọi là trường hợp cơ sở hoặc điểm dừng Trường hợp cơ sở hoặc trường hợp đầu cuối là điều kiện ngăn chặn đệ quy vô hạn. Trong trường hợp thiết bị đầu cuối, không có lời gọi hàm đệ quy nào xảy ra. Không có trường hợp đầu cuối, chúng ta không bao giờ có thể dừng việc thực thi hàm đệ quy Một hàm đệ quy được xác định rõ phải thỏa mãn hai điều kiện là
Xem xét mã ví dụ sau được đưa ra bên dưới, trong đó chúng tôi sẽ hiển thị một thông báo bốn lần bằng phương pháp đệ quy ví dụ 1. count = 0 def display(): global count count += 1 if count <= 4: # base case. print("Hello world") display() # recursive call. display() # normal method call. Output: Hello world Hello world Hello world Hello world Trong đoạn mã chương trình trên, chúng ta đã sử dụng một “câu lệnh if” có điều kiện trong thân hàm để kiểm tra số đếm có nhỏ hơn 4 không. Đây là điều kiện cơ bản Miễn là điều kiện này còn đúng, hàm đệ quy display() sẽ tự gọi. Trên mỗi lần lặp, số đếm tăng thêm 1 và hàm display() được gọi cho đến khi số đếm bằng bốn Khi đếm đến 5, câu lệnh điều kiện đánh giá là sai. Vì điều kiện cơ sở đã thỏa mãn nên hàm sẽ không gọi nữa ví dụ 2 Hãy viết một chương trình rất đơn giản để in các số đếm ngược từ 5 đến 1 dựa trên đệ quy def countDown(num): # Displaying the number. print(num, end= " ") # Decreasing the number value by 1. newNum = num - 1 # Base case or stopping point. if newNum > 0: countDown(newNum) countDown(5) # calling function. Output: 5 4 3 2 1 Trong đoạn mã chương trình trên, chúng ta đã chuyển số 5 làm đối số trong khi gọi một hàm. Bên trong thân hàm, chúng ta đã sử dụng một “câu lệnh if” có điều kiện để kiểm tra xem đối số được truyền vào có lớn hơn 0 không. Đây là điều kiện cơ bản Miễn là Python đánh giá điều kiện này là đúng, thì hàm đệ quy CountDown() sẽ tự gọi. Trên mỗi lần lặp, giá trị số giảm đi 1 và hàm countDown() được gọi cho đến khi số dương Xem các bước sau để hiểu rõ các cuộc gọi đệ quy
Khi số đạt đến 0, "câu lệnh if" có điều kiện đánh giá là sai. Vì điều kiện cơ sở được đáp ứng, chức năng không được gọi nữa ví dụ 3 Viết chương trình đếm ngược các số đến 0 bằng phương pháp đệ quy def recursiveFunction(): print('Hello') recursiveFunction() # recursive call. recursiveFunction() # calling function.0 def recursiveFunction(): print('Hello') recursiveFunction() # recursive call. recursiveFunction() # calling function.1 Lưu ý . Nếu chúng ta thực hiện một lời gọi đệ quy bên trong khối if, thì khối other sẽ chứa logic của điều kiện cơ sở. Nếu chúng ta thực hiện lời gọi đệ quy bên trong khối other, khối if sẽ chứa logic của điều kiện cơ sở. Các loại đệ quy trong PythonCó hai loại đệ quy trong Python. họ đang
Hãy hiểu từng cái một với sự trợ giúp của các ví dụ đệ quy đầuTrong kiểu đệ quy này, lời gọi đệ quy xảy ra trước các xử lý khác trong hàm. Ví dụ def recursiveFunction(): print('Hello') recursiveFunction() # recursive call. recursiveFunction() # calling function.2_______3_______3 Trong mã chương trình trên, đầu tiên các cuộc gọi đệ quy xảy ra và sau đó quá trình in diễn ra. Do đó, giá trị cuối cùng của num, i. e. 1, được hiển thị đầu tiên. Do đó, số in theo thứ tự từ 1 đến 6 đệ quy đuôiTrong loại đệ quy này, quá trình xử lý xảy ra trước khi gọi đệ quy. Đệ quy đuôi hoạt động giống như một vòng lặp trong đó hàm thực thi tất cả các câu lệnh trước khi gọi đệ quy. Hãy lấy một ví dụ dựa trên nó def recursiveFunction(): print('Hello') recursiveFunction() # recursive call. recursiveFunction() # calling function.4_______3_______5 Trong mã chương trình này, quá trình in đầu tiên diễn ra và sau đó xảy ra lệnh gọi đệ quy. Do đó, giá trị đầu tiên của n, i. e. 1, được hiển thị đầu tiên trên bảng điều khiển. Do đó, các số in theo thứ tự từ 1 đến 10 Chương trình giai thừa sử dụng đệ quy trong PythonSau đây, chúng ta sẽ tìm hiểu cách tính giai thừa của một số bằng phương pháp đệ quy. Giai thừa của một số là tích của số đó với tất cả các số nguyên dương đứng sau nó. Chúng tôi đại diện cho nó như là n Ví dụ: giai thừa của số 4 được biểu thị bằng 4. Nó bằng 4 * 3 * 2 * 1, kết quả là 24. Các bước cơ bản để tính giai thừa của bất kỳ số n nào, như sau (n) * (n – 1) * (n – 2) * (n – 3) *. . . . . * 1 Trước hết hãy viết chương trình tính giai thừa của một số bằng vòng lặp for Mã chương trình def recursiveFunction(): print('Hello') recursiveFunction() # recursive call. recursiveFunction() # calling function.6 def recursiveFunction(): print('Hello') recursiveFunction() # recursive call. recursiveFunction() # calling function.7 Trong đoạn mã chương trình trên, chúng tôi đã lấy số 7 làm đầu vào từ người dùng và lưu trữ nó trong một biến num. Sau đó, chúng ta đã gọi hàm bằng cách truyền giá trị của biến num Bên trong hàm, chúng tôi đã kiểm tra xem số đó là âm, 0 hay dương bằng cách sử dụng câu lệnh if elif other. Bên trong khối other, chúng ta đã sử dụng hàm for loop và range() để tính giai thừa của một số. Nhìn vào các bước sau trong bảng dưới đây Phép lặp * i (giá trị trả về)i = 11 * 1 = 1i = 21 * 2 = 2i = 32 * 3 = 6i = 43 * 4 = 24Giai thừa của một số bằng phương pháp đệ quyBây giờ hãy viết mã để tính giai thừa của một số bằng cách sử dụng đệ quy Mã chương trình def recursiveFunction(): print('Hello') recursiveFunction() # recursive call. recursiveFunction() # calling function.8 def recursiveFunction(): print('Hello') recursiveFunction() # recursive call. recursiveFunction() # calling function.9 Trong chương trình trên, fact() là một hàm đệ quy, vì nó gọi chính nó. Khi chúng ta gọi hàm này bằng cách chuyển giá trị dương làm đối số, nó sẽ tự gọi đệ quy bằng cách giảm số Mỗi lệnh gọi hàm đệ quy nhân một số với giai thừa của (số – 1) cho đến khi số đó bằng 1. Khi số bằng 1, đệ quy kết thúc. Đây là điều kiện cơ bản Mỗi hàm đệ quy phải có một điều kiện cơ sở để ngăn đệ quy vô hạn. Nhìn vào các bước dưới đây của các cuộc gọi đệ quy
Lúc đầu, bạn có thể thấy rằng hiểu logic của hàm đệ quy khó hơn, nhưng chúng sẽ trở nên dễ dàng hơn khi thực hành một số chương trình Ưu điểm của đệ quy trong PythonCó những ưu điểm sau khi sử dụng kỹ thuật đệ quy trong lập trình Python. Họ như
Nhược điểm của đệ quy trong PythonNgoài nhiều ưu điểm của việc sử dụng đệ quy, cũng có những nhược điểm sau khi sử dụng nó trong lập trình Python. Họ như Đệ quy trực tiếp là gì?Nếu một hàm gọi chính nó , nó được gọi là đệ quy trực tiếp. Điều này dẫn đến một cuộc gọi đệ quy một bước. hàm thực hiện một cuộc gọi đệ quy bên trong thân hàm của chính nó.
Đệ quy trực tiếp và gián tiếp là gì?Sự khác biệt giữa đệ quy trực tiếp và gián tiếp là gì? . Một hàm fun được gọi là đệ quy gián tiếp nếu nó gọi một hàm khác chẳng hạn fun_new và fun_new gọi fun trực tiếp hoặc gián tiếp
Hai loại đệ quy Python là gì?Chúng có hai loại. đệ quy gián tiếp và trực tiếp .
Các loại đệ quy trực tiếp là gì?Hai loại đệ quy là gì? . Đệ quy trực tiếp về cơ bản là một hàm gọi chính nó trong một lệnh gọi đệ quy một bước trong khi đệ quy gián tiếp là khi một hàm gọi một hàm khác để hoạt động trên hàm ban đầu trong một lệnh gọi đệ quy hai bước |