1

新的 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);
}
4

2 回答 2

0

字符并不意味着任何东西只是长度。您可以将其转换为数字问题，如下所示：

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;
}
于 2012-04-28T02:06:57.317 回答
0

请注意，在您的问题中，在每个递归步骤中，您将两个字符串的大小减少一个，直到其中一个字符串的长度为零（递归的基本情况）。不难看出，递归调用的次数是min(m, n) + 1，其中m是 的初始长度，s1是n的初始长度s2。

例如， ifs1 = "abc"和s2 = "de"它将需要 2 次递归调用来遍历s2（具有最小长度的字符串）加上 1 次额外调用以退出基本情况，因此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
于 2012-04-28T13:12:45.667 回答