Механизм рекурсивного обратного вызова

Question

Я хотел бы реализовать алгоритм для печати всех допустимых (например, правильно открытых и закрытых) комбинаций n-пар скобок.

Пример:

input: 2(например, 2 пары круглых скобок): () (), (())

Алгоритм работает отлично:

1 public static void f(int l, int r, char[] str, int count) {
2 if (l < 0 || r < l) return; 
3 if (l == 0 && r == 0) {
4     System.out.println(str); 
5 } else {
6     if (l > 0) { 
7         str[count] = ‘(‘;
8         f(l - 1, r, str, count + 1);
9     }
10     if (r > l) { 
11         str[count] = ‘)’;
12         f(l, r - 1, str, count + 1);
13     }
14 }
15 }

, который я вызываю с помощью f (count,count, str, 0) ;, давайте предположим, что в нашем примере f (2,2, "", 0)

Вопрос: Я новичок в программировании и не понимаю механизм обратного вызова внутри процесса рекурсии .

Чтобы шаг за шагом детализировать:

f(2,2,"",0)
-> str = "(" -> f(1,2,"(",1)
-> str = "((" -> f(0,2,"((",2)
-> str = "(()" -> f(0,1,"(()",3)
-> str = "(())" -> f(0,0,"(())",4)
-> print "(())" !

В этой точке я озадачен.Итак, я иду на предыдущий вызов, после вызова f (0,0, "(())", 4).Я попадаю в строку 15 внутри f (0,1, "(()", 3). Вот пробел, что здесь происходит? Я должен попытаться вставить здесь "(" (что не получится, посколькуl == 0), но что у меня в стеке вызовов?

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

Answer 1

Когда функция завершается, она возвращается к месту, где она была первоначально вызвана. Поэтому после того, как вы достигнете строки 15 из f(0,1,"(()",3), программа возобновит работу со строки 13 из f(0,2,"((",2). Если бы вы печатали параметры в начале каждого вызова функции, вы получили бы что-то вроде этого:

f(2, 2, "", 0)
  f(1, 2, "(", 1)
    f(0, 2, "((", 2)
      f(0, 1, "(()", 3)
        f(0, 0, "(())", 4)  <-- print "(())"
    f(1, 1, "()", 2)
      f(0, 1, "()(", 3)
        f(0, 0, "()()", 4)  <-- print "()()"