在Java中遞歸迭代

-4

我試圖將此遞歸方法轉換爲迭代方法。但我陷入了中間。在Java中遞歸迭代

static void string_recurse(String active,String rest) { 
    if (rest.length() == 0) { 
    System.out.println(active); 
    } else { 
    string_recurse(active + rest.charAt(0), rest.substring(1, rest.length())); 
    string_recurse(active, rest.substring(1, rest.length())); 
    } 
}

我不明白如何將此遞歸方法轉換爲迭代方法。這種方法所做的是打印給定單詞的所有「子集」單詞。更正式地說，如果我們有串s_1s_2...s_n它枚舉所有字符串s_{i1}s_{i2}...s_{ik}這樣i1, i2, ..., ik是{1, ..., n}一個子集，i1 < i2 < ... < ik

例如，當我們調用string_recurse("","abc");我們得到的輸出：

abc 
ab 
ac 
a 
bc 
b 
c 
(the empty word)

來源

2013-10-26 Marlio

你能說出這個方法做什麼嗎？ –

你究竟在哪裏卡住？令人驚訝的是，我甚至沒有在這裏看到一個循環。 – SudoRahul

什麼是活動和休息字符串？你能舉一些例子嗎？ –

class Main { 

    static void string_recurse(String active,String rest) { 
     if (rest.length() == 0) { 
      System.out.println(active); 
     } else { 
      string_recurse(active + rest.charAt(0), rest.substring(1, rest.length())); 
      string_recurse(active, rest.substring(1, rest.length())); 
     } 
    } 

    static void string_iterative(String s) { 
     int n = s.length(); 
     for (int mask = (1 << n) - 1; mask >= 0; mask--) { 
      String temp = ""; 
      for (int pos = 0; pos < n; pos++) 
       if (((1 << (n - 1 - pos)) & mask) != 0) 
        temp += s.charAt(pos); 
      System.out.println(temp);    
     } 
    } 

    public static void main(String[] args) { 
     String s = "abcd"; 
     string_recurse("", s); 
     string_iterative(s); 
    } 
}

注意：如果你知道你的字符串的長度永遠不會超過32使用這種迭代方法。如果您知道該字符串的長度超過32但受限於64，則將mask定義爲long。如果長度可以大於64則堅持原始的遞歸方法。

這種迭代方法的想法是將字符串的每個字符映射到1或0。 1表示相應的字符參與當前的子字，0意味着相反的字符。因此，要循環所有「子集詞」，我們只需要從00..0 (n bits)循環到11..1(n bits)。這可以通過遍歷整數範圍[0，2^n - 1]並使用數字的二進制表示來完成。請注意，在給定的例子中，這些數字以反向方式循環，以使迭代函數與遞歸函數保持一致。

來源

2013-10-26 16:53:52 svs

在Java中遞歸迭代

回答

相關問題