Muy buenas, me llamo Miguel y en esta ocasión les traigo un nuevo tutorial.
Índice
Clave su próxima entrevista con estos útiles problemas de práctica
Como este parece ser un escenario común, especialmente en un entorno de entrevista técnica, estoy preparando una lista de desafíos de algoritmos clásicos para ayudar a flexionar nuestros músculos cerebrales recursivos , ya que este parece ser un escenario común, especialmente en un entorno de entrevista técnica …
1. Inversión de una cuerda
/* Instruction: Given a string, write a recursive function to return the reversed string. */// Example: reverseString('covid') // => 'divoc'
Este parece ser el primer desafío que encuentra todo novato de código. Si aún no ha resuelto este problema con la recursividad, le animo a que lo pruebe antes de seguir leyendo.
Aquí está mi solución, que se puede refactorizar mediante un operador ternario:
2. Sumar los números
/* Instruction: Given an array and an index, write a recursive function to add up the elements of an array. */// Examples: addingUpTo([1, 4, 5, 3], 2) // => 10 // => adding the number all the way up to index 2 (1 + 4 + 5) addingUpTo([4, 3, 1, 5], 1) // => 7 // => adding the number all the way up to index 1 (4 + 3)
Debido a que devolvemos la suma de varios números, inmediatamente pensé en declarar una variable sum.
Además, dado que se nos da un índice, decidí iniciar sum como el elemento en ese índice y agregar los números hacia atrás.
El caso base sería cuando llegamos al final de la operación, que en este caso es index 0, ya que estamos agregando hacia atrás:
3. Encontrar el entero más grande
/* Instruction: Given an array, write a recursive function to find the largest integer in an array. */// Examples: maxOf([1, 4, 5, 3]) // => 5 maxOf([3, 1, 6, 8, 2, 4, 5]) // => 8
Este es un problema de comparación. Entonces, naturalmente, el caso base sería cuando no podemos hacer una comparación (es decir, cuando solo queda un elemento en la matriz).
Ahora, ¿cómo podríamos seguir comparando y reduciendo los elementos en la matriz para llegar al caso base? El método splice en JavaScript vino a mi rescate.
Gracias a la mutabilidad del método splice, puedo comparar los dos primeros elementos de la matriz, eliminar el más pequeño y llamar de forma recursiva a la función con una matriz actualizada:
4. Encontrar elemento específico
/* Instruction: Given an array and a number, write a recursive function to see if the array includes the given element. */// Examples: includesNumber([1, 4, 5, 3], 5) // => true includesNumber([3, 1, 6, 8, 2, 4, 5], 9) // => false
De manera similar a la función maxOf(), necesitamos comparar los elementos de la matriz con el número dado.
Podemos regresar inmediatamente true una vez que encontremos una coincidencia. De lo contrario, podemos llamar a la función de forma recursiva y pasar la matriz menos el elemento con el que acabamos de comparar hasta que alcancemos el caso base.
El caso base que he establecido aquí es cuando no queda ningún elemento en la matriz, en cuyo caso regresamos false, ya que ninguno de los elementos dentro de la matriz coincide con el número dado:
En retrospectiva, debería haber usado en splice lugar del método slice para eliminar el elemento actual.
El uso slice activará una nueva copia de la matriz en cada llamada de función recursiva, lo que podría ralentizar la operación si se le proporciona un conjunto de datos más grande.
5. Palíndromo
/* Instruction: Given a string, write a recursive function to see if a word is a palindrome. */// Examples: isPalindrome('madam') // => true isPalindrome('covid') // => false
Un palíndromo es una palabra o frase que se lee igual si inviertes el orden de todos los caracteres opuestos.
Abordé este problema con un espejo en mente: compare el primer y último carácter de la cadena en cada función recursiva hasta que alcancemos el punto medio, que se convierte en nuestro caso base.
En el caso recursivo, deberíamos regresar inmediatamente false si el carácter actual no equivale al carácter opuesto, ya que este no satisface la composición de un palíndromo:
6. Permutación
/* Instruction: Given a string, write a recursive function to print out an array of all possible permutations of the string. */// Examples: permutations('abc') // => ['abc', 'acb', 'bac', 'bca', 'cab', 'cba'] permutations('aabc') // => ["aabc", "aacb", "abac", "abca", "acab", "acba", "baac", "baca", "bcaa", "caab", "caba", "cbaa"]
Una permutación es la reordenación de un conjunto de elementos. Ahora, necesitamos al menos dos elementos para lograr la permutación. Si la cadena solo tiene un carácter o menos, no hay nada que reorganizar, por lo que ese sería nuestro caso base.
El caso recursivo es complicado para mí. A diferencia de los desafíos anteriores, esta vez necesitamos varias capas de operaciones para lograr los resultados deseados:
Como se comentó en el fragmento de código, en el caso recursivo, no solo necesitamos factorizar el caso en el que hay caracteres repetidos en la cadena dada, sino que también tenemos que concatenar el carácter actual con cada permutación del resultado del recursivo. función.
Si aún le resulta confuso, le recomiendo encarecidamente este tutorial detallado que me ayudó a comprender la solución recursiva para este desafío.
7. Fibonacci
/* Instruction: Given a number, write a recursive function to print out the n-th entry in the fibonacci series. Fibonacci series is a sequence, where each number is the sum of the preceding two: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34] */// Example: fib(3) // => 2 fib(6) // => 8
Escuché que no es común encontrar la solución recursiva sin buscarla, así que aquí está la versión de «libro de texto». Según algunos desarrolladores experimentados, es una fórmula que vale la pena memorizar:
La complejidad en tiempo de ejecución de este enfoque recursivo es exponencial ( O(2^n)), por lo que no es tan eficaz como el antiguo enfoque iterativo simple ( O(n)).
Puede utilizar la memoization técnica para optimizar la recursividad, pero eso está fuera del alcance de este artículo.
Pensamientos finales
Todos tenemos diferentes enfoques para resolver un problema mediante la recursividad. Me tomó bastante práctica desarrollar mi propia estrategia.
A partir de ahora, tiendo a comenzar por descubrir el caso base, como lo sugieren varios recursos. Luego me adentraré en el caso recursivo, que generalmente implica la creación de subtareas y la combinación de los resultados de las subtareas.
¿Cómo entrenas tu cerebro para pensar de forma recursiva? ¡Házmelo saber en los comentarios!
Añadir comentario