Entiendo cómo leer la recursividad pero no sé cómo resolverlos.

En primer lugar, no hay ningún problema en la programación que requiera una solución recursiva.

En el mundo real, en la industria, al escribir código que tiene que vender a los clientes y obtener ganancias y cumplir con los plazos, los programadores casi nunca usan la recursividad.

La recursión casi nunca se ve fuera de la academia.

Dicho esto, aprender a resolver problemas usando la recursividad, o aprender a detectar problemas que se pueden resolver usando la recursividad, es una habilidad útil porque te ayuda a expandir tu forma de pensar. En ese sentido, es como una lección de patrones de diseño.

Para ver si un problema se puede resolver utilizando un algoritmo recursivo, la clave es preguntarse si el problema se puede volver a enmarcar de esta manera:

problema X = solución parcial Y + problema X-1

Por ejemplo, la multiplicación de enteros.

X * Y = X + (X * (Y-1))

Las soluciones recursivas son a menudo muy pobres e ineficientes. Por ejemplo, considere el problema de crear un valor de cadena separado por comas de una lista de elementos (semi-pseudocódigo):

string CSVString (elementos de la lista) {
if (items.Count == 0) return “”;
devolver items.First.ToString () + “,” + CSVstring (items.Remove (0));
}

Sí, me doy cuenta de que el código anterior incluye una coma adicional al final. El punto, la solución recursiva a ese problema es terriblemente ineficiente, y nunca verías tal cosa en un código real para un producto real. A menos que el programador solo tratara de ser lindo.

Para responder a su pregunta, detectar soluciones recursivas a los problemas requiere tiempo y práctica. Se trata de ver cómo se puede enmarcar el problema como una solución parcial simple + alguna reducción del problema original.

Ya sea que esté utilizando un bucle o una recursión, siempre es valioso identificar la condición de terminación, la invariante (la condición que se garantiza que es cierta en cada pase) y la variante (un número natural que se garantiza que disminuirá en cada pase: no puede ir por debajo de cero, por lo que esto garantiza la terminación). En la terminación, tanto la condición de terminación como la invariante están garantizadas.

Por ejemplo, si necesita procesar cada elemento en una lista de longitud n , uno por uno, lo invariable es que el número de elementos procesados ​​más el número de elementos que aún se deben procesar es siempre n , la condición de terminación es que el número de los elementos que aún deben procesarse son cero y la variante es el número de elementos que aún deben procesarse.

En ese ejemplo, para configurar una recursión (¡o un bucle!) Se ramifica si ya ha alcanzado la condición de terminación. Si es así, ya terminaste. De lo contrario, debe hacer algo que reduzca el valor de la variante, en este caso, la cantidad de elementos que aún deben procesarse. Bueno, eso está bastante claro: ¡procesa un artículo! Luego recurse (o bucle) en lo que queda.

La configuración de la recursión eficiente es un poco más complicada y solo es realista si está utilizando un lenguaje o entorno que optimiza la recursividad de cola. Eso es más de lo que puedo ingresar fácilmente en un solo mensaje aquí, pero hay muchos cursos en línea que lo enseñan: el Coursera one en la programación Scala es excelente (y gratuito).

Respondí una pregunta similar, en otro hilo:

La respuesta de Martin Klarqvist a ¿Cómo se construye este método (s) recursivo en Java?

Este ejemplo contiene una función, con un bucle dentro, haciendo una llamada recursiva a sí mismo.

En la mayoría de los casos, un bucle es lo suficientemente bueno para lo que está tratando de lograr. Un bucle es una declaración que se repite siempre que se cumpla la condición dada. A menudo no hay una buena razón para que una función se llame a sí misma utilizando un bucle. Si está utilizando un método, puede haber una razón para llamar al método de una instancia de objeto de la misma clase (siempre que el método no sea estático). El objeto en cuestión podría, por ejemplo, no tener acceso a cierta información o una propiedad podría no estar configurada. Por ejemplo, si estás en un teatro y alguien te pregunta en qué fila estás sentado, si no lo sabes, puedes preguntarle a la persona que está frente a ti y solo agregarás 1 fila a eso. Si la persona frente a usted no sabe, podría preguntarle a la persona frente a él, etc.

pseudocódigo ejemplos de diferentes formas de bucle:

while (condición) {
hacer algo
}

para (iterador hacer algo
iterador de incremento
}

etiqueta:
hacer algo
if (condición) {
ir a la etiqueta
}

myFunction (valor) {
hacer algo con valor
if (el valor cumple la condición de condición) {
valor = myFunction (valor)
}
valor de retorno
}

En general, debe evitar usar los dos últimos por razones de rendimiento y legibilidad. Los primeros dos ejemplos son funciones estándar incluidas en la mayoría de los idiomas en estos días, por lo que google while o for loop para cualquier idioma que esté utilizando y lo encontrará más probable.

Mi respuesta no ha cambiado mucho desde que hiciste esta pregunta anteriormente. La respuesta de Gregory Schoenmakers a ¿Cómo sabes qué poner para tu caso general en métodos recursivos?

Más allá de cierto punto, todo lo que puedes hacer es practicar, practicar, practicar.

Resuelve un montón de problemas de recursión. Pídale a un maestro ejemplos de problemas y trabaje mucho en ellos. Dicho esto, la recursión puede ser difícil de razonar y casi siempre es más lenta que la solución iterativa. Tiendo a evitar la recursión donde puedo.