Примечание. Изначально это было опубликовано в моем блоге по адресу 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.
Ключевые компоненты, которые бросаются мне в глаза, это:
- У меня есть только одна переменная
partialAnswers
, которой я манипулирую до тех пор, пока она не будет соответствовать критериям полного ответа. Затем я помещаю единственное решение в свой массивallAnswers
. - Я исследую все ответвления первой возможности, затем возвращаюсь на шаг за шагом, пока не вернусь в исходное состояние. В этот момент я начинаю исследовать все ветки в поисках следующей возможности.
- Мой код оказывается в основном простым и чистым. В этой простой задаче мне нужно беспокоиться только об одном параметре/аргументе. (Мой предыдущий неочищенный подход потребовал бы двух аргументов:
remainingProblem
иanswerSoFar
, которые могут быть немного беспорядочными, чтобы поддерживать порядок.)
Волшебство, которое происходит в операторе else
, — это то, что я, возможно, раньше изо всех сил пытался придумать, но теперь это похоже на детскую игру. (Это хорошо, правда?)
Следующий? Возможно, хвостовая рекурсия.