如何將迭代函數轉換爲遞歸函數？

Question

我有一些迭代方法，添加，刪除，按索引搜索，並計算我的鏈表上的具體名稱，但我想實現它們使用遞歸解決方案。

我不確定如何開始。爲了進行轉換，我是否應該遵循任何準則？

這裏是我的代碼：

在LinkedList的方法來計算具體的名稱

public int CountName(string name) 
{ 
    int count = 0; 

    for (Node current = firstNode; current != null; current = current.Next) 
    { 
     count++; 
     if (current.patient.Name == name) return count; 
    } 

    return 0; 
} 

GET節點方法

public Node GetNode(string name) 
{ 
    for (Node current = firstNode; current != null; current = current.Next) 
    { 
     if (current.patient.Name == name) 
     { 
      return current; 
     } 
    } 

    return null; 
} 

刪除方法

public void Delete(string name) 
{ 
    Node last = lastNode; 

    if (last.patient.Name == name) 
    { 
     firstNode = firstNode.Next; 
    } 
    else if (lastNode.patient.Name == name) 
    { 
     Node temp = firstNode; 

     while (temp.Next != lastNode) 
     { 
      temp = temp.Next; 
     } 

     lastNode = temp; 
     temp.Next = null; 
    } 
    else 
    { 
     for (Node current = firstNode; current != null; current = current.Next) 
     { 
      if (current.patient.Name == name) 
      { 
       last.Next = current.Next; 
      } 
      else 
      { 
       last = current; 
      } 
     } 

     size--; 
    } 
} 

打印所有什麼在我的鏈表法

public List<string> PrintAll() 
{ 
    List<String> temp = new List<string>(); 

    if (firstNode == null) 
    { 
     temp.Add("There are no items in the linked list"); 
     return temp; 
    } 
    else 
    { 
     Node helpNode = firstNode; 

     while (helpNode != null) 
     { 
      temp.Add(helpNode.GetPatient().Name); 
      helpNode = helpNode.getNext(); 
     } 

     return temp; 
    } 
} 

Answer 1

拇指的基本規則是，你將所有的迭代函數維持某種類型的國家（像那些控制環路）爲函數的參數變量。此外，你需要有一個「特殊情況」狀態，只返回一個值而不進行遞歸調用，否則你最終會陷入無限循環。

我們以CountName方法爲例。首先，讓我們重新編寫它，以便它返回具有指定名稱的所有節點的計數（當前它返回節點的數量，直到包括用指定名稱找到的第一個節點）：

原始（迭代）：

public int CountName(string name) 
{ 
    int count = 0; 

    for (Node current = firstNode; current != null; current = current.Next) 
    {     
     if (current.patient.Name == name) count++; 
    } 

    return count; 
} 

這裏的狀態變量是current節點變量，也就是循環狀態，這將是遞歸調用

基礎

對我們的特殊情況是停止環處理的條件：當current == null，在這種情況下我們返回0;

如果patient.name屬性匹配，我們爲該值添加一個值並處理下一個節點。

如果patient.name屬性不匹配，我們只處理下一個節點。

這告訴我們的是，我們需要能夠傳遞一個Node我們的方法爲好，我們將默認爲firstNode（這是在我們的循環條件初始值），以及遞歸設置爲current.Next （這是循環條件的最後部分）。

鑑於這些情況，這裏是一個遞歸解決方案：

public int CountName(string name, Node startFrom = firstNode) 
{ 
    // If this node is null, we just return 0 without any more recursive calls 
    if (startFrom == null) return 0; 

    // If the name matches, we make a recursive call from the next node, 
    // add one to the value, and return it 
    if (startFrom.patient.Name == name) 
    { 
     return CountName(name, startFrom.Next) + 1; 
    } 

    // Otherwise we just make the recursive call from the next node 
    return CountName(name, startFrom.Next); 
} 

希望給你足夠完成你的方法的其餘部分。