Как происходит перестановка букв в этом алгоритме с рекурсией?

Question

[Luke LikeSkywalker]

Наткнулся на такой код.

function getPermutations(string) {

  // Base case
  if (string.length <= 1) {
    return new Set([string]);
  }

  const allCharsExceptLast = string.slice(0, -1);
  const lastChar = string[string.length - 1];

  // Recursive call: get all possible permutations for all chars except last
  const permutationsOfAllCharsExceptLast = getPermutations(allCharsExceptLast);

  // Put the last char in all possible positions for each of the above permutations
  const permutations = new Set();
  permutationsOfAllCharsExceptLast.forEach(permutationOfAllCharsExceptLast => {
    for (let position = 0; position <= allCharsExceptLast.length; position++) {
      const permutation = permutationOfAllCharsExceptLast.slice(0, position) + lastChar + permutationOfAllCharsExceptLast.slice(position);
      permutations.add(permutation);
    }
  });

  return permutations;
}

В данном коде не совсем понятно почему выполняется блок кода который находится после рекурсивного вызова. Он же должен выполниться только один раз или он будет выполняться каждый раз с вызовом каждой функции? И если так то почему блок кода может использовать переменную permutationsofAllCharsExceptLast если он пока ещё не «готов»?
Можно объяснить на пальцах или схемами, я немного туповат.

Comments

[WapSter]

Не ты один этого не понимаешь, давно пользуюсь js, но до сих пор не понимаю как работает рекурсия.

[Roman]

Знание принципов освобождает от запоминания множества фактов.

Answer 1

[Руслан .]

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

Условие для остановки рекурсии:
if (string.length <= 1) {
return new Set([string]);
}

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

Проще на примере, если взят строку 'ABC' на вход, то рекурсия будет такой
->getPermutations('ABC')
--> getPermutations('AB')
---> getPermutations('A')
----> getPermutations('')
<---- ''
<---'A'
<--'A', 'BA', 'AB'
<-'A', 'BA', 'AB', 'CA', 'AC', 'CBA', 'BCA', 'BAC', 'CAB', 'ACB', 'ABC'

Comments

[Luke LikeSkywalker]

А как насчёт второго блока? В какой момент он выполняется?

[Руслан .]

oolooq, второй блок выполняется в тот момент, когда начинается подъем вверх.
На моей схеме это место помечено:
<---- ''
Это тот момент, когда в вызываемой функции выполняется оператор return.
Т.е. выходит так, что после:

if (string.length <= 1) {
return new Set([string]);
}

Выполнение передается в место предыдущего вызова:

const permutationsOfAllCharsExceptLast = getPermutations(allCharsExceptLast);

Далее отрабатывает второй блок и исполняется

return permutations;

Который передает управление на предыдущий вызов

const permutationsOfAllCharsExceptLast = getPermutations(allCharsExceptLast);

Либо, если стек уже пустой, то на выход из процедуры.

[h88p]

Руслан ., Почему у вас ----> getPermutations(''), если при условии, что <=1 идет return?

[Руслан .]

h88p,
А здесь вы правы, не доглядел.

При string = 'A' уже сработает проверка:
if (string.length <= 1) {
return new Set([string]);
}
и вернется return new Set([string]);

Т.е. глубина рекурсии будет на 1 шаг короче, чем у меня.

[Anyuta300699]

Руслан ., подскажите, пожалуйста, будет ли это работать, если буквы повторяются? допустим пример ata

[Руслан .]

Anyuta300699, судя по коду должно, но есть нюанс. Все дублирующиеся буквы будут считаться одной буквой и перестановка a(1) t a(2) будет идентично a(2) t a(1) и в выходной set будет только один экземпляр ata.

Answer 2

[Luke LikeSkywalker]

Окей я разобрался. Спасибо что помогли. От себя хочу добавить маленькую схему если кто нибудь зашёл сюда через поисковик.

Или

Answer 3

[Владимир Олохтонов]

Число вызовов не будет бесконечным, потому что строка конечна, а от неё при каждом рекурсивном вызове отсекается последний символ.

Вызов функции вернёт управление в точку вызова в момент завершения, если для этого понадобится подождать возврата управления от каких-то других вызовов — будем ждать.

Попробуйте что-нибудь совсем простое написать в рекурсивной форме, чтобы разобраться с тем как это работает, например программу, которая считает до 10, добавляя по 1 при каждом вызове.

PS: несмотря на то, что рекурсия выглядит как будто это одна функция, на самом деле это целое дерево вызовов, для каждого из которых состояние (фрейм) хранится в памяти, поэтому память будет расходоваться вот так: O(ncalls * call_consumtion).