Đệ quy có nhanh trong python không?

Một chương trình máy tính bao gồm các hướng dẫn từng dòng. Máy tính thực hiện các lệnh đó theo từng dòng. Tuy nhiên, một số hướng dẫn có thể lặp đi lặp lại với một mẫu chung. Đệ quy hoặc phép lặp giúp một người viết một vài dòng mã để thực hiện các tác vụ lặp đi lặp lại như vậy. Giả sử một danh sách Python có các phần tử năm chuỗi. Chúng tôi muốn in các phần tử một trong một dòng. Hoạt động này cần năm dòng mã

 flowers = ['lily', 'tulip', 'rose', 'lavender', 'dandelion'] 
 print[flowers[0]]
 print[flowers[1]]
 print[flowers[2]]
 print[flowers[3]]
 print[flowers[4]] 

đầu ra

Có thể quan sát thấy rằng năm dòng mã theo cùng một mẫu. Sự khác biệt duy nhất trong mỗi dòng là chỉ mục của các phần tử danh sách. Nếu danh sách này chứa 100 hoặc 1000 phần tử thì sao? . Những loại vấn đề này được giải quyết thông qua phép lặp hoặc đệ quy. Ở đây, dạng lặp của các mã trên như sau

 for flower in flowers:
   print[flower] 

đầu ra

Hai dòng này là đủ để hoàn thành nhiệm vụ ngay cả khi danh sách chứa một triệu phần tử

Đệ quy trong Python

Đệ quy là một cách tiếp cận chức năng để chia nhỏ một bài toán thành một tập hợp các bài toán con đơn giản có mẫu giống hệt nhau và giải chúng bằng cách gọi một bài toán con bên trong một bài toán con khác theo thứ tự tuần tự. Đệ quy được thực hiện bằng cách xác định một hàm có thể giải một bài toán con tại một thời điểm. Ở đâu đó bên trong hàm đó, nó gọi chính nó nhưng giải một bài toán con khác. Do đó, cuộc gọi đến chính nó tiếp tục cho đến khi một số tiêu chí giới hạn được đáp ứng.  

Cuộc gọi đầu tiên đến hàm đệ quy từ chương trình chính sẽ chỉ được trả về sau khi tất cả các cuộc gọi phụ kết thúc. Do đó, Python lưu trữ kết quả của tất cả các bài toán con trong bộ nhớ tạm thời, thực hiện một số phép tính số học [nếu cần] và giải phóng bộ nhớ sau khi kết thúc đệ quy

Lặp lại trong Python

Các phép lặp được thực hiện thông qua các vòng lặp 'for' và 'while'. Lặp đi lặp lại thực hiện một tập hợp các hướng dẫn cho đến khi một số tiêu chí giới hạn được đáp ứng. Trái ngược với đệ quy, phép lặp không yêu cầu bộ nhớ tạm thời để lưu kết quả của mỗi lần lặp. Thay vào đó, các lập trình viên nên định nghĩa một biến [một số, hoặc danh sách, hoặc chuỗi hoặc bất kỳ loại dữ liệu có thể thay đổi nào] trước khi bắt đầu các lệnh gọi lặp để thu thập kết quả [nếu có các kết quả số học như vậy] trong mỗi lần lặp.  

Hơn nữa, một tác vụ lặp có thể được hoàn thành bằng vòng lặp 'for' hoặc vòng lặp 'while'. Vòng lặp 'for' lặp qua một chuỗi [chẳng hạn như danh sách, chuỗi, bộ và phạm vi]. Nó kết thúc vòng lặp khi không còn phần tử nào trong dãy. Nó tự động đi qua các phần tử liên tiếp. Nhưng một vòng lặp 'trong khi' cần khởi tạo một trình vòng lặp và tăng thủ công giống nhau. Vòng lặp 'while' được thực thi cho đến khi thỏa mãn điều kiện dựa trên trình vòng lặp

Đệ quy vs Lặp lại

Vì Python không lưu trữ bất cứ thứ gì về các bước lặp trước đó, nên phép lặp khá nhanh hơn và tiết kiệm bộ nhớ hơn so với đệ quy. Trong thực tế, hầu như tất cả các phép lặp đều có thể được thực hiện bằng truy hồi và ngược lại. Một số tác vụ có thể được thực hiện bằng đệ quy đơn giản hơn lặp lại do gọi nhiều lần cùng một chức năng. Mặt khác, một số tác vụ có thể được thực hiện bằng phép lặp theo cách tao nhã hơn là đệ quy. Xét về độ phức tạp về thời gian và hạn chế về bộ nhớ, phép lặp được ưu tiên hơn đệ quy. Cả vòng lặp đệ quy và 'trong khi' trong lần lặp có thể dẫn đến tình huống cuộc gọi vô hạn nguy hiểm. Nếu tiêu chí giới hạn không được đáp ứng, vòng lặp while hoặc hàm đệ quy sẽ không bao giờ hội tụ và dẫn đến gián đoạn thực thi chương trình.  

Vì đệ quy được thực thi bằng cách định nghĩa một hàm, nên hàm này có thể được gọi bất cứ khi nào được yêu cầu ở bất kỳ đâu trong chương trình. Mã lặp phải được xây dựng tại địa điểm yêu cầu. Tuy nhiên, một bộ mã lặp có thể được khái quát hóa bằng cách khai báo bên trong một hàm Python điển hình [không phải hàm đệ quy]

Các ví dụ sau đây sẽ giúp hiểu rõ hơn về các phương pháp lập trình đệ quy và lặp lại

Giai thừa của một số nguyên

Tính giai thừa là một trường hợp sử dụng phổ biến để hiểu phép lặp và đệ quy. Chẳng hạn, chúng ta muốn tính giai thừa của 10. Nó có thể được xác định là 1*2*3*4*5*6*7*8*9*10 = 3628800. Có thể xem đây là 10 bài toán con nhân một số nguyên tăng dần thành kết quả cuối cùng

 # using a for loop
 n = 10
 result = 1
 for i in range[1,n+1]:
   result *= i
 print[result] 

đầu ra

Một hàm phạm vi được triển khai trong vòng lặp 'for' vì nó yêu cầu một chuỗi để lặp lại. Hàm phạm vi cung cấp các giá trị lặp đi lặp lại từ 1 đến 10, mỗi lần một giá trị. Nó dừng lặp lại khi hàm phạm vi ngừng cung cấp giá trị [i. e. , lúc 10]

 # using a while loop
 n = 10
 result = 1
 i = 1
 while i