¿Por qué la recursión me causa tantos problemas?

No voy a repetir toda la información útil que ya está aquí, porque ya está aquí (recursividad, yay 😀), pero por sus comentarios me parece que su [único] problema es lo que identificó: “trato de siga el patrón que seguirá el código “. Eso es lo que debe evitar con todo el poder de su voluntad * ya que, de lo contrario, también tendrá una recurrencia. Así que aquí hay una forma útil (espero) de analizar el programa de recursión que está escribiendo: debe asumir que no es en absoluto responsable de todo el programa.

Usted es solo uno de los mil empleados corporativos a los que se les asignó la responsabilidad sobre un nivel de recursión. Entonces, cuando vaya a realizar “su” nivel (por ejemplo, f (n)), en cualquier momento puede llamar a la función f (n-1), f (n / 2), etc., simplemente vaya a otro de sus colegas y él en una caja negra en un segundo te da el resultado de esta llamada. Y claro, si hay un error en algún lugar que tal vez su respuesta sea incorrecta, pero usted no es responsable ni puede perder su tiempo de trabajo tratando de verificar si no cometió un error y le dio un resultado incorrecto, si eso es así entonces su resultado también será incorrecto, claro, pero es él quien será despedido por ello. 😀 Entonces, cuando analiza su programa, su única responsabilidad es aceptar ciegamente cualquier resultado que le hayan dado las llamadas recursivas y asegurarse de que si da por sentado que todas fueron correctas, su resultado también será correcto. Por supuesto, dado que en el mundo real, estos otros resultados no se dan instantáneamente desde un cuadro negro, sino que se calculan utilizando la misma función, entonces si puede asegurarse de que su nivel funcione siempre y cuando asuma que todos los demás niveles también funcionan, significa que todo el programa funciona .

* [por supuesto, no estoy hablando aquí sobre la situación cuando ya ha encontrado alguna entrada específica sobre la que sabe que el programa no funciona y puede seguirla a mano para esta entrada específica, pero la situación es exactamente lo mismo para los programas recursivos y los iterativos, por lo que no hay dureza adicional en ese caso: si su aporte es grande, tratar de seguirlo con recursión es infructuoso porque necesitaría seguir hasta 1000 niveles, pero igual de bien tratar de seguir La ejecución del programa iterativo no tiene sentido porque el ciclo habría tenido 1000 iteraciones. Si bien su entrada es pequeña, puede seguir 5 iteraciones a mano en una hoja de papel, pero también puede realizar la recursión bajando 5 niveles en una hoja de papel, así que eso no es un problema entonces]

Los algoritmos recursivos son realmente difíciles de depurar, porque tienden a hacer todo su trabajo al final cuando se acumula el seguimiento de la pila, y muchos algoritmos recursivos se dividen en múltiples caminos. Cada vez que intento resolver un problema, la recurrencia no suele ser lo primero que miro. Es difícil de escribir y muy difícil de extender, por lo que es realmente el más adecuado para problemas fundamentales como las matemáticas y los gráficos.

Aprender a pensar de forma recursiva es muy importante para tu desarrollo como informático. Algunos problemas no tienen una solución iterativa de propósito general. Muchas veces una solución recursiva puede ser más eficiente y más fácil de leer. Si planea perder el tiempo con lenguajes de programación funcionales como esquema o haskell, entonces necesita tener una comprensión sólida de la recursividad, ya que todas las declaraciones de programación en estos lenguajes son esencialmente recursivas.

Es normal tener un momento difícil de recursión las primeras veces que lo ve. Quédate con él, porque te hará un mejor programador.

También me causó problemas al principio. Cuando me encontré por primera vez con la recursión, se explicó con un ejemplo que resuelve un problema simple de Fibonnacci. Resumir una secuencia de Fibonnacci se puede resolver simplemente mediante una iteración, por lo que la recursión no fue la forma real de solución para este simple problema, que me hizo no entender completamente.

Más tarde, trabajé en el problema de las torres de Hanoi. Eso me proporcionó aprender un poco más sobre cuál es la recursión.

Mientras trabajaba en el proyecto de graduación de mi maestría, tuve que escribir el código para el algoritmo ID3 para hacer una clasificación en un conjunto de datos. Ese fue el momento en que entiendo completamente cómo funciona la recursividad. Es casi imposible ejecutar el algoritmo ID3 sin recurrencia.

En pocas palabras, es difícil entender la recursividad hasta que puedas trabajar en un problema que solo puede resolverse mediante la recursión, en otras palabras, un problema de recursión real.

El artículo de Wikipedia explica cómo y por qué usar la recursividad en el algoritmo ID3.

La recursión te causa muchos problemas porque la recursión te causa muchos problemas. 😀

En serio, dices que tienes lo básico. Supongo que eso significa que puede rastrear la función factorial y puede codificar el algoritmo de Fibonacci y las torres del problema de Hanoi de forma recursiva. (Si no, practica).

Las listas enlazadas y los árboles son un terreno fértil para practicar la programación recursiva. Aunque muchas de las funciones pueden (y deben) escribirse de forma iterativa, la recursión a menudo puede ser más descriptiva. Di un ejemplo en la respuesta de Gregory Schoenmakers a ¿Cuál sería el algoritmo que acepta un puntero a un árbol de búsqueda binario y elimina el elemento más pequeño del árbol?

También puede encontrar más ejemplos en https://www.quora.com/profile/Gr… .

Tenga en cuenta que el problema de BearFills que ha vinculado anteriormente no parece ser un problema de programación recurrente. Todo lo que está haciendo es contar subconjuntos, no enumerarlos.

Me parece que la clave para entender cómo usar la recursión es entender que estás escribiendo funciones para llevar a cabo pasos individuales en un problema, usando la pila de tiempo de ejecución para mantener el estado mientras el proceso se lleva a cabo. Estás tratando de generalizar qué es ese único paso que debe llevarse a cabo, y estás usando los parámetros que pasas con cada paso recursivo para configurar las condiciones necesarias para usar ese algoritmo general para resolver el siguiente paso.

En el ejemplo que proporcionó, es realmente un ejercicio de matemática combinatoria. La única condición que debe cumplirse es que todo el rectángulo debe estar completamente cubierto. Entonces, tienes que calcular cuántas combinaciones de sellos cumplen esa condición, dado un rectángulo HxW.

La entrada de número de sellos le indica qué tamaños de sellos tiene disponibles, ya que realmente representa el “ancho” de una “ventana” en una secuencia numérica que va 2 ^ 0, 2 ^ 1, 2 ^ 2, etc. donde cada número m representa un cuadrado m x m . Entonces, si la entrada de número de sellos es 3, los sellos que tiene son 1 × 1, 2 × 2 y 4 × 4. Luego, la tarea es averiguar cuántas combinaciones puede usar para cubrir completamente el rectángulo HxW.

El verdadero desafío en este ejemplo no es repetir los pasos. Entonces, eso tiene que ser parte del estado que guarde a medida que avanza en el proceso. Desea guardar las combinaciones que funcionaron en pasos recursivos anteriores, para no repetirlas en el siguiente paso. Esto requiere algún tipo de estructura de datos, o estructura de “lista”. Me imagino una matriz bidimensional funcionando. El problema te dice cuáles serán los máximos de las dimensiones.

Dentro de cada paso, también necesitará una forma de verificar cuál es el “intento” actual contra lo que ya funcionó. Creo que probablemente necesitará una matriz de “prueba” unidimensional dentro de la función, donde puede almacenar una combinación, y luego puede llamar a otra función para comparar esa “prueba” con los resultados que ya han funcionado. Dentro de la función, debe tener lógica tratando de averiguar si una combinación funciona, y luego comparar para ver si ya se ha probado. En cada paso de la recursión, puede ser posible eliminar algunos pasos avanzando un contador en la lista de parámetros a la función recursiva, que indica algo sobre lo que ya se ha intentado, pero solo estoy especulando.

No dijo en qué idioma estaba trabajando, por lo que la forma en que se implementa lo anterior variará según el idioma. Asumí un mínimo común denominador en mi descripción.