手動計數遞歸調用

Question

新的CS學生，正在爲最後的學習而學習。我試圖找出一般會調用遞歸方法的次數。作爲例子添加了代碼。如果我輸入abcd和efgh，根據字符串的大小調用多少個電話？如果n是任何數據大小，則任何遞歸方法中的調用次數都是n（？）。

public static String interweave(String s1, String s2) 
{ 
    if (s1.equals("")) return s2; 
    else if (s2.equals("")) return s1; 
    else return "" + interweave(s1.substring(0,s1.length()-1), s2.substring(0,s2.length()-1)) 
     +s1.charAt(s1.length()-1)+s2.charAt(s2.length()-1); 
} 

Answer 1

注意，在你的問題，在每個遞歸步驟，你通過這兩個字符串中的一個尺寸減小，直到其中一方具有零長度（的基本情況遞歸）。很容易看出，遞歸調用的數量爲min(m, n) + 1，其中m爲s1的起始長度，而n的起始長度爲s2。

例如，如果s1 = "abc"和s2 = "de"將花費2遞歸調用遍歷s2（具有最小長度的字符串）加上一個額外呼叫在基礎案例離開，因此min(s1.length(), s2.length()) + 1 == 3。您可以通過編程測試它是這樣的：

static int counter; 

public static String interweave(String s1, String s2) { 
    counter++; 
    if (s1.equals("")) 
     return s2; 
    else if (s2.equals("")) 
     return s1; 
    else 
     return interweave(s1.substring(0, s1.length()-1), s2.substring(0, s2.length()-1)) 
     + s1.charAt(s1.length()-1)+s2.charAt(s2.length()-1); 
} 

public static int count(String s1, String s2) { 
    counter = 0; 
    interweave(s1, s2); 
    return counter; 
} 

現在，當您運行下面的語句，公式按預期工作：

// s1.length() == s2.length() 
System.out.println(count("abcde", "fghij")); 
> 6 

// s1.length() > s2.length() 
System.out.println(count("abcde", "fg")); 
> 3 

// s1.length() < s2.length() 
System.out.println(count("ab", "cdefg")); 
> 3 

Answer 2

字符不代表任何東西只是長度。可以按如下方式將此轉換爲數字的問題：

public static String interweave(int s1, int s2) 
{ 
    if (s1 == 0) return s2; 
    else if (s2 == 0) return s1; 
    else return interweave(s1-1, s2-1)+2; 
}