Проблема в понимании рекурсии - Java - PullRequest
Новая
       0

Проблема в понимании рекурсии - Java

1 голос
/ 11 апреля 2011

Я получил код из этого вопроса, я запустил его в Eclipse, и код был в порядке, но я запутался в том, как внутренний порядок рекурсии проходит. 

public class Permute {
    public static void main(String[] args) throws IOException {
        System.out.println("Enter a string");
        BufferedReader bufReader = new BufferedReader(new InputStreamReader(
                System.in));
        String text = bufReader.readLine();
        shuffle("", text);
    }

    public static void shuffle(String dummy, String input) {
        if (input.length() <= 1)
            System.out.println(dummy + input);
        else {
            for (int i = 0; i < input.length(); i++) {
                input = input.substring(i, i + 1) + input.substring(0, i)
                        + input.substring(i + 1);
                shuffle(dummy + input.substring(0, 1), input.substring(1));

            }
        }
    }
}

Я обнаружил трудности в понимании рекурсии в цикле for в Shuffle. Какие-нибудь указатели в декодировании шагов рекурсии?

РЕДАКТИРОВАТЬ : Хорошо, это мое понимание, скажем, предположим, что мой ввод ABC, и когда я бегу в первом цикле, я получаю пустышку = A и вход = BC, так что ближайший шаг будет идти вниз по рекурсии для input = BC и dummy = A, а затем вернитесь, чтобы повторить i для начального ввода?

Ответы [ 3 ]

1 голос
/ 11 апреля 2011

Он полностью перетасовывает вход по длине входов, рекурсивно.Поэтому, как только каждая рекурсия перемешивает строку с помощью члена i'th, она возвращает.

Это будет алгоритм сложности n-квадрата в нотации big-O.работать без отладчика;)

1 голос
/ 11 апреля 2011

Добавить глобальный счетчик: 

static int depth = 0; /* calling depth of the recursive method */

Добавить в качестве первой строки shuffle: 

System.out.printf("%" + depth++ + "s call dummy='%s' input='%s'\n", "", dummy, input);

Добавить в качестве последней строки shuffle: 

System.out.printf("%" + --depth + "s return\n", "");

Запустите программу. Теперь вы можете видеть, что происходит.

1 голос
/ 11 апреля 2011

Думайте об этом как о делении работы по шагам.Ваша shuffle функция принимает два аргумента: dummy для части строки, которая уже перетасована, и input для части строки, которая все еще должна быть перетасована.

На каждом шаге,вы перетасовываете первый символ input: 

        for (int i = 0; i < input.length(); i++) {
            input = input.substring(i, i + 1) + input.substring(0, i)
                    + input.substring(i + 1);

, а затем рекурсивно применяете алгоритм, а уже перетасованная часть является символом более длинным: 

            shuffle(dummy + input.substring(0, 1), input.substring(1));

Пока ничего нетбольше перемешать: 

    if (input.length() <= 1)
        System.out.println(dummy + input);
...