Как рекурсия работает в перестановке?

Question

Я смотрю программу перестановок, написанную here. Код выглядит следующим образом:

public static void main(String[] args) { 
    permutation("", "CAT"); 
} 

private static void permutation(String prefix, String str) { 
    int n = str.length(); 
    if (n == 0) { 
     System.out.println(prefix); 
    } else { 
     for (int i = 0; i < n; i++) { 
      permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1)); 
     } 
    } 
} 

за слово CAT, я получаю следующий результат:
CAT
CTA
ACT
ATC
TCA
TAC

Я могу проследить через шаги рекурсии и понять, как это работает, чтобы получить CAT и CTA, но я не вижу, как это продолжается. После n == 0 (это базовый случай) все должно прекратиться (что произойдет после того, как мы получим CTA).

Другие источники:
Я прочитал объяснение here, но я все еще возникают проблемы с пониманием, как он продолжает идти. Я чувствую, что понимаю концепцию рекурсии. Я могу использовать его вслепую, но я хочу понять, КАК он работает здесь.

Существует еще одна версия перестановочной рекурсии here, но это использование backtracking, и я понимаю, что это немного лучше. Это рекурсивный хвост, который я не понимаю.

Вопрос:
Может кто-то пожалуйста, объясните, как рекурсия работает так, что мы заканчиваем СТО в приведенном выше примере? Это не домашнее задание. Я просто смотрю в разные программы и работаю через некоторых мастеров-мастеров.

Спасибо!

Answer 1

Давайте посмотрим на то, что генерирует первый вызов:

("" + str.charAt(0), str.substring(0, 0) + str.substring(0 + 1)) 
p("C", "AT") 

("" + str.charAt(1), str.substring(0,1) + str.substring(1 + 1)) 
p("A", "CT") 

("" + str.charAt(2), str.substring(0, 2) + str.substring(2 + 1)) 
p("T", "CA") 

Каждого вызов извлекает каждую букву str и добавляет его к текущей приставке. Первый вызов помещает каждую букву исходной строки в начало перестановки. Тогда для каждой такой перестановки, алгоритм извлекает каждую букву оставшегося суффикса и добавляет его к накопительной приставке, так что все возможности исследуются:

C AT 
    CA T 
    CT A 
     "CAT" 
     "CTA" 

A CT 
    AC T 
    AT C 
     "ACT" 
     "ATC" 

T CA 
    TC A 
    TA C 
     "TCA" 
     "TAC" 

Answer 2

Помните о состоянии (значения каждой локальной переменной и параметров) для каждого рекурсивного вызова. Только один вызов заканчивается после того, как возвращается CAT, остальные продолжаются там, где они остановились.

Думайте о каждом рекурсивном вызове как о вызове совершенно новой функции, которая просто делает то же самое.

Так будет выполняться ваша функция. Это может помочь, если вы также указали значения каждой локальной переменной (в вашем случае это всего лишь i и параметры). Я просто написал, что называет.

p("", "CAT") -> p("C", "AT") -> p("CA", "T") -> p("CAT", "") -> CAT and return 
              -> return 
          -> p("CT", "A") -> p("CTA", "") -> CTA and return 
              -> return 
          -> return 
      -> p("A", "CT") -> ...