Cómo resolver la recursividad cuando no tienen caminos claros

Hola, leí tu pregunta Josh. Gracias por el A2A. Usted plantea una pregunta de que todos los que han dado un paso adelante y se enfrentaron a los desafíos involucrados con aprender a codificar, y la recursividad es uno de esos desafíos. Es un concepto difícil de entender al principio. Dicho esto, felicidades por perseverar hasta ahora. Si ha llegado hasta aquí, probablemente haya completado su primer año de codificación académica, o su primer libro sobre conceptos de programación orientada a objetos. Ahora que he dicho eso, el resto de la publicación voy a tratar de explicar la recursividad, en un momento eso abrirá tu mente (no puedes enseñarle nada a nadie, solo puedes ayudarlo a pensarlo de una manera que permítales comprenderlo).

PROGRAMACIÓN FUNCIONAL:

En la teoría de la programación, aprendemos que los lenguajes se pueden clasificar en paradigmas. Los idiomas, como las personas, exhiben ciertas características o estilos de sintaxis que nos permiten hacer estas clasificaciones. Estas características, cuando se ven y aplican en muchos idiomas, se convierten en el sello distintivo del paradigma y hacen que sea mucho más fácil aprender idiomas. Por ejemplo, se cree que las características distintivas en los lenguajes orientados a objetos son: orden de ejecución, asignación de variables e iteración . Lo anterior también se ha dicho como algo que dice: el orden de ejecución es crítico y el sello distintivo del paradigma imperativo.

Continuando, algunos idiomas se construyen exclusivamente a partir de la recursividad. Se dice que los lenguajes clasificados en el paradigma funcional tienen las características distintivas de: recursividad y variables de un solo valor. Un ejemplo de lenguaje funcional dominante sería ML.

RECURSIÓN VS. ITERACIÓN

La definición básica de una función recursiva es una función cuya entrada son los valores de su salida hasta que se alcanza un punto de detención definitivo . Si nunca se alcanza la condición de terminación (punto de detención), se produce la desafortunada aparición de recursión infinita. Como probablemente ya pueda imaginar, la recursividad es una generalización de la iteración. Con esto quiero decir que todo lo que se puede hacer con una iteración (bucles / ciclos) también se puede hacer con algún tipo de función recursiva.

Ahora que no sé cuál es el idioma que estás aprendiendo actualmente, tuve la impresión, según algunas de tus preguntas anteriores, de que es Java. Entonces, voy a codificar un conjunto de programas factoriales en Java, el primero es el producto recursivo, el segundo logrará el producto a través de la iteración pura.

FACTORIAL RECURSIVO:

/ *
* FactRecursive.java
* Creado para demostrar la recursividad frente a la iteración en una respuesta a
* una pregunta de Quora sobre recursividad.
* autor: GSWade
* /
import java.util.Scanner;

clase pública FactRecursive
{
public static void main (String [] args)
{
// NOTA: Para probar, se debe agregar un período a Systemin
Scanner scan = nuevo escáner (Systemin);
int theNth;

System.out.println (“Para calcular un factorial ingrese un número mayor que cero:”);

theNth = scan.nextInt ();
int thefact = 1;
int outfact = 0;

para (int j = 1; j <= theNth; j ++)
{
// pasa la salida (valor de retorno) como argumento
thefact = factfinder (thefact, j);
}
// imprime la respuesta
System.out.println (“El factorial de” + theNth + “es igual a:” + thefact);

System.exit (0);

}
Public static int factfinder (int infact, int nth)
{
volver de hecho * nth;
}
}

FACTORIAL ITERATIVO:

/ *
* CycledFact.java
* Creado para demostrar la recursividad frente a la iteración en una respuesta a
* una pregunta de Quora sobre recursividad.
* autor: GSWade
* /
import java.util.Scanner;

clase pública CycledFact {

public static void main (String [] args)
{
// parte 1: crear un objeto de escáner
// NOTA: Para probar este programa, agregue un punto a Systemin
// para producir Systemin
Scanner scan = nuevo escáner (Systemin);
int theNth;
System.out.println (“Para calcular un factorial ingrese un número mayor que cero:”);
theNth = scan.nextInt ();

/ *
* el hecho debe ser inicializado, por lo que el valor de 1 es más
* lógico
* /

int thefact = 1;

// permitir j = theNth para inicializar j.
/ *
* Como theNth es el valor inicial del conteo de bucles
* reducir (iterar inversamente) el recuento var
* /
para (int j = theNth; j> 0; j–)
{
/ *
* sobrecarga al operador con operando multiplicativo
* primer ciclo thefact = 1, entonces thefact = 1 * theNth
* segundo ciclo thefact = thefact * theNth y así sucesivamente
* /
el hecho * = j;
}

System.out.println (“El factorial de” + theNth + “es igual a:” + thefact);

System.exit (0);

}
}

Mirando y enumerando las principales diferencias entre los programas anteriores, obtenemos lo siguiente:

Programa Factorial Recursivo

Tiene 2 métodos en la clase, el método void main () y el método factfinder () . Uno de los argumentos ( entradas ) del método factfinder () se almacena en la variable entera thefact, que también es la variable que almacena el valor de retorno de la salida de factfinder ().

Programa Factorial Iterativo:

Al contrario que el programa Factorial recursivo, el programa iterativo solo tiene un método con su clase. Este algoritmo es mucho más rápido, aunque aún no se nota debido al increíble hardware disponible en la computadora portátil o de escritorio promedio, porque hay menos entrada / salida.

Ahora, para resolver sus problemas recursivos y diseñar funciones / métodos recursivos, debe responder al menos las siguientes preguntas,

1. ¿Cuál es la condición de terminación (punto de parada)?
2. ¿Cuáles son las limitaciones? Sugerencia: como ejemplo, observe los dos programas, aunque el mensaje le indica al usuario que no ingrese cero, ¿qué sucede si lo hace?
3. ¿Se puede alcanzar la condición de terminación?

Ahora de todo lo que dije, ¿qué más se puede hacer en una OOP para ayudar a ver a través de la bruma? ¿Qué tal codificar inicialmente el problema usando iteraciones, hasta que se logre un resultado preciso? luego emule el algoritmo dividiéndolo en pedazos en el diseño de su función / método recursivo. Hay muy pocos casos en los que la declaración anterior no lo ayudará al diseñar soluciones recursivas. Incluso si los algoritmos terminaron siendo muy diferentes, puede ver los errores de diseño recursivos a medida que crea y preguntarse: “¿Qué falta?”, Y desde allí realizar un diseño retrosintético sobre lo que falta.

¡Espero que esto ayude!

La recursión es definitivamente un concepto difícil de entender. Soy más una persona visual. Entonces, para mí, dibujar diagramas (como el que se muestra a continuación) me ayudó mucho cuando abordé por primera vez los problemas de recurrencia:

La imagen de arriba explica este código de ejemplo (que está en Java):

Programa de clase pública {
public static void main (cadena final [] args) {
int final n = 4;
System.out.println (n + “! =” + Factorial (n));
}
privado estático int factorial (final int n) {
si (n == 0)
retorno 1;
retorno n * factorial (n – 1);
}

Además, consulte esta explicación en stackoverflow: comprender la recursividad básica

Para responder específicamente a su pregunta (que está en Codebat, ¿verdad?), Primero la abordaría dibujando este diagrama. Quizás esto te ayude a entenderlo:

// Para el caso de prueba 463
//Primera llamada:
3+ sumDigits (463/10)
// Segunda llamada:
6 + sumDigits (46/10)
// Tercera convocatoria:
4 + sumDigits (4/10)
// Cuarta convocatoria:
sumDigits (0)
// Golpea el caso base y la función termina.

Este diagrama esencialmente se reduce a esto: 3 + 6 + 4 + 0 = 13 (la suma total de 463).

Espero que esto ayude!

Fuente para el primer diagrama / problema de muestra:

1) Jade Cheng – CSCI 2912 – Recursión

Pienso en la recursividad como la resolución de problemas dentro de otros problemas.

Un bucle es como un problema al lado de otro problema. Simplemente te abres camino a través de la lista de elementos.

Entonces, si necesita sumar una serie de números, el ciclo los trataría como una lista. Comenzaría con la lista 3456 y dado que ya está tratando cada elemento individual como una cosa atómica (3) (4) (5) (6), todo lo que tiene que hacer es trabajar con los elementos (3) + (4 ) + (5) + (6).

Sin embargo, si no sabe de antemano que cada uno de ellos es su propio número, entonces no puede modelarlo como una lista. Es solo 3456. Tienes que descubrir si hay un solo dígito dentro de ese número. Básicamente, si hay un número dentro de otro número.

Entonces acepta la cadena 3456 y corta un elemento de ella 345 (6) y verifica si es un número. Ahora tiene una nueva cadena 345. No necesita ninguna lógica nueva. Simplemente puede llamar a la misma operación en esa nueva cadena 34 (5). Ahora tienes 34. Alimenta eso en la misma función y tienes 3. Dado que 3 no se puede subdividir, has llegado a la caja terminal y has terminado de recurrir. Devuelve ((((((3) 4) 5) 6).

La recursión es necesaria cuando aún no tienes un mapa del territorio. Si necesita averiguar qué hay en un sistema de archivos, debe seguir abriendo carpetas hasta que se quede sin carpetas. Tal vez haya una carpeta en esa carpeta, tal vez más, pero cada carpeta tiene el mismo problema dentro del mismo problema.

La recursión se utiliza en muchos problemas que se resuelven mediante una estrategia de “divide y vencerás”. Por lo general, intenta pensar en un caso fácil para calcular lo que desea y luego reduce los casos más complejos a versiones más simples hasta que todos los casos sean fáciles.

Si está tratando de obtener la suma de los dígitos de un número de un dígito: eso es realmente simple.

Si el número tiene más de un dígito, puede dividir la división del problema en dos problemas más fáciles: la suma del último dígito (que está cubierto por el caso base anterior) y la suma del resto de los dígitos.

Usando Python, así es como lo haría …

def sumOfDigits (n):
si n <10:
volver n
más:
return sumOfDigits (n% 10) + sumOfDigits (n / 10)

Usted el caso es fácil (n <10), luego devolvemos la parte simple. Si el caso es más difícil, divida n en dos partes: el último dígito y todo lo demás. La suma de todos los dígitos es la suma de los dígitos para cada parte.

La mayoría de las personas aprenden a hacer esto con un ciclo while. En Python, se vería así:

def sumOfDigitsWhile (n):
total = 0
mientras n> 0:
total = total + (n% 10)
n = n / 10
retorno total

Sospecho que la recursión es una idea que la mayoría de las personas tiene dificultades para comprender inicialmente, porque la enseñanza deficiente dificulta la tarea. Muchas personas encuentran que el segundo programa es más fácil de entender, pero después de un tiempo verán cómo no es realmente tan bueno. Debe crear una segunda variable para contener el valor temporal de la suma de todos los dígitos, y eso parece un desperdicio.

A veces no siempre es obvio. Si te esfuerzas lo suficiente, encontrarás que eventualmente es un caso base.

Piensa en el problema. Si usa la recursión, supondría que hay un subproblema más pequeño. Que hay aqui

Si tiene algún número de N dígitos, entonces un problema menor sería un número de N – 1 dígito. ¿Cómo puedes reducir eso a N – 1?

Obviamente dividirías por 10.

El caso base sería cuando N es 0.

Para cada subproblema, ¿cómo resolvería ese subproblema?

Desea la suma de cada dígito. Lo bueno de la recursividad es que puede usar el resultado del subproblema más pequeño para calcular el más grande. Puede usar la soultion de N = 1 para calcular N = 2 para el mismo número. Aquí es donde la ‘referencia en sí misma’ es importante. Lo que obtienes es que la solución que tienes se muestra en tu publicación.