Chức năng không đệ quy trong python là gì?

Tái diễn hay không tái diễn, đó là câu hỏi. Tất cả chúng ta đều biết về niềm vui mà chúng ta có với các hàm đệ quy. Nhưng nó cũng có những nhược điểm riêng, một trong số đó sẽ được giải thích trong bài viết này để giúp bạn lựa chọn sáng suốt

Giả sử, chúng ta cần tạo một hàm mà khi được gọi cần in dữ liệu trong danh sách liên kết

Điều này có thể được thực hiện theo 2 cách

• 1. Với đệ quy
• 2. không có đệ quy

1. Với đệ quy

```
def print_linkedlist[head]:

   if head is not None:
       print[head.data]
       print_linkedlist[head.next]
```

Cách tiếp cận đầu tiên cũng hoạt động nhưng nếu danh sách thực sự dài khoảng 1000 phần tử thì chương trình sẽ đạt độ sâu đệ quy và lỗi. Đừng quên rằng khi độ dài danh sách tăng lên, kích thước ngăn xếp cũng tăng tuyến tính

Độ sâu đệ quy là gì?

Trước khi chúng tôi tiếp tục, bạn nên biết rằng vấn đề này là của riêng Python. Có những ngôn ngữ mà chúng tôi không gặp phải vấn đề này nhưng điều đó sẽ không được thảo luận ở đây. Chúng ta biết rằng một hàm đệ quy gọi chính nó. Điều này có nghĩa là một chức năng mới được gọi trong chức năng ban đầu. Giả sử một danh sách được liên kết đếm từ 0 đến n x 1 bằng cách sử dụng mã đệ quy được đề cập ở trên

Hàm đầu tiên xem dữ liệu của nút đầu trong danh sách và sau đó in dữ liệu đó. Nhưng chức năng đầu tiên vẫn chưa kết thúc. Một chức năng cũ không thể kết thúc cho đến khi tất cả các chức năng bên trong nó kết thúc. Nếu chúng ta quan sát ngăn xếp cuộc gọi có danh sách các chức năng hiện đang chạy.  

# the first function waiting for
# innermost functions to end
print_linkedlist[]

       # the child function called 
       # within the first function
           print_linkedlist[]

Ngăn xếp cuộc gọi tiếp tục tăng vì các chức năng cũ hơn không bao giờ kết thúc vì chúng đang đợi các chức năng con bên trong kết thúc. Cuối cùng, ngăn xếp cuộc gọi trông giống như

# original Function
print_linkedlist[]

  # first level function
  print_linkedlist[]
  
    # second level function
    print_linkedlist[]
    
      # third level function
      print_linkedlist[]
        ……
          ……
            ……
            
              # 1000 level function – Maximum 
              # Recursion Depth Reached
              print_linkedlist[]

Và BÙMMM. ĐỘ SÂU HỒI QUY TỐI ĐA

Độ sâu đệ quy đếm số lớp hoạt động bên trong hàm đệ quy. Trong Python, giới hạn độ sâu đệ quy tối đa mặc định là 1000. Giới hạn giúp ngăn tràn ngăn xếp gây ra bởi đệ quy vô hạn

Do đó, cách tiếp cận thứ hai như bên dưới sẽ tốt hơn vì kích thước ngăn xếp không đổi

2. Không có đệ quy/lặp lại

```
def print_linkedlist[node]:
   while node:
       print[node.data]
       node=node.next
```

Sự kết luận

Sử dụng đệ quy rất thú vị nhưng bạn nên hiểu khi nào nên và khi nào không sử dụng nó. Một số ngôn ngữ như Scala và Haskell hỗ trợ một tính năng thú vị có tên là TAIL CALL RECURSION để ngăn vấn đề về độ sâu đệ quy bằng cách kết thúc lệnh gọi của hàm trước đó khi một lệnh gọi mới được thực hiện. Nhưng Python không hỗ trợ tính năng này. Vì vậy, ít nhất là trong Python, hãy ưu tiên cách tiếp cận lặp lại nếu bạn cho rằng hàm có thể đạt đến giới hạn đệ quy

Đối với sinh viên nâng cao hơn, hãy thảo luận về chi phí hệ thống dưới dạng ngăn xếp cần thiết. Ngăn xếp cuộc gọi là cấu trúc dữ liệu được chương trình sử dụng để lưu trữ thông tin về các chương trình con đang hoạt động trong chương trình. Ngăn xếp được sử dụng để chương trình có thể theo dõi vị trí chương trình con sẽ trả lại quyền điều khiển sau khi chương trình kết thúc thực thi

def fib[n]:
    if n == 1:
        return [1]
    if n == 2:
        return [1, 1]
    fibs = [1, 1]
    for _ in range[2, n]:
        fibs.append[fibs[-1] + fibs[-2]]
    return fibs

print[fib[1]]  # [1]
print[fib[2]]  # [1, 1]
print[fib[3]]  # [1, 1, 2]
print[fib[10]] # [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
 
Tóm lại, mỗi lệnh gọi sẽ tính toán đệ quy hai giá trị cần thiết để có được kết quả cho đến khi điều khiển chạm vào trường hợp cơ sở, điều này xảy ra khi nright]];
}

Về cơ bản, hàm này trả về một nút giống với gốc của cây ban đầu bằng cách xây dựng đệ quy các cây con bên trái và bên phải cho đến khi chúng chạm vào các nút lá. Như chúng ta có thể thấy, thao tác này không thể thực hiện được bằng cách sử dụng hàm không đệ quy vì bạn không biết trước cây trông như thế nào. Trong loại tình huống này, chúng ta chỉ có thể dựa vào đệ quy

chức năng không đệ quy là gì?

Các hàm đệ quy và không đệ quy trong Python là gì?

Sự khác biệt giữa đệ quy và không đệ quy là gì?

Không đệ quy và lặp lại có giống nhau không?