@oolooq

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

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

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 если он пока ещё не «готов»?
Можно объяснить на пальцах или схемами, я немного туповат.
  • Вопрос задан
  • 149 просмотров
Решения вопроса 2
LaRN
@LaRN
Senior Developer
При каждом заходе в тело функции 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'
Ответ написан
@oolooq Автор вопроса
Окей я разобрался. Спасибо что помогли. От себя хочу добавить маленькую схему если кто нибудь зашёл сюда через поисковик.5cc7a6c210538170820481.png

Или
5cc7a7034f0e6263872076.png
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
sgjurano
@sgjurano
Разработчик
Число вызовов не будет бесконечным, потому что строка конечна, а от неё при каждом рекурсивном вызове отсекается последний символ.

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

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

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы