Recursive to Iterative in Java [closed]

Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

Questions asking for code must demonstrate a minimal understanding of the problem being solved. Include attempted solutions, why they didn't work, and the expected results. See also: Stack Overflow question checklist

Closed 8 years ago.

Improve this question

I'm trying to convert this recursive method to an iterative method. But I am stuck in the middle.

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()));
  }
}

I can't understand how to convert this recursive method to an iterative one. What this method does is it prints all "subset" words of a given word. More formally, if we have the string s_1s_2...s_n it enumerates all strings s_{i1}s_{i2}...s_{ik} such that i1, i2, ..., ik is a subset of {1, ..., n} and i1 < i2 < ... < ik

For example when we call string_recurse("","abc"); we get the output:

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

Answer 1

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);
    }
}

Note: If you know that your string's length never goes over 32 use this iterative method. If you know that the string's length goes over 32 but is bounded by 64 define mask as long. If the length can be more than 64 stick with the original recursive method.

The idea of this iterative method is to map every character of the string to either 1 or 0. 1 means that the corresponding character takes part in the current sub-word and 0 means the opposite. So to loop over all "subset words" we just need to loop from 00..0 (n bits) to 11..1(n bits). This can be done just by looping over the integer range [0, 2^n - 1] and by using the binary representation of the numbers. Note that in the given example those numbers are looped over in reverse fashion in order for the iterative function to be consistent with the recursive one.