Рекурсивный поиск в массиве с помощью цикла for
Я знаю, что есть лучшие способы поиска в массиве, но я действительно хочу понять, как вернуться, когда значение найдено в рекурсивном вызове. Регистрация при обнаружении не является проблемой, но я не могу сделать это возвращение истинным при обнаружении.
Проблема основная. Полный поиск значения в многомерном массиве и возврат true, если он найден, или false, если не найден, с использованием цикла for и рекурсии. Я пытался вернуть рекурсивную функцию и все остальное, что я могу придумать, но ничего не работает полностью.
function lookForKey( arr ){
for ( let i = 0; i < arr.length; i++ ) {
if ( arr[i] == "key" ){
console.info( "Key found.");
return true;
} else if ( Array.isArray( arr[i] ) ){
lookForKey( arr[i] );
}
}
return false;
}
let arr = [
["foo", "bar"],
["foo", "bar", "key"]
];
console.info( lookForKey( arr ) );
Я ценю любое понимание этого!
Вы ищете только рекурсивное решение? Есть много способов сделать это.
@jmargolisvt Они не ищут решения. Они хотят узнать, что они делают неправильно.
Спасибо. Я знаю, что это начало. И теперь, когда я думаю об этом, это полностью меняет вопрос. Возврат рекурсивного вызова приводит к возврату функции после проверки первого массива, поскольку он не соответствует ни одному условному выражению. Я просто не уверен, как заставить рекурсивный вызов продолжить предыдущий цикл for после того, как этот первый вызов не найдет совпадения.
![Безумие обратных вызовов в javascript [JS]](https://i.imgur.com/WsjO6zJb.png)
Ответы 4
Результат приходит как false, потому что мы пытаемся вернуть false из функции. Пока цикл for работает, единственный способ прервать его, когда мы получим желаемый результат, — это использовать break. И мы можем сохранить статус поиска в переменной с именем result, которую можно вернуть из функции lookForKey
function lookForKey( arr ) {
var result = false;
for ( let i = 0; i < arr.length; i++ ) {
if ( arr[i] == "key" ){
result = true;
break;
} else if ( Array.isArray( arr[i] ) ){
result = lookForKey( arr[i] );
}
}
return result;
}
В приведенном выше коде вместо того, чтобы возвращать false из функции, мы возвращаем переменную result, которая содержит фактическое значение поиска. Здесь мы используем оператор break, чтобы выйти из цикла for, как только получим желаемый результат.
@Taplar, спасибо, что поправили меня. Я неправильно понял вопрос и отредактировал его сейчас. Дайте мне знать, если вы думаете, что я правильно понял на этот раз. Простите меня, поскольку я новый участник.
function lookForKey( arr ){
for ( let i = 0; i < arr.length; i++ ) {
if ( arr[i] == "key" ){
console.info( "Key found.");
return true;
} else if ( Array.isArray( arr[i] ) ){
if (lookForKey(arr[i])) return true;
}
}
return false;
}
let arr = [
["foo", "bar"],
["foo", "bar", "key"]
];
console.info( lookForKey( arr ) );Итак, две замены. Во-первых, вы должны иметь возврат на рекурсивный вызов. Однако, если рекурсивный вызов возвращает false, вы не хотите возвращаться немедленно от вызывающего объекта. Вы хотите продолжить цикл. Таким образом, вы можете сделать это условным и возвращать true только в том случае, если рекурсивный вызов возвращает true.
Большое спасибо, что нашли время объяснить. Я понимаю, почему это работает. Мне все еще не хватает чего-то, что именно заставляет рекурсивный вызов возвращаться из цикла после проверки последнего элемента в первом массиве, а не продолжать итерацию.
@Mike с данными вашего примера, он вернет true из if, потому что key является последним значением в последнем подмассиве. Если бы он не существовал ни в одном из подмассивов, все циклы for завершились бы без возврата, и в нижней части произошло бы возвращение false.
Извини! Я имел в виду до добавления вашего условного выражения, когда просто возвращал рекурсивный вызов. return lookForKey( arr[i] ); Это останавливается после проверки первого массива данных моего примера, а не переходит к следующему массиву. Я не понимаю, почему это должно прекратиться.
Если у вас нет условного выражения для вложенного вызова, оно войдет в этот вложенный вызов для первого массива. Затем он проверит все элементы и увидит, что они не являются key. Другого не произойдет, потому что ни одно из значений вложенного массива не является массивом, поэтому он вернет false в нижней части метода, который вернет false вызывающей стороне. Итак, в этот момент логика подтвердила, что ключ не находится в первом подмассиве. Если бы вы немедленно вернули это значение false, это привело бы к завершению метода, и вы не перешли бы к проверке продолжающихся подмассивов. @Майк
Вопрос требует рекурсивного решения проблемы, и в этом ответе по-прежнему используется цикл for 🤦🏽♀️
@Спасибо Ответ касается заданной проблемы. Цель вопроса — объяснить, почему это не сработало. Цель не в том, чтобы изменить вопрос. Вы можете не соглашаться с подходом ОП, но научить кого-то тому, как что-то делать, — это неплохо.
@Taplar Я не совсем с тобой согласен. Однако, если ученик остановится на этом ответе и оставит петлю for на месте, вы только научите его, как безрассудно комбинировать технику одной школы мысли с техниками другой школы. Это больше не правильный способ использования любой техники!
Я не согласен с тем, что концепция петли for и концепция recursion — это разные школы мысли. Вы спорите о деталях реализации, а не о школах мысли. @Спасибо, но это становится разговорчивым. Теперь у ОП есть преимущества просмотра этого решения и других решений, чтобы увидеть разные точки зрения.
@ Спасибо. Первое предложение в моем вопросе: «Я знаю, что есть лучшие способы поиска в массиве». Я просто пытался понять кое-что, с чем я столкнулся в упражнении с алгоритмом, которое требует как цикла for, так и рекурсии. Благодаря Taplar у меня теперь гораздо лучшее понимание. Тем не менее, я ценю ваш ответ и опыт рекурсии.
Утверждение найденного условия путем возврата true может быть выполнено в одном логическом выражении, которое будет сокращено, как только истина станет неоспоримой.
function myFind( haystack, needle ){
for ( let i = 0; i < haystack.length; i++ ) {
if ( haystack[i] === needle
||
( Array.isArray( haystack[i] )
&&
myFind( haystack[i], needle )
)
)
return true; // return only when found
// not found, check next array element
}
return false; // not found as any element or in any element
}
let arr = [
["foo", "bar"],
["foo", "bar", "key"]
];
console.info( myFind( arr, "key" ) );
console.info( myFind( arr, "foo" ) );
console.info( myFind( arr, "xyzzy" ) );Спасибо @richard! Ваше объяснение тоже очень помогло.
Рекурсия — это функциональное наследие, поэтому ее использование с функциональным стилем дает наилучшие результаты. Это означает, что нужно избегать таких вещей, как мутации, переназначение переменных и другие побочные эффекты. for — это побочный эффект и конструкция цикла, используемая в императивном стиле. Обратите внимание, что когда мы используем функциональный стиль, нет причин использовать for, поскольку рекурсия — это цикл.
- Если ввод
arrпуст, искать нечего. Вернуть базовый регистр,false - (индукция) Вход
arrне пуст. Если первый элементarr[0]является массивом, рекурсивноsearchэлемент или рекурсивно ищите подзадачу,arr.slice(1) - (индукция) Вход
arrне пуст, и первый элемент не является массивом. Если первый элемент соответствует запросу,q, вернуть true, в противном случае рекурсивно искать подзадачу,arr.slice(1)
Ниже мы пишем search, используя индуктивное рассуждение, приведенное выше -
function search (arr, q)
{ if (arr.length === 0)
return false // 1
else if (Array.isArray(arr[0]))
return search(arr[0], q) || search(arr.slice(1), q) // 2
else
return arr[0] === q || search(arr.slice(1), q) // 3
}
const input =
[ ["foo", "bar"]
, ["foo", "bar", "key"]
]
console.info(search(input, "key"))
console.info(search(input, "bar"))
console.info(search(input, "zzz"))Если мы лукавим, if, else и return также являются побочными эффектами. Вы также можете написать search как чистое выражение -
const search = (arr, q) =>
arr.length === 0
? false // 1
: Array.isArray(arr[0])
? search(arr[0], q) || search(arr.slice(1), q) // 2
: arr[0] === q || search(arr.slice(1), q) // 3
const input =
[ ["foo", "bar"]
, ["foo", "bar", "key"]
]
console.info(search(input, "key"))
console.info(search(input, "bar"))
console.info(search(input, "zzz"))А присваивание деструктурирования делает вещи немного более декларативными.
const none =
Symbol("none")
const search = ([ v = none, ...more ], q) =>
v === none
? false // 1
: Array.isArray(v)
? search(v, q) || search(more, q) // 2
: v === q || search(more, q) // 3
const input =
[ ["foo", "bar"]
, ["foo", "bar", "key"]
]
console.info(search(input, "key"))
console.info(search(input, "bar"))
console.info(search(input, "zzz"))Все варианты search выше имеют одинаковый результат -
true
true
false
Я вызвал некоторые споры, сделав несколько комментариев о рекурсии и for циклах, не принадлежащих к одной и той же школе мысли. Во-первых, вот как search может выглядеть без рекурсии:
function search (arr, q)
{ const s = [arr]
let v
while(v = s.shift())
if (Array.isArray(v))
for (const _ of v)
s.unshift(_)
else if (v === q)
return true
return false
}
const input =
[ ["foo", "bar"]
, ["foo", "bar", "key"]
]
console.info(search(input, "key"))
console.info(search(input, "bar"))
console.info(search(input, "zzz"))Но это не значит, что идеи не могут пересекать школы. Рассмотрим этот вариант, который использует forEach с рекурсией и опирается на технику вызова с текущим продолжением, callcc ниже —
const callcc = f =>
{ try { return f(value => { throw {callcc, value} }) }
catch (e) { if (e.callcc) return e.value; else throw e }
}
function search (arr, q)
{ const loop = (t, exit) =>
Array.isArray(t)
? t.forEach(v => loop(v, exit))
: t === q && exit(t)
return callcc(k => loop(arr, k))
}
const input =
[ ["foo", "bar"]
, ["foo", "bar", "key"]
]
console.info(search(input, "key"))
console.info(search(input, "bar"))
console.info(search(input, "zzz"))этот ответ - искусство <3, +1
@thank you Хотя это не относится к моему конкретному вопросу, это отличная информация, и она очень хорошо составлена. Я обязательно изучу все, чем вы поделились.
рад помочь, Майк. не стесняйтесь обращаться, если вы где-то застряли.
Ваш else if не возвращается. Итак, если рекурсивный вызов возвращает true/false, то ничего не делается с результатом от вызывающей стороны.