Chức năng đệ quy hoạt động bên trong 'vòng lặp for' như thế nào

Question

Tôi khá mới trong 'hàm đệ quy'. Vì vậy, tôi đang cố gắng để quấn đầu của tôi xung quanh lý do tại sao chúng tôi sử dụng chức năng đệ quy và làm thế nào đệ quy chức năng làm việc và tôi nghĩ rằng tôi đã có một sự hiểu biết khá tốt về nó.

Hai ngày trước, tôi đã cố gắng giải quyết vấn đề đường đi ngắn nhất. Tôi đã một đồ thị sau (đó là trong python):

graph = {'a': ['b', 'c'], 
      'b': ['c', 'd'], 
      'c': ['d'], 
      'd': ['c'], 
      'e': ['f'], 
      'f': ['c']} 

Tôi chỉ cố gắng để tìm một con đường, không phải là path.So ngắn nhất, đây là mã:

def find_path(graph,start,end,path=[]): 
    path = path + [start] 
    #Just a Test 
    print(path) 

    if start == end: 
     return path 

    if start not in graph: 
     return None 

    for node in graph[start]: 
     if node not in path: 
      new_path = find_path(graph,node,end,path) 
     if new_path: 
      #Just a test 
      print(path) 
      return new_path 

print(find_path({'a':['b','c'],'b':['c','d'],'c':['d'],'d':['c'],'e': 
['f'],'f':['c']},'a','d')) 

tôi khởi đầu đỉnh là 'a' và đỉnh kết thúc là 'd'.

Trong dòng thứ tư, tôi chỉ in 'đường dẫn' để xem con đường đi đến đâu.

Trên dòng 17, tôi cũng in 'đường dẫn', một lần nữa chỉ để kiểm tra. Và đây là kết quả:

['a'] 
['a', 'b'] 
['a', 'b', 'c'] 
['a', 'b', 'c', 'd'] 
['a', 'b', 'c'] 
['a', 'b'] 
['a'] 
['a', 'b', 'c', 'd'] 

Bốn dòng đầu tiên của kết quả là kết quả của 'in (đường dẫn)' trên dòng 4 của mã. Tuy nhiên, dòng thứ 5, thứ 6 và thứ 7 là kết quả của 'in (đường dẫn)' trên dòng 17 của mã.

Câu hỏi của tôi là tại sao danh sách đường dẫn giảm một đỉnh mỗi lần?

Tôi đã cố gắng tìm giải pháp đó trong 2 ngày. Tôi đã đi đến diễn đàn, đọc tài liệu về đệ quy và xem video. Nhưng, không may mắn.

Tôi sẽ rất tuyệt nếu ai đó có thể trả lời.

Answer 1

Trước tiên, tôi sẽ giải thích về ý nghĩa của backtracking. Tôi cũng đã đăng câu trả lời này here.

Đệ quy nghĩa là gọi hàm từ bên trong cùng chức năng đó. Bây giờ điều xảy ra là khi hàm gặp một cuộc gọi đến chính nó ..hãy tưởng tượng rằng một trang mới mở ra và điều khiển được chuyển từ trang cũ sang trang mới này đến khi bắt đầu chức năng, khi chức năng gặp lại cuộc gọi trong trang mới này, một trang khác mở ra bên cạnh nó và theo cách này trang mới tiếp tục xuất hiện bên cạnh trang cũ. Lưu ý rằng tất cả các biến cục bộ chỉ nằm trong phạm vi với các trang tương ứng của chúng. Đó là nếu bạn muốn truy cập vào giá trị trong trang trước, bạn có thể chuyển nó tới hàm trong các tham số hoặc tạo biến toàn cầu.

Cách duy nhất để quay trở lại là sử dụng câu lệnh trả về. Khi hàm gặp nó, điều khiển sẽ chuyển từ trang mới trở lại trang cũ trên cùng một dòng từ nơi nó được gọi và bắt đầu thực hiện bất kỳ điều gì bên dưới dòng đó. Đây là nơi bắt đầu quay lại. Để tránh các vấn đề như nạp dữ liệu một lần nữa khi nó được lấp đầy, bạn thường cần phải đặt một câu lệnh trả về sau mỗi lần gọi hàm.

Bây giờ trong mã của bạn,

def find_path(graph,start,end,path=[]): 
    path = path + [start] 
    #Just a Test 
    print(path) 

    if start == end: 
     return path 

    if start not in graph: 
     return None 

    for node in graph[start]: 
     if node not in path: 
      new_path = find_path(graph,node,end,path) <---- when function returns it will start executing from here again. 
     if new_path: 
      #Just a test 
      print(path) 
      return new_path 

Và lưu ý rằng biến path của bạn không phải là một biến toàn cầu. Đó là một địa phương. Điều này có nghĩa là mọi lúc bạn gọi lại nó. Để tránh điều này bạn đang đi qua giá trị đường dẫn một lần nữa trong các tham số chức năng (trong lần cuối).

Vì vậy, cuối cùng khi hàm trả về sau khi nó đã tìm thấy d nó trở về trạng thái trước đó mà biến đường dẫn chỉ có a, b, c trong đó. đó là những gì bạn in ra.

Chỉnh sửa: - Trong trường hợp bất kỳ đối tượng nào, lời giải thích của tôi về đệ quy sử dụng các trang hoàn toàn không phải là technichal, nếu bạn muốn biết nó thực sự xảy ra như thế nào, bạn sẽ phải đọc về hồ sơ kích hoạt và cách nó đẩy tất cả nhà nước lên một chồng

Answer 2

Điều này là do đệ quy mang lại kết quả từ các cuộc gọi "trong cùng" đến "ngoài cùng". Đó là dòng đầu tiên câu lệnh 17 print xảy ra từ mức đệ quy sâu nhất nơi đường dẫn có nhiều nút nhất. Sau khi mức đó trở lại cấp độ tiếp theo "trở lên" được in (một nút ít hơn trong đường dẫn). Lưu ý rằng chức năng print của bạn là sau cuộc gọi đệ quy đến find_path.

Bạn có thể hình dung nó như sau:

find_path(..., path=['a']) # Recursion level 1. 
| 
| find_path(..., path=['a', 'b']) # Recursion level 2. 
| | 
| | find_path(..., path=['a', 'b', 'c']) # Recursion level 3. 
| | print(path) # Prints ['a', 'b', 'c']. 
| | return # Return from level 3. 
| | 
| print(path) # Prints ['a', 'b']. 
| return # Return from level 2. 
| 
print(path) # Prints ['a']. 
return # Return from level 1. 

Nếu bạn muốn duy nhất (phụ) đường dẫn được in trong "tăng" để sau đó bạn có thể dễ dàng đặt print chức năng trước cuộc gọi đệ quy đến find_path.

Biến số new_path giữ đường dẫn được tìm thấy đệ quy trong khi path chỉ giữ đường dẫn đến nút hiện tại.

Bằng cách này, điều khoản if new_path: có thể không thành công nếu trước đó chi nhánh if chưa được nhập vì sau đó new_path không được xác định.

Answer 3

1) phương pháp find_path là lần đầu tiên được gọi với a như nút khởi đầu thiết lập path như ['a'] và gọi phương thức find_path với b như nút khởi động trước khi in đường dẫn trên dòng 17.

2) Cuộc gọi đến phương thức find_path với b làm nút bắt đầu se ts con đường như ['a','b'] và gọi phương thức find_path với c như nút khởi động trước khi in đường dẫn trên dòng 17.

3) Các cuộc gọi đến find_path phương pháp với c là nút bắt đầu sẽ đặt đường dẫn như ['a','b','c'] và gọi phương thức find_path với d như nút khởi động trước khi in đường dẫn trên dòng 17.

4) các cuộc gọi đến find_path phương pháp với d là nút bắt đầu sẽ đặt đường dẫn như ['a','b','c','d'] in nó trên dòng 4 và lợi nhuận.

5) Bây giờ nó sẽ trả về trên dòng 14 trong việc thực hiện phương pháp find_path với c như nút start (vốn đã thiết lập đường dẫn như ['a','b','c'] như đã đề cập tại điểm 3) và in đường dẫn trên dòng 17 (đó là dòng thứ 5 kết quả của bạn) và trả về.

6) này trả về trên dòng 14 trong việc thực hiện phương pháp find_path với b như nút start (vốn đã thiết lập đường dẫn như ['a','b'] như đã đề cập tại điểm 2) và in đường dẫn trên dòng 17 (đó là dòng thứ 6 của bạn kết quả) và trả về.

7) này trả về trên dòng 14 trong việc thực hiện phương pháp find_path với a như nút start (vốn đã thiết lập đường dẫn như ['a'] như đã đề cập tại điểm 1) và in đường dẫn trên dòng 17 (đó là dòng thứ 6 của bạn kết quả) và trả về.

Bạn có thể tưởng tượng nó như là LIFO (Last In First Out)