¿Cómo debe abordar la recursión?

Question

Actualmente estoy estudiando la recursividad en la escuela, y tengo problemas para pensar en los métodos cuando hay muchas llamadas recursivas. Solo quiero preguntar cómo debería pensar en la recursión porque sé que rastrear las llamadas al método en cada paso será demasiado tedioso.

En lugar de seguir cada llamada recursiva, lo que cubrimos brevemente fue pensar en la recursión por inducción, pero el problema que tengo es ver cómo la inducción se puede aplicar a situaciones distintas de las matemáticas. Al igual que si hay un método que imprime de forma recursiva los números de la siguiente manera:

public void blah(int n) 
{ 
    for (int i = 0; i < n; i++) 
     blah(i); 
    System.out.print(n); 
} 

tengo problemas para pensar acerca de lo que imprime, y yo no puedo ver cómo la inducción podría ser relevante aquí (perdón por mi ignorancia si puede ser usado en todas partes).

Pero supongo que mi verdadera pregunta es cómo puede abordar la recursión sin tener que rastrear cada llamada a un solo método. ¿Es lo mejor que puedes hacer para ver el caso base y el tipo de trabajo al revés? (Pero incluso entonces creo que me confundo sobre lo que sucede).

Answer 1

cómo puede abordar la recursividad sin tener que rastrear cada llamada a un solo método?

Existen varias formas de "entender" los programas recursivos: una implica pensar en una llamada recursiva como una caja negra, y la otra requiere "reproducir" algunos casos y adivinar el patrón.

El primer método supone que el método recursivo ya está escrito y que hace algo conocido. Esto es útil cuando piensas en analizadores de descenso recursivos; no es tan bueno para los programas que producen salida (a diferencia de consumiendo entrada), como el suyo.

El segundo método es más aplicable a programas similares a su ejemplo. Jugar por los valores 0, 1, 2 y 3.

0 - 0 
1 - 0 1 
2 - 0 0 1 2 
3 - 0 0 1 0 0 1 2 3 

¿Notaste el patrón? La salida para N enumera las salidas para los artículos previos N-1 e imprime N al final. Una vez que piense que puede continuar el patrón, sabrá que comprende su programa recursivo.

Answer 2

se puede encontrar una buena explicación sobre el pensamiento de forma recursiva sobre here

Desde el enlace

• Escriba un prototipo de la función recursiva.

• Escriba un comentario que describa lo que hace la función.

• Determine la carcasa base (puede haber más de una), y su solución .

• Determine qué problema (o problemas) más pequeños debe resolver. Si lo hace más fácil para que usted siga, guardar las soluciones a los más pequeños
  problemas a variables locales (por ejemplo, pequeña en el ejemplo de suma()) .ASSUME la llamada recursiva funciona

• uso de las soluciones el problema más pequeño para resolver el problema más grande. (Si esto se hace INCORRECTAMENTE, las soluciones de los problemas más pequeños
  también se computarán incorrectamente, por lo tanto, la suposición en
  fallará el paso anterior).

Answer 3

Así es como pienso sobre la recursividad. Es bastante simple, en realidad.

• ¿Qué debo hacer para detenerlo? Esto se conoce como su caso base .
• ¿Qué hago si aún no he terminado?

Tomemos, por ejemplo, el problema recursivo clásico: F (n) = n !. 0! se define como 1, y cualquier otra cosa mayor que 0 se define como n * F (n-1)

En este ejemplo, cumplo mis dos condiciones: detengo cuando llego a 0 !, y multiplico lo que sea valor que tengo por el (n-1) valor th.

Otro enfoque que uso: si se puede hacer recursivamente, entonces se puede hacer de forma iterativa. Es decir, si puedo escribir un ciclo para realizar la misma tarea, entonces puedo escribir un método recursivo para realizar la tarea también. A menudo es más fácil pensar en ciertos problemas recursivamente (por ejemplo, Ackermann's Function), y otros iterativamente (por ejemplo, caminando por una lista vinculada).

Querrá utilizar la iteración donde más le convenga.

Answer 4

Su ejemplo muestra

0 0 1 0 0 1 2 0 0 1 0 0 1 2 3 4 

Si se llama con bla (4).

En general, cuando vuelvo a recurrir, me aseguro de manejar primero la caja base. Después de eso, manejar el estado de la recursión, entonces la lógica puede venir.

En este ejemplo, el control de caso base es i < n y ocurrirá primero en 0 < 0 que es falso y rompe el bucle for imprimir 0. Entonces la siguiente iteración a cabo se ejecutará, que era para ir de i = 0 to 1 < 1 que de nuevo imprime 0 después de llamar a i = 0 < 0. Luego, termina el ciclo y se imprime el 1. Entonces es 2s turno, lol. Y así sucesivamente hasta que cada número haya tenido su turno.

Answer 5

No estoy seguro exactamente cómo decirte que pienses en ello, pero creo que esto podría ayudarte a comprender cómo es el flujo. Te sientes bien después de codificarlo por un tiempo, pero mucha gente simplemente lo evita porque los hace sentir mal. Me disculpo porque no está codificado en Java, pero no se trata del código, sino de lo que imprime, así que ejecútelo en cualquier Linux box o cygwin.

perl -e 'sub foo {my $n =shift;my $depth=shift;print "\t"x$depth;print "blah($n)\n";for(my $i=0;$i<$n;$i++){foo($i,$depth+1)};print "\t"x$depth;print $n,"\n"};foo(shift);' 5 

Llamado con una arg 3 de esto es lo que parece:

blah(3) 
      blah(0) 
      0 
      blah(1) 
        blah(0) 
        0 
      1 
      blah(2) 
        blah(0) 
        0 
        blah(1) 
          blah(0) 
          0 
        1 
      2 
    3 

trato como si alguien más dice que visualizarlo en componentes más pequeños. ES DECIR. ¿Qué está haciendo la función además de la recursión?En este caso, la función está contando de 0 a algún número. Ahora factor en lo que hace la recursión. Para cada recuento comienza un nuevo recuento hasta el número que ha alcanzado. A menudo encuentro que ayuda a dividirlo en más de una función, de modo que lo que realmente hace es encapsulado y la recursión separada, pero esto hace que la recursión sea menos obvia.

Creo que también ayuda a usar problemas del mundo real, como atravesar una jerarquía de directorios u otra estructura de árbol.

Answer 6

Así que voy a ser el más contundente aquí, o obtendrás recursión o no y no hay absolutamente nada de malo en eso. Es solo una de esas cosas que separa a los programadores (sad but true according to Joel). Ahora, para explicar la recursividad como si usted tuviera cinco años, la tarea se vuelve un poco turbia. Imagine que tiene cuatro (4) manzanas y cada vez que le pido que las cuente tome una de sus manzanas y dármela. La primera vez que hablo contigo me dirás que tienes cuatro manzanas y me entregarás una. Ahora continuamos este proceso hasta que tenga cero manzanas, esto será análogo a lo que otros han llamado base case o exit statement que asegura que su función terminará.

Ahora, ya no tiene más de cinco años, si le pedí que pruebe que para todos los casos de N que esto funcionaría, ¿cómo lo haría? A esto es a lo que su profesor recurre cuando dice resolver un problema por inducción. Un ejemplo de cómo resolver por inducción sería el siguiente: Tengo seis latas de Mountain Dew en mi escritorio y estoy en el proceso de beber una de ellas. Digo "Wow, esta lata de Mountain Dew sabe como un arcoiris eléctrico". Yo usaría la inducción para decir que las otras cinco latas y, por extensión, todas las latas de Mountain Dew saben a arco iris eléctrico. Entonces, en el caso de recursión, demuestras que una función terminará y será correcta utilizando el mismo proceso.

Puede ayudar a resolver una instancia "trivial" del problema como blah(0) and blah(1) and blah(2), esto le mostrará que la solución tiende en la dirección que anticipa y que puede usar la inducción para decir que este proceso terminará cualquier entrada N.