試圖理解遞歸函數

Question

爲了更好地理解遞歸，我試圖計算每對（），（ ）之間有多少個字符，而不包括其他（）中的字符。例如：

(abc(ab(abc)cd)(()ab)) 

將輸出：

Level 3: 3 
Level 2: 4 
Level 3: 0 
Level 2: 2 
Level 1: 3 

這裏的 「級別」 是指（）嵌套的水平。因此，三級意味着角色在一對（3）內的一對（2）內的一對（1）內。

要做到這一點，我的猜測是最簡單的做法是實現對函數的某種遞歸調用，如函數「recursiveParaCheck」中的註釋。我開始考慮重現關係時，我的方法是什麼？

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <ctype.h> 

int recursiveParaCheck(char input[], int startPos, int level); 

void main() 
{ 
    char input[] = ""; 

    char notDone = 'Y'; 
    do 
    { 
     //Read in input 
     printf("Please enter input: "); 
     scanf(" %s", input); 

     //Call Recursive Function to print out desired information 
     recursiveParaCheck(input, 1, 1); 

     printf("\n Would you like to try again? Y/N: "); 
     scanf(" %c", &notDone); 
     notDone = toupper(notDone); 
    }while(notDone == 'Y'); 

} 

int recursiveParaCheck(char input[], int startPos, int level) 
{ 
    int pos = startPos; 
    int total = 0; 
    do 
    { 
     if(input[pos] != '(' && input[pos] != ')') 
     { 
      ++total; 
     } 

     //What is the base case? 
     if(BASE CASE) 
     { 
      //Do something? 
     } 

     //When do I need to make a recursive call? 
     if(SITUATION WHERE I MAKE RECURSIVE CALL) 
     { 
      //Do something? 
     } 



     ++pos; 
    }while(pos < 1000000); // assuming my input will not be this long 
} 

Answer 1

遞歸是一個奇妙的編程工具。它提供了一種處理各種問題的簡單而強大的方法。然而，看到如何遞歸地處理問題通常很困難;它可能很難「遞歸地思考」。編寫遞歸程序也很容易，要麼運行時間太長，要麼根本不能正確終止。在本文中，我們將回顧遞歸的基礎知識，並希望幫助您開發或提煉非常重要的編程技巧。

什麼是遞歸？ 爲了說明遞歸是什麼，我們首先必須回答「什麼是遞歸？」基本上，如果一個函數自己調用，它就是遞歸的。

你也許會想，這是不是非常令人興奮的，不過這個功能在設計遞歸算法演示了一些關鍵的考慮因素：

它可以處理一個簡單的「基本情況」，而無需使用遞歸。 在這個例子中，基本情況是「HelloWorld（0）」;如果函數被要求打印零時間，那麼它將返回而不產生任何更多的「HelloWorld」。 它避免了週期。 爲什麼使用遞歸？ 我們上面說明的問題很簡單，我們編寫的解決方案可行，但我們可能會更好地使用循環，而不是用遞歸來打擾。在遞歸趨於發光的地方，問題稍微複雜一些。遞歸可以應用於幾乎任何問題，但是某些情況下您會發現它特別有用。在本文的其餘部分中，我們將討論這些場景中的一些場景，並且一路上，我們將討論使用遞歸時要記住的一些核心思想。在算法討論中，當我們談論一個圖時，我們通常不會討論顯示變量之間關係的圖表（如您的TopCoder評分圖，它顯示了關係在時間和你的評價之間）。相反，我們通常在討論以各種方式相互連接的事物，人員或概念的網絡。例如，路線圖可以被認爲是一張圖表，顯示了城市以及它們如何通過公路連接。圖形可能很龐大，複雜並且難以用編程方式處理。它們在算法理論和算法競賽中也很常見。幸運的是，使用遞歸可以使圖更簡單。圖的一種常見類型的層次結構，其中一個例子是一個企業的組織結構圖：

名經理 貝蒂薩姆 鮑勃·薩利 迪爾伯特彌敦道 約瑟夫·薩利彌敦道 維羅尼卡 薩利維羅尼卡 薩姆·約瑟夫 蘇珊·鮑伯 Veronica
在此圖中，對象是人，圖中的連接顯示誰向公司報告誰。圖表上方的上方線條表示圖表中較低的人向其上方的人員報告。在右側，我們看到這個結構如何在數據庫中表示。對於每位員工，我們都會記錄他們的姓名和經理姓名（如果需要，我們可以根據這些信息重建整個層次結構 - 您是否看到了？）。

現在假設我們給了編寫一個看起來像「countEmployeesUnder（employeeName）」的函數的任務。此功能旨在告訴我們有多少員工（直接或間接）向由employeeName命名的人員報告。例如，假設我們調用「countEmployeesUnder（'Sally'）」來找出有多少員工向Sally報告。

從一開始就足夠簡單，可以指望有多少人直接在她身下工作。要做到這一點，我們循環遍歷每個數據庫記錄，併爲每個經理是莎莉的員工增加一個計數器變量。實現這個方法，我們的函數會返回一個2：Bob和Joseph。這是一個開始，但我們也想要計算像Susan或Betty這樣的人，他們在層次結構中較低，但是間接地向Sally報告。這很尷尬，因爲在查看Susan的個人記錄時，例如，現在還不清楚Sally是如何參與的。

正如你可能猜到的，一個好的解決方案是使用遞歸。例如，當我們在數據庫中遇到Bob的記錄時，我們不只是將計數器加1。相反，我們增加一個（來計算Bob），然後增加一個報告給Bob的人數。我們如何查明有多少人向Bob報告？我們使用對我們正在編寫的函數的遞歸調用：「countEmployeesUnder（'Bob'）」。下面是這種方法的僞代碼：

function countEmployeesUnder(employeeName) 
{ 
    declare variable counter 
    counter = 0 
    for each person in employeeDatabase 
    { 
     if(person.manager == employeeName) 
     { 
      counter = counter + 1 
      counter = counter + countEmployeesUnder(person.name) 
     } 
    } 
    return counter 
} 

如果這不是非常清楚，最好的辦法是嘗試通過行由行精神上幾次跟隨它。請記住，每次進行遞歸調用時，都會得到所有本地變量的新副本。這意味着每個電話會有一個單獨的計數器副本。如果情況並非如此，當我們在函數的開始處設置爲零時，我們真的會搞砸了。作爲一個練習，考慮如何改變函數來增加一個全局變量。提示：如果我們增加了一個全局變量，我們的函數不需要返回一個值。

使命聲明 編寫遞歸算法時需要考慮的一個非常重要的事情是對函數的「任務聲明」有一個清晰的概念。例如，在這種情況下，我認爲一個人不應該被視爲向他或她自己報告。這意味着「countEmployeesUnder（'Betty'）」將返回零。因此，我們職能的使命陳述可能是「返回直接或間接向employeeName中指定的人報告的人數 - 不包括名爲employeeName的人員。」

讓我們考慮一下爲了讓它成爲一個人而被視爲向他或她自己報告的必要條件。首先，我們需要做到這一點，以便如果沒有人向某人報告，我們會返回一個而不是零。這很簡單 - 我們只是在函數的開始處將「counter = 0」行更改爲「counter = 1」。這是有道理的，因爲我們的函數必須返回比以前更高的值1。對「countEmployeesUnder（'Betty'）」的調用現在將返回1。

但是，我們必須在這裏非常小心。我們已經改變了我們的函數的使命陳述，當使用遞歸時，這意味着仔細看看我們如何遞歸地使用調用。例如，「countEmployeesUnder（'Sam'）」現在會給出一個不正確的答案3.要明白爲什麼，請按照代碼進行操作：首先，我們將Sam設置爲1，將counter設置爲1.然後，當我們遇到Betty時，我們我們將她計爲1.然後我們會計算向貝蒂報告的員工 - 現在也會返回1。

很明顯，我們對Betty進行了雙重計數;我們的功能「使命陳述」不再符合我們使用它的方式。我們需要擺脫「counter = counter + 1」這一行，認識到遞歸調用現在將貝蒂算作「向Betty報告的人」（因此我們不需要在遞歸調用之前對她進行計數）。

隨着我們的功能越來越複雜，模糊的「使命陳述」問題變得越來越明顯。爲了使遞歸工作，我們必須清楚地說明每個函數調用在做什麼，否則我們最終會遇到一些非常難以調試的錯誤。即使時間緊迫，通常撰寫評論詳細說明該功能應該做什麼也是值得開始的。有一個清晰的「使命宣言」意味着我們可以確信我們的遞歸調用將按照我們的預期行事，並且整個畫面會正確地結合在一起。