Hướng dẫn recursively iterate through list python - đệ quy lặp qua danh sách python

Nói rằng tôi có danh sách x = [1, 2, 3, 4]

Có một phương pháp đệ quy nơi tôi có thể đi qua danh sách để tìm giá trị?

Cuối cùng tôi muốn có thể so sánh một giá trị được trả về trong danh sách, (hoặc danh sách lồng nhau) với một số tùy ý để xem nó phù hợp.

Tôi có thể nghĩ một cách để làm điều này bằng cách sử dụng một vòng lặp, nhưng tôi gặp khó khăn trong việc tưởng tượng một phương pháp đệ quy để làm điều tương tự. Tôi biết rằng tôi không thể đặt một bộ đếm để theo dõi vị trí của mình trong danh sách vì gọi chức năng đệ quy sẽ đặt lại bộ đếm mỗi lần.

Tôi đã nghĩ rằng tôi có thể đặt trường hợp cơ sở của mình về hàm như là một so sánh giữa số và danh sách Len 1.

Tôi chỉ muốn một số gợi ý thực sự.

Đã hỏi ngày 4 tháng 2 năm 2014 lúc 20:59Feb 4, 2014 at 20:59

2

Đây không phải là cách để làm mọi thứ trong Python, nhưng chắc chắn - bạn có thể đi qua danh sách các danh sách đệ quy:

def findList(lst, ele):
    if not lst:         # base case: the list is empty
        return False
    elif lst[0] == ele: # check if current element is the one we're looking
        return True
    elif not isinstance(lst[0], list): # if current element is not a list
        return findList(lst[1:], ele)
    else:                              # if current element is a list
        return findList(lst[0], ele) or findList(lst[1:], ele)

Đã trả lời ngày 4 tháng 2 năm 2014 lúc 21:02Feb 4, 2014 at 21:02

Óscar Lópezóscar LópezÓscar López

229K35 Huy hiệu vàng307 Huy hiệu bạc380 Huy hiệu Đồng35 gold badges307 silver badges380 bronze badges

1

Các hàm đệ quy là thành ngữ khi bạn có một danh sách được liên kết. Danh sách Python giống như mảng hơn. Nhưng vẫn có thể xử lý một danh sách Python với chức năng đệ quy - không có tiện ích thực sự, nhưng nó có thể thú vị như một bài tập.

Bạn bắt đầu với một danh sách đầy đủ và trường hợp cơ sở của bạn là khi danh sách trống. Đi qua danh sách bằng cách chuyển danh sách trong một đối số, sử dụng

Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

0 để tìm nạp đồng thời và xóa mục đầu tiên trong danh sách, đánh giá mục popped, sau đó chuyển danh sách (giờ ngắn hơn) vào cùng một hàm.

Chỉnh sửa: Trên thực tế, trên suy nghĩ thứ hai, bạn sẽ tốt hơn khi không sử dụng x.pop () và thay vào đó là nhìn trộm ở giá trị thứ nhất và chuyển phần còn lại trong một lát cắt. Điều này sẽ không hiệu quả, bởi vì bạn đang sao chép danh sách mỗi khi bạn cắt lát, nhưng nó tốt hơn là tiêu thụ phá hủy danh sách bên trong chức năng đệ quy của bạn, trừ khi đó là tác dụng phụ mong muốn.

Đã trả lời ngày 4 tháng 2 năm 2014 lúc 21:03Feb 4, 2014 at 21:03

Andrew Gorcesterandrew GorcesterAndrew Gorcester

Huy hiệu vàng 19.2K755 Huy hiệu bạc71 Huy hiệu đồng7 gold badges55 silver badges71 bronze badges

Vâng, bạn sẽ có hai trường hợp cơ sở:

1) Bạn đã đạt đến cuối danh sách => Trả về Sai.

2) Phần tử hiện tại của bạn là phần tử bạn đang tìm kiếm => Trả về True (hoặc phần tử hoặc vị trí của nó, bất cứ điều gì bạn quan tâm).

Điều bạn phải làm tất cả thời gian là kiểm tra cả hai trường hợp cơ sở trên phần tử hiện tại và áp dụng chức năng đệ quy trên phần tử tiếp theo trong danh sách nếu không một trong các trường hợp cơ sở được áp dụng.

Đã trả lời ngày 4 tháng 2 năm 2014 lúc 21:05Feb 4, 2014 at 21:05

FedorsmirnovfedorsmirnovfedorSmirnov

6912 Huy hiệu vàng9 Huy hiệu bạc19 Huy hiệu đồng2 gold badges9 silver badges19 bronze badges

Ngăn xếp lỗi tràn trong hàm đệ quy

Một hàm đệ quy được gọi với đầu vào yêu cầu quá nhiều lần lặp sẽ khiến ngăn xếp cuộc gọi trở nên quá lớn, dẫn đến lỗi tràn ngăn xếp. Trong những trường hợp này, việc sử dụng một giải pháp lặp lại là thích hợp hơn. Một giải pháp đệ quy chỉ phù hợp cho một vấn đề không vượt quá một số lượng cuộc gọi đệ quy nhất định.

Ví dụ:

Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

1 bên dưới ném lỗi tràn ngăn xếp khi đầu vào 1000 được sử dụng.

def myfunction(n):
  if n == 0:
    return n
  else:
    return myfunction(n-1)
myfunction(1000)  

Trình tự Fibonacci

Trình tự Fibonacci là một chuỗi các số toán học sao cho mỗi số là tổng của hai số trước, bắt đầu từ 0 và 1.

Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

Gọi xây dựng ngăn xếp trong khi vòng lặp

Một ngăn xếp cuộc gọi với bối cảnh thực thi có thể được xây dựng bằng cách sử dụng vòng lặp

Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

2,

Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

3 để biểu thị ngăn xếp cuộc gọi và

Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

4 để biểu thị bối cảnh thực thi. Điều này rất hữu ích để bắt chước vai trò của một ngăn xếp cuộc gọi bên trong hàm đệ quy.

Cây tìm kiếm nhị phân

Trong Python, một cây tìm kiếm nhị phân là một cấu trúc dữ liệu đệ quy giúp các danh sách được sắp xếp dễ dàng hơn để tìm kiếm. Cây tìm kiếm nhị phân:

• Tham khảo hai đứa trẻ nhất trên mỗi nút cây.
• Con trái cây trái của cây phải chứa một giá trị thấp hơn cha mẹ của nó.
• Đứa trẻ bên phải của cây phải chứa một giá trị lớn hơn cha mẹ của nó.

     5
    / \
   /   \
  3     8
 / \   / \
2   4 7   9

Danh sách đệ quy và lồng nhau

Một danh sách lồng nhau có thể được đi qua và làm phẳng bằng hàm đệ quy. Trường hợp cơ sở đánh giá một yếu tố trong danh sách. Nếu nó không phải là một danh sách khác, phần tử duy nhất được thêm vào một danh sách phẳng. Bước đệ quy gọi hàm đệ quy với phần tử danh sách lồng nhau là đầu vào.

def flatten(mylist):
  flatlist = []
  for element in mylist:
    if type(element) == list:
      flatlist += flatten(element)
    else:
      flatlist += element
  return flatlist
print(flatten(['a', ['b', ['c', ['d']], 'e'], 'f']))

Đệ quy Fibonacci

Tính toán giá trị của số Fibonacci có thể được thực hiện bằng cách sử dụng đệ quy. Với đầu vào của Index N, hàm đệ quy có hai trường hợp cơ sở - khi chỉ mục bằng 0 hoặc 1. Hàm đệ quy trả về tổng của chỉ số trừ 1 và chỉ số trừ 2.

Thời gian chạy lớn của hàm Fibonacci là O (2^n).

def fibonacci(n):
  if n <= 1:
    return n
  else:
    return fibonacci(n-1) + fibonacci(n-2)

Mô hình đệ quy như ngăn xếp cuộc gọi

Người ta có thể mô hình hóa đệ quy dưới dạng

Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

5 với

Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

6 bằng cách sử dụng vòng lặp

Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

2 và Python

Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

3. Khi đạt được

Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

9, hãy in ra ngăn xếp cuộc gọi

Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

3 theo cách LIFO (cuối cùng theo cách đầu tiên) cho đến khi ngăn xếp cuộc gọi trống.

Sử dụng vòng lặp

Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

2 khác, lặp qua ngăn xếp cuộc gọi

Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

3. Bật mục cuối cùng ra khỏi danh sách và thêm nó vào một biến để lưu trữ kết quả tích lũy.

In kết quả.

def countdown(value):
  call_stack = []
  while value > 0 : 
    call_stack.append({"input":value})
    print("Call Stack:",call_stack)
    value -= 1
  print("Base Case Reached")
  while len(call_stack) != 0:
    print("Popping {} from call stack".format(call_stack.pop()))
    print("Call Stack:",call_stack)
countdown(4)
'''
Call Stack: [{'input': 4}]             
Call Stack: [{'input': 4}, {'input': 3}]         
Call Stack: [{'input': 4}, {'input': 3}, {'input': 2}]     
Call Stack: [{'input': 4}, {'input': 3}, {'input': 2}, {'input': 1}]                                
Base Case Reached                                  
Popping {'input': 1} from call stack                       
Call Stack: [{'input': 4}, {'input': 3}, {'input': 2}]  
Popping {'input': 2} from call stack                   
Call Stack: [{'input': 4}, {'input': 3}]       



Popping {'input': 3} from call stack 
Call Stack: [{'input': 4}] 
Popping {'input': 4} from call stack 
Call Stack: []
'''

Đệ quy trong Python

Trong Python, một hàm đệ quy chấp nhận một đối số và bao gồm một điều kiện để kiểm tra xem nó có khớp với trường hợp cơ sở hay không. Một hàm đệ quy có:

• Trường hợp cơ sở - Một điều kiện đánh giá đầu vào hiện tại để ngăn chặn đệ quy tiếp tục.
• Bước đệ quy - Một hoặc nhiều cuộc gọi đến hàm đệ quy để đưa đầu vào gần hơn với trường hợp cơ sở.

def countdown(value):
  if value <= 0:   
    print("done")
  else:
    print(value)
    countdown(value-1)  

Xây dựng một cây tìm kiếm nhị phân

Để xây dựng một cây tìm kiếm nhị phân như một thuật toán đệ quy, hãy làm như sau:

BASE CASE: 
If the list is empty, return "No Child" to show that there is no node. 

RECURSIVE STEP:
1. Find the middle index of the list.
2. Create a tree node with the value of the middle index.
3. Assign the tree node's left child to a recursive call with the left half of list as input.
4. Assign the tree node's right child to a recursive call with the right half of list as input.
5. Return the tree node.

def build_bst(my_list):
  if len(my_list) == 0:
    return "No Child"
  middle_index = len(my_list) // 2
  middle_value = my_list[middle_index]
  print("Middle index: {0}".format(middle_index))
  print("Middle value: {0}".format(middle_value))
  tree_node = {"data": middle_value}
  tree_node["left_child"] = build_bst(my_list[ : middle_index])
  tree_node["right_child"] = build_bst(my_list[middle_index + 1 : ])
  return tree_node
sorted_list = [12, 13, 14, 15, 16]
binary_search_tree = build_bst(sorted_list)
print(binary_search_tree)

Độ sâu đệ quy của cây tìm kiếm nhị phân

Cây tìm kiếm nhị phân là một cấu trúc dữ liệu xây dựng một danh sách đầu vào được sắp xếp thành hai cây con. Đứa trẻ bên trái của cây con chứa một giá trị nhỏ hơn gốc của cây. Đứa trẻ bên phải của cây con chứa một giá trị lớn hơn gốc của cây.

Một hàm đệ quy có thể được viết để xác định độ sâu của cây này.

def myfunction(n):
  if n == 0:
    return n
  else:
    return myfunction(n-1)
myfunction(1000)  

0

Tổng số với đệ quy

Tóm tắt các chữ số của một số có thể được thực hiện đệ quy. Ví dụ:

def myfunction(n):
  if n == 0:
    return n
  else:
    return myfunction(n-1)
myfunction(1000)  

1

def myfunction(n):
  if n == 0:
    return n
  else:
    return myfunction(n-1)
myfunction(1000)  

2

Palindrom trong đệ quy

Một palindrom là một từ có thể được đọc giống nhau cả hai cách - tiến và lùi. Ví dụ, ABBA là một palindrom và ABC thì không.

Giải pháp để xác định xem một từ có phải là một palindrom có ​​thể được thực hiện như một hàm đệ quy hay không.

def myfunction(n):
  if n == 0:



 return n
 else:
 return myfunction(n-1)
myfunction(1000) 

3

Chức năng lặp Fibonacci

Một chuỗi Fibonacci được tạo thành thêm hai số trước đó bắt đầu bằng 0 và 1. Ví dụ::

def myfunction(n):
  if n == 0:
    return n
  else:
    return myfunction(n-1)
myfunction(1000)  

4

Một hàm để tính toán giá trị của một chỉ mục trong chuỗi Fibonacci,

     5
    / \
   /   \
  3     8
 / \   / \
2   4 7   9

3 có thể được viết dưới dạng hàm lặp.

def myfunction(n):
  if n == 0:
    return n
  else:
    return myfunction(n-1)
myfunction(1000)  

5

Phép nhân đệ quy

Việc nhân hai số có thể được giải quyết đệ quy như sau:

def myfunction(n):
  if n == 0:
    return n
  else:
    return myfunction(n-1)
myfunction(1000)  

6

def myfunction(n):
  if n == 0:
    return n
  else:
    return myfunction(n-1)
myfunction(1000)  

7

Chức năng lặp cho giai thừa

Để tính toán giai thừa của một số, nhân tất cả các số tuần tự từ 1 với số.

Một ví dụ về một chức năng lặp để tính toán một giai thừa được đưa ra dưới đây.

def myfunction(n):
  if n == 0:
    return n
  else:
    return myfunction(n-1)
myfunction(1000)  

8

Tìm kiếm tối thiểu trong danh sách

Chúng ta có thể sử dụng đệ quy để tìm phần tử có giá trị tối thiểu trong danh sách, như được hiển thị trong mã bên dưới.

def myfunction(n):
  if n == 0:
    return n
  else:
    return myfunction(n-1)
myfunction(1000)  

9

Tìm hiểu thêm về Codecademy

Đệ quy có tốt hơn python lặp không?

Đệ quy có hiệu quả trong python không?

Đệ quy có tốt hơn các vòng không?

Đệ quy có giống như vòng lặp không?