Sé que esto puede ser básico y simple, pero como soy autodidacta, quería saber qué estaba mal y pensé que este es el mejor lugar para aprender.
Estoy tratando de escribir un código recursivo que devuelva verdadero o falso. La condición a verificar es si el conjunto de palabras puede formar la palabra objetivo dada.
El error que sigo recibiendo es:
if (targetString.indexOf(dictionary[i]) == 0) { ^ RangeError: Maximum call stack size exceeded at String.indexOf (<anonymous>)Estoy bastante seguro de que el problema con el código está en una forma en la que estoy regresando porque siempre lo encuentro confuso.
mi código es:
let targetString = "furniture"; let dictionary = ["fur", "ure", "nit"]; const tableData = {}; const canConstructRecursive = (targetString, dictionary) => { if (targetString == "") { return true } for (let i = 0; i < dictionary.length; i++) { if (targetString.indexOf(dictionary[i]) == 0) { shorterTargetString = targetString.slice(0, dictionary[i].length); return canConstructRecursive(shorterTargetString, dictionary); } } return false; } console.log(canConstructRecursive(targetString, dictionary));Estoy aprendiendo recursividad y, de vez en cuando, siento que no entiendo la lógica de volver a la llamada recursiva siguiente/anterior.
Realmente agradecería si alguien pudiera ayudarme con lo que estoy haciendo mal y cambiar mi forma de pensar.
Mi forma de pensar es que:
el caso base se devuelve si se alcanza en esa etapa; de lo contrario, el bucle pasa por todas las opciones y el nodo interno o la pila superior deben devolver el valor a la pila inferior, por lo que estoy haciendo return canConstructRecursive() inside for. Si incluso en todas las opciones, que es toda la iteración del bucle for, no se devuelve, al final se devuelve falso.
Gracias de antemano
La razón es que aunque su variable se llame shorterTargetString , no se garantiza que sea realmente más corta. Si i es el índice de la palabra más corta en el dictionary , entonces no hay forma de que su cadena se acorte al repetirla.
El error es que el segmento no debe comenzar en 0, sino después de la parte que coincidió, por lo tanto, elimine el primer argumento de la llamada del slice .
Esto resolverá el error de desbordamiento de pila.
En segundo lugar, si la llamada recursiva devuelve false , no debe darse por vencido, sino seguir intentándolo con la siguiente palabra. Por lo tanto, solo return del bucle cuando sea true de la recursividad:
let targetString = "furniture"; let dictionary = ["fur", "ure", "nit"]; const tableData = {}; const canConstructRecursive = (targetString, dictionary) => { if (targetString == "") { return true } for (let i = 0; i < dictionary.length; i++) { if (targetString.indexOf(dictionary[i]) == 0) { shorterTargetString = targetString.slice(dictionary[i].length); if (canConstructRecursive(shorterTargetString, dictionary)) { return true; }; } } return false; } console.log(canConstructRecursive(targetString, dictionary)); Su código devolverá incondicionalmente el valor de la llamada recursiva, incluso cuando sea false . Esto no es bueno: en caso de que la llamada recursiva devuelva false , la persona que llama debe continuar con su ciclo for para probar alternativas.
Por ejemplo, agreguemos una palabra a su diccionario de ejemplo: estará de acuerdo en que agregar una palabra del diccionario no debería cambiar el resultado de la entrada "mobiliario". Asi que aqui esta:
["furn", "fur", "ure", "nit"] Pero sorpresa: ¡su código ahora devuelve false para "muebles"! Esto se debe a que "furn" es matemático, pero la llamada recursiva con "iture" como primer argumento no encuentra más coincidencias, por lo que devuelve false , y ahora la persona que llama también devuelve false . Esto está mal. Debería renunciar a "furn", pero no a todo el ejercicio. Debería haber continuado y probado con "piel". Esta es la razón por la que la salida del bucle for sólo debe ocurrir en caso de éxito , no en caso de error . La falla solo se puede confirmar cuando se han probado todas las palabras del diccionario, por lo que el ciclo for debe continuar mientras no haya un éxito recursivo.
El usuario trincot ya explicó qué estaba mal con su código. Aquí, solo quiero señalar que su estructura, que es algo así como for (...) {if (...) { if (...) {return true} } } return false , podría manejarse mejor con Array.prototype.some y una instrucción && . Combinando esto con el hecho de que t .indexOf (s) == 0 podría expresarse más claramente como t .startsWith (s) , y agregando una declaración condicional en lugar de una declaración if , podemos llegar a lo que creo que es una declaración más formulación elegante:
const canConstruct = (t = '', ss = []) => t == '' ? true : ss .some ((s) => t .startsWith (s) && canConstruct (t .slice (s .length), ss)) console .log (canConstruct ('furniture', ['fur', 'ure', 'nit'])) //=> true console .log (canConstruct ('furniture', ['furn', 'fur', 'ure', 'nit'])) //=> true console .log (canConstruct ('banana', ['b', 'ana'])) //=> false console .log (canConstruct ('banana', ['ba', 'na'])) //=> true