Примечание. Изначально это было опубликовано в моем блоге по адресу https://therobinkim.com/blog/recognizing-a-pattern-in-my-recursive-functions. Любые обновления будут появляться там, а не здесь.

Шон Дрост из Hack Reactor научил меня писать рекурсивные функции с оператором if-else:

function recursion() {
  if(baseCase) {
    // do something
  } else {
    // get me 1 step closer to the base case
  }
}

Когда я просматривал некоторые учебные материалы из Hack Reactor и метался по кодовым войнам, я начал распознавать общий паттерн в своем коде при решении задач перестановок, основанных на предложении Шона.

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

function findAllAnswers(problem) {
  var partialAnswer = "";
  var allAnswers = [];

  findAnswers(problem);

  return allAnswers;

  function findAnswer(problem) {
    if(problem.length === 0) {
      allAnswers.push(partialAnswer);
      return;
    }
    else {
      // add the first bit of 'problem' to partialAnswer
      partialAnswer.push(problem[0]);
      // explore all branches that include this first bit
      findAnswer(problem.slice(1));
      // lets remove what we added just before the recursive call
      partialAnswer = partialAnswer.substring(0, partialAnswer.length - 1);
    }
  }
}

Я использовал этот подход, чтобы решить проблему N-Queens, перечислить все возможности совпадения «камень-ножницы-бумага» и найти все перестановки слов, которые вы могли бы ввести в цифровую клавиатуру мобильного телефона T-9.

Ключевые компоненты, которые бросаются мне в глаза, это:

  1. У меня есть только одна переменная partialAnswers, которой я манипулирую до тех пор, пока она не будет соответствовать критериям полного ответа. Затем я помещаю единственное решение в свой массив allAnswers.
  2. Я исследую все ответвления первой возможности, затем возвращаюсь на шаг за шагом, пока не вернусь в исходное состояние. В этот момент я начинаю исследовать все ветки в поисках следующей возможности.
  3. Мой код оказывается в основном простым и чистым. В этой простой задаче мне нужно беспокоиться только об одном параметре/аргументе. (Мой предыдущий неочищенный подход потребовал бы двух аргументов: remainingProblem и answerSoFar, которые могут быть немного беспорядочными, чтобы поддерживать порядок.)

Волшебство, которое происходит в операторе else, — это то, что я, возможно, раньше изо всех сил пытался придумать, но теперь это похоже на детскую игру. (Это хорошо, правда?)

Следующий? Возможно, хвостовая рекурсия.