Вы делаете так называемый поиск в глубину через рекурсию . Каждый речит рекурсию немного по-своему. Что-то в конечном итоге заставит вас щелкнуть.
Я хотел бы сделать пару аннотаций в вашем коде, которые помогут ему распечатать более естественную расшифровку того, что происходит. Надеюсь, это поможет некоторым.
Но я думаю, что самое важное - это визуализировать, сколько уровней глубоко в рекурсии у вас с некоторым отступом. Когда вы регистрируетесь во время рекурсивного поиска в глубину, вы в основном создаете двоичное дерево, в котором результат выглядит так:
Root
Root > Left
Root > Right
И он начинает вкладываться с рекурсией, как это:
Root
Root > Left
Root > Left > Left
Root > Left > Right
Root > Right
Root > Right > Left
Root > Right > Right
И вместо «левого» и «правого» путей вы создаете «+5» и «* 3» ветви исследования. В своей рекурсии вы сначала исследуете ветку +5 дерева в поисках решения. Если вы его не найдете, вы исследуете ветку * 3 дерева. Если ничего не найдено, это просто означает, что ответ не лежит на рассматриваемой вами ветке, и необходимо сделать другой выбор ранее в дереве.
Некоторое обратное отслеживание возникает при попытке обоих путейи ни один не преуспевает. Но на самом деле это всего лишь вывод из гипотезы, в которой мы говорим: «Можем ли мы попасть туда, если мы +5?»или "мы можем туда добраться, мы * 3?"Если ответ «нет» на оба вопроса, вы просто не сможете добраться туда, где находитесь. Вы не должны фактически возвращаться назад, красота рекурсии в том, что вы попали туда, где находитесь в поиске, потому что кто-то вызвал вас как часть «что если ...». Если весь ваш поиск окажется пустым, нет проблем. Вы просто оставляете свою текущую ветвь поиска, и «кто-то», вызвавший вас, попробует что-то другое в другой ветке.
Состояние вашей рекурсии (какую ветку вы исследуете) сохраняется на вашем стек вызовов . Вот где мы на самом деле «поддерживаем».
history никогда не изменяется. Мы просто исследуем различные версии history, которые создаются с помощью рекурсии. Каждый history является своей собственной копией, и он только когда-либо становится длиннее (левая или правая ветвь в дереве поиска) или прекращается, и поиск продолжается из некоторого другого history в другом месте рекурсии.
ТакВот ваш код с некоторыми отступами и многословными описаниями того, что происходит на каждом шаге, которое, мы надеемся, немного ближе к рекурсии.
function spaces(indent) {
return ' '.repeat(indent);
}
function findSolution(target) {
function nope(indent, history) {
console.log(spaces(indent) + `Sadly we've exhausted all possible ways of getting there from this starting point. We may still be able to get to ${target}, but not by starting from ${history}.`);
return false;
}
function badnews(history) {
console.log(`I've tried everything and there's just no way of getting to ${target}. :(`);
return false;
}
function find(current, which, history, indent) {
if (current == target) {
console.log(spaces(indent) + `${which}, and guess what...we finally found a solution! Because ${history} = ${current}. So we can stop now. :)`);
return history;
} else if (current > target) {
//console.log(`CURRENT AT NULL: ` + current);
console.log(spaces(indent) + `${which}, we reached a dead end because ${history} = ${current} which is unfortunately already bigger than ${target}.`);
return null;
} else {
console.log(spaces(indent) + `${which}, ${history} looks promising because it equals ${current}, which is still less than ${target}. We'll try two ways of getting to ${target} from here.`);
return find(current + 5, 'First, by adding 5', `(${history} + 5)`, indent+1) ||
find(current * 3, 'Second, by multiplying by 3', `(${history} * 3)`, indent+1) ||
nope(indent+1, history);
}
}
return find(1, 'Initially', "1", 0) || badnews();
}
console.log(`${findSolution(24)}`);
Вывод копируется ниже, на всякий случай. Извините, нет переноса выходных данных, потому что отступ имеет более важное значение, поэтому вы можете увидеть, сколько уровней в глубине рекурсии вы находитесь, и что вызывает обратный путь. Вы можете запустить сниппет, если вы находите вывод консоли сниппета более читабельным.
Initially, 1 looks promising because it equals 1, which is still less than 24. We'll try two ways of getting to 24 from here.
First, by adding 5, (1 + 5) looks promising because it equals 6, which is still less than 24. We'll try two ways of getting to 24 from here.
First, by adding 5, ((1 + 5) + 5) looks promising because it equals 11, which is still less than 24. We'll try two ways of getting to 24 from here.
First, by adding 5, (((1 + 5) + 5) + 5) looks promising because it equals 16, which is still less than 24. We'll try two ways of getting to 24 from here.
First, by adding 5, ((((1 + 5) + 5) + 5) + 5) looks promising because it equals 21, which is still less than 24. We'll try two ways of getting to 24 from here.
First, by adding 5, we reached a dead end because (((((1 + 5) + 5) + 5) + 5) + 5) = 26 which is unfortunately already bigger than 24.
Second, by multiplying by 3, we reached a dead end because (((((1 + 5) + 5) + 5) + 5) * 3) = 63 which is unfortunately already bigger than 24.
Sadly we've exhausted all possible ways of getting there from this starting point. We may still be able to get to 24, but not by starting from ((((1 + 5) + 5) + 5) + 5).
Second, by multiplying by 3, we reached a dead end because ((((1 + 5) + 5) + 5) * 3) = 48 which is unfortunately already bigger than 24.
Sadly we've exhausted all possible ways of getting there from this starting point. We may still be able to get to 24, but not by starting from (((1 + 5) + 5) + 5).
Second, by multiplying by 3, we reached a dead end because (((1 + 5) + 5) * 3) = 33 which is unfortunately already bigger than 24.
Sadly we've exhausted all possible ways of getting there from this starting point. We may still be able to get to 24, but not by starting from ((1 + 5) + 5).
Second, by multiplying by 3, ((1 + 5) * 3) looks promising because it equals 18, which is still less than 24. We'll try two ways of getting to 24 from here.
First, by adding 5, (((1 + 5) * 3) + 5) looks promising because it equals 23, which is still less than 24. We'll try two ways of getting to 24 from here.
First, by adding 5, we reached a dead end because ((((1 + 5) * 3) + 5) + 5) = 28 which is unfortunately already bigger than 24.
Second, by multiplying by 3, we reached a dead end because ((((1 + 5) * 3) + 5) * 3) = 69 which is unfortunately already bigger than 24.
Sadly we've exhausted all possible ways of getting there from this starting point. We may still be able to get to 24, but not by starting from (((1 + 5) * 3) + 5).
Second, by multiplying by 3, we reached a dead end because (((1 + 5) * 3) * 3) = 54 which is unfortunately already bigger than 24.
Sadly we've exhausted all possible ways of getting there from this starting point. We may still be able to get to 24, but not by starting from ((1 + 5) * 3).
Sadly we've exhausted all possible ways of getting there from this starting point. We may still be able to get to 24, but not by starting from (1 + 5).
Second, by multiplying by 3, (1 * 3) looks promising because it equals 3, which is still less than 24. We'll try two ways of getting to 24 from here.
First, by adding 5, ((1 * 3) + 5) looks promising because it equals 8, which is still less than 24. We'll try two ways of getting to 24 from here.
First, by adding 5, (((1 * 3) + 5) + 5) looks promising because it equals 13, which is still less than 24. We'll try two ways of getting to 24 from here.
First, by adding 5, ((((1 * 3) + 5) + 5) + 5) looks promising because it equals 18, which is still less than 24. We'll try two ways of getting to 24 from here.
First, by adding 5, (((((1 * 3) + 5) + 5) + 5) + 5) looks promising because it equals 23, which is still less than 24. We'll try two ways of getting to 24 from here.
First, by adding 5, we reached a dead end because ((((((1 * 3) + 5) + 5) + 5) + 5) + 5) = 28 which is unfortunately already bigger than 24.
Second, by multiplying by 3, we reached a dead end because ((((((1 * 3) + 5) + 5) + 5) + 5) * 3) = 69 which is unfortunately already bigger than 24.
Sadly we've exhausted all possible ways of getting there from this starting point. We may still be able to get to 24, but not by starting from (((((1 * 3) + 5) + 5) + 5) + 5).
Second, by multiplying by 3, we reached a dead end because (((((1 * 3) + 5) + 5) + 5) * 3) = 54 which is unfortunately already bigger than 24.
Sadly we've exhausted all possible ways of getting there from this starting point. We may still be able to get to 24, but not by starting from ((((1 * 3) + 5) + 5) + 5).
Second, by multiplying by 3, we reached a dead end because ((((1 * 3) + 5) + 5) * 3) = 39 which is unfortunately already bigger than 24.
Sadly we've exhausted all possible ways of getting there from this starting point. We may still be able to get to 24, but not by starting from (((1 * 3) + 5) + 5).
Second, by multiplying by 3, and guess what...we finally found a solution! Because (((1 * 3) + 5) * 3) = 24. So we can stop now. :)
(((1 * 3) + 5) * 3)