Я знаю, что есть лучшие способы поиска в массиве, но я действительно хочу понять, как вернуться, когда значение найдено в рекурсивном вызове. Регистрация при обнаружении не является проблемой, но я не могу сделать это возвращение истинным при обнаружении.
Проблема основная. Полный поиск значения в многомерном массиве и возврат 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 ) );
Я ценю любое понимание этого!
🤔 А знаете ли вы, что...
JavaScript обеспечивает обработку ошибок с использованием конструкции try...catch.
Результат приходит как 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, как только получим желаемый результат.
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.
Утверждение найденного условия путем возврата 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" ) );Рекурсия — это функциональное наследие, поэтому ее использование с функциональным стилем дает наилучшие результаты. Это означает, что нужно избегать таких вещей, как мутации, переназначение переменных и другие побочные эффекты. for — это побочный эффект и конструкция цикла, используемая в императивном стиле. Обратите внимание, что когда мы используем функциональный стиль, нет причин использовать for, поскольку рекурсия — это цикл.
arr пуст, искать нечего. Вернуть базовый регистр, falsearr не пуст. Если первый элемент 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"))