Hướng dẫn what is iterative and recursive in python? - lặp đi lặp lại và đệ quy trong python là gì?

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 hướng dẫn đó 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ô hình chung. Đệ quy hoặc lặp lại giúp người ta 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 với các yếu tố năm chuỗi. Chúng tôi muốn in các yếu 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]) 

Output:

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ỉ số của các yếu tố danh sách. Điều gì sẽ xảy ra nếu danh sách này chứa 100 hoặc 1000 yếu tố? Mã hóa sẽ trở thành một nhiệm vụ tẻ nhạt. Những loại vấn đề này được giải quyết thông qua việc lặp lại hoặc đệ quy. Ở đây, dạng lặp của các mã trên như sau.

Belamy

Đăng ký liều hàng tuần của bạn về những gì đang hoạt động trong công nghệ mới nổi.

 for flower in flowers:
   print(flower) 

Output:

Hai dòng này là đủ để đạt được nhiệm vụ ngay cả khi danh sách chứa một triệu yếu tố!

Đệ quy trong Python

Recursion là một cách tiếp cận chức năng để chia một vấn đề thành một tập hợp các bài toán con đơn giản với một mô hình giống hệt nhau và giải quyết chúng bằng cách gọi một biểu tượng con bên trong một vấn đề khác theo thứ tự tuần tự. Đệ quy được thực thi bằng cách xác định một hàm có thể giải quyết một vấn đề nhỏ tại một thời điểm. Ở đâu đó bên trong chức năng đó, nó tự gọi mình nhưng giải quyết một vấn đề nhỏ 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. & NBSP;

Cuộc gọi đầu tiên đến một chức năng đệ quy từ chương trình chính sẽ chỉ được trả lại sau khi tất cả các phân nhóm kết thúc. Do đó, Python lưu trữ kết quả của tất cả các vấn đề phụ trong bộ nhớ tạm thời, thực hiện một số hoạt động 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 lần lặp được thực hiện thông qua ‘cho các vòng lặp và‘ trong khi các vòng lặp. Lặp lại thực hiện một tập hợp các hướng dẫn liên tục cho đến khi một số tiêu chí giới hạn được đáp ứng. Trái ngược với đệ quy, việc lặp lại không yêu cầu bộ nhớ tạm thời để giữ kết quả của từng lần lặp. Thay vào đó, các lập trình viên nên xác định 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 cuộc gọi lặp để thu thập kết quả (nếu có kết quả số học như vậy) trong mỗi lần lặp. & NBSP;

Hơn nữa, một nhiệm vụ lặp có thể được thực hiện bằng một vòng lặp ’cho vòng lặp hoặc một vòng lặp trong khi. Một vòng lặp cho vòng lặp lặp qua một chuỗi (như một danh sách, chuỗi, tuple và phạm vi). Nó chấm dứt vòng lặp khi không còn phần tử trong chuỗi. Nó tự động đi qua các yếu tố liên tiếp. Nhưng một vòng lặp ’trong khi vòng lặp cần khởi tạo của một trình lặp và sự gia tăng thủ công giống nhau. Một vòng lặp trong khi vòng lặp được thực thi cho đến khi một điều kiện dựa trên vòng lặp được thỏa mãn.

Đệ quy so với lặp lại

Vì Python không lưu trữ bất cứ điều gì về các bước lặp trước đó, việc lặp lại khá nhanh và tiết kiệm bộ nhớ so với đệ quy. Trong thực tế, hầu hết tất cả các lần lặp có thể được thực hiện bởi các đệ quy và ngược lại. Một số tác vụ có thể được thực hiện bằng cách đệ quy đơn giản hơn so với lặp lại do nhiều lần gọi cùng một chức năng. Mặt khác, một số nhiệm vụ có thể được thực hiện bằng cách lặp một cách thanh lịch hơn là đệ quy. Về độ phức tạp về thời gian và các ràng buộc bộ nhớ, việc lặp lại được ưu tiên hơn đệ quy. Cả đệ quy và ‘trong khi các vòng lặp trong lần lặp có thể dẫn đến tình huống gọi vô hạn nguy hiểm. Nếu các tiêu chí giới hạn không được đáp ứng, một vòng lặp trong thời gian hoặc một hàm đệ quy sẽ không bao giờ hội tụ và dẫn đến việc phá vỡ trong việc thực hiện chương trình. & NBSP;

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

Các ví dụ sau đây sẽ cho sự hiểu biết tốt hơn về các phương pháp lập trình đệ quy và lặp lại.

Đơn vị của một số nguyên

Tính toán giai thừa là một trường hợp sử dụng phổ biến để hiểu lặp lại và đệ quy. Chẳng hạn, chúng tôi muốn tính toán giai đoạn 10. Nó có thể được xác định là 1*2*3*4*5*6*7*8*9*10 = 3628800. Điều này có thể được xem là 10 vấn đề phụ của việc nhân lên số nguyên đến một 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) 

Output:

Một hàm phạm vi được thực hiện trong một vòng lặp for 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. Nó dừng lặp lại khi hàm phạm vi ngừng cung cấp các giá trị (tức là, ở mức 10).

 # using a while loop
 n = 10
 result = 1
 i = 1
 while i <= n:
   result *= i
   i += 1
 print(result) 

Output:

Trong một vòng lặp trong khi một vòng lặp, một trình lặp tôi được giới thiệu và tăng lên qua mỗi vòng lặp. Trong khi vòng lặp dừng lặp lại khi giá trị của I vượt quá số nguyên 10.

 # using recursion
 def Factorial(n):
   # declare a base case (a limiting criteria)
   if n == 1:
     return 1
   # continue with general case
   else:
     return n * Factorial(n-1)
 
 print(Factorial(10)) 

Output:

Một hàm đệ quy, được đặt tên là Factorial (), được xác định với các tiêu chí giới hạn của n = 1. Đầu tiên, nó cố gắng tìm ra giai đoạn 10. Factorial (10) được chia thành 10 * giai thừa (9). Hơn nữa, giai thừa (9) được chia thành 9 * giai thừa (8), v.v. Khi giai thừa (1) được gọi, nó dừng đệ quy. & Nbsp;

Factorial (10) đang chờ giá trị của giai thừa (9). Factorial (9) đang chờ giá trị của giai thừa (8), v.v. Do đó, một khi các tiêu chí giới hạn (ở đây, n = 1) đạt được, nó bắt đầu trả về các giá trị.

Đảo ngược một chuỗi

Một chuỗi hoặc một chuỗi có thể được đảo ngược thông qua lặp hoặc đệ quy. Ở đây, chúng tôi xác định một hàm có một chuỗi và trả về dạng đảo ngược của nó thông qua một cách tiếp cận lặp. Hàm này có thể được gọi là bất kỳ số lần nào với các chuỗi khác nhau mỗi lần. & NBSP;

 def Reverse_iter(s):
   rev = ''
   for k in s:
     rev = k + rev
   return rev

 Reverse_iter('Welcome!') 

Output:

Nhiệm vụ tương tự được thực hiện thông qua một cách tiếp cận đệ quy như sau.

 def Reverse_rec(s):
   if not s:
     return ''
   else:
     return Reverse_rec(s[1:]) + s[0]

 Reverse_rec('Welcome!') 

Output: 

Xây dựng một tam giác với các con số

Xây dựng một hình tam giác các số bằng cách in 1 trên dòng đầu tiên, 1 nghìn trên dòng thứ hai, 1 triệu trên dòng thứ ba, v.v., cho đến khi một số dòng được quy định. Sau khi xây dựng đường dài, giảm số lượng các chữ số theo thứ tự giảm dần. Tổng số dòng được in sẽ bằng 2n+1, trong đó n là số đầu vào.

 # Iterative form
 n = 8
 # rise up
 for i in range(n):
   print(10**(3*i))
 # fall down
 for i in range(n, -1, -1):
   print(10**(3*i)) 

Output:

Trong cấu trúc ở trên, vòng lặp đầu tiên in chuỗi tăng dần và vòng thứ hai đã in chuỗi giảm dần. Điều tương tự có thể được thực hiện với một chức năng đệ quy như sau.

 # recursive form
 def Triangle(n, i=0):
   if n==0:
     print(1)
     return None
   print(10**(3*i))
   if i<n:
     # raise up
     Triangle(n, i+1)
   else:
     # fall down
     Triangle(n-1, i-1)

 Triangle(8) 

Output: 

Mặc dù các kết quả tương tự thu được thông qua cả hai phương pháp lặp và đệ quy, cách tiếp cận đệ quy có một con đường khó khăn trong khi phương pháp lặp đi theo một con đường đơn giản. Đây là loại vấn đề trong đó phương pháp đệ quy rất nản lòng. Tuy nhiên, việc hiểu đệ quy với loại vấn đề đơn giản này có thể giúp người ta hiểu các thuật toán nâng cao phụ thuộc rất nhiều vào các đệ quy, chẳng hạn như quay lại và lập trình động.

Sắp xếp nhanh chóng

Quicksort là một thuật toán nổi tiếng sắp xếp danh sách hoặc mảng đã cho tại chỗ. Trên thực tế, phương thức Python sắp xếp () theo thuật toán này để sắp xếp. Sắp xếp hợp nhất, và sắp xếp chèn là các thuật toán phân loại nổi tiếng khác. QuickSort sử dụng cả phương pháp đệ quy và lặp để thực hiện hoạt động sắp xếp một cách nhanh chóng và hiệu quả. & NBSP;

QuickSort ban đầu chọn phần tử đầu tiên của mảng làm phần tử trục của nó. Nó so sánh phần tử trục với các phần tử liên tiếp lặp đi lặp lại và thực hiện một sự thay đổi nếu phần tử bên phải cao hơn phần bên trái. Do đó, ở cuối lần lặp, phần tử trục có các phần tử nhỏ hơn ở các phần tử bên trái và lớn hơn ở bên phải. Tuy nhiên, cả hai phần tử bên trái và các yếu tố bên phải vẫn chưa được phân loại. Mảng hiện được chia thành hai phần dựa trên phần tử trục. Mảng trái và mảng phải được sắp xếp đệ quy bằng cách sử dụng hàm QuickSort ().

 def Quicksort(a, l, r):
   # consider the left most as pivot element
   current = l+1
   # base case (as limiting criteria)
   if r <= current:
     return None
   for i in range(l+1, r):
     # compare pivot element and shift current's postion
     if a[l] >= a[i]:
       a[i], a[current] = a[current], a[i]
       current += 1
   # exchange pivot element and current-but-one element
   a[l], a[current-1] = a[current-1], a[l]
   # perform Quicksort before current element
   Quicksort(a, l, current-1)
   # perform Quicksort after current element
   Quicksort(a, current, r) 
   return None 

Kiểm tra cách nó hoạt động.

 for flower in flowers:
   print(flower) 

Output:

Không có đệ quy, việc thực hiện Quicksort này sẽ là một công việc tốn nhiều công sức.

Máy tính xách tay Google Colab với việc triển khai mã trên.

Gói lên

Trong bài viết này, chúng tôi đã thảo luận về các phương pháp lặp và đệ quy của lập trình Python với một vài ví dụ. Chúng tôi đã thảo luận về các ràng buộc và hạn chế của cả hai phương pháp. Cuối cùng, chúng tôi đã thảo luận về thuật toán Quicksort nổi tiếng kết hợp cả hai mô hình lặp và đệ quy để thực hiện phân loại mảng. Người đọc quan tâm có thể tham khảo các thuật toán sắp xếp khác, heap, tìm kiếm nhị phân, lập trình động và thuật toán quay lại để tìm hiểu làm thế nào các đệ quy và lần lặp được chọn một cách hiệu quả cho một nhiệm vụ cụ thể.

Tài liệu tham khảo và đọc thêm

• Đọc thêm về đệ quy
• Đọc thêm về phép lặp
• Đọc thêm về Thuật toán Quicksort
• 7 thuật toán có thể giúp đỡ trong cuộc phỏng vấn khoa học dữ liệu của bạn

Có gì lặp lại trong Python?

Viêm lặp lại vs đệ quy là gì?

Python đệ quy là gì?

Đó là đệ quy tốt hơn hoặc lặp lại trong Python?