algorithm - recursivos - Dominar la programación recursiva

recursividad matematica ejemplos

Question

Tengo problemas para pensar / resolver el problema en términos de recursión. Realmente aprecio el concepto y puedo entenderlos como crear casos base, casos de salida y llamadas recursivas, etc. Puedo resolver problemas simples como escribir factoriales o la suma de enteros en una matriz. Ahí es donde mi pensamiento se detiene. Realmente no podría aplicar los conceptos o encontrar soluciones cuando el problema se complica. Por ejemplo, la torre de Hanoi, aunque puedo entender el problema y la solución, yo solo no puedo encontrar una solución. Se aplica a otros algoritmos, como la clasificación rápida / cruce de árbol binario también. Entonces mi pregunta es

1. ¿Cuál es la mejor manera de dominarlo?
2. ¿Alguien puede sugerir una lista de problemas o preguntas, que puedo usar como ejercicio para practicarlo?
3. ¿El aprendizaje del lenguaje funcional me ayudará con mi comprensión?

Por favor aconséjame.

Answer 1

Estudiar un lenguaje funcional ciertamente te ayudaría a pensar en la recursión. Recomendaría Haskell o Lisp (o Clojure). Lo bueno es que no es necesario llegar a los "bits duros" de ninguno de estos idiomas antes de llegar a la recursión. Para aprender acerca de la recursión, no tiene que aprender lo suficiente de ninguno de estos idiomas para hacer una programación "real".

La sintaxis de concordancia de patrones de Haskell significa que los casos base son fáciles de ver. En Haskell, Factorial se ve así:

factorial 0 = 1
factorial n = n * factorial (n - 1)

... que es exactamente equivalente a un lenguaje de procedimiento:

int factorial(n) {
    if(n==0) {
         return 1;
    } else {
         return n * factorial(n-1)
    }
}

... pero con menos sintaxis para oscurecer el concepto.

Para completar, aquí está el mismo algoritmo en Lisp:

(defun factorial (n)
   (if (== n 0)
       1
       (* n (factorial (- n 1)))))

Lo que debería poder ver es equivalente, aunque al principio todos los paréntesis tienden a oscurecer la opinión de la gente sobre lo que está sucediendo. Aún así, un libro Lisp cubrirá muchas técnicas recursivas.

Además, cualquier libro sobre un lenguaje funcional le dará muchos ejemplos de recursión. Comenzarás con algoritmos que funcionan con listas:

 addone [] = []
 addone (head:tail) = head + 1 : addone tail

.. que usa un patrón muy común con una llamada recursiva por función. (En realidad, un patrón tan común que casi todos los idiomas lo resumen en una función de biblioteca llamada map )

Luego pasará a las funciones que atraviesan árboles, haciendo una llamada recursiva para cada rama desde un nodo.

En términos más generales, piense en problemas como este:

"¿Puedo resolver una pequeña parte de este problema y dejarme con el mismo problema, solo que más pequeño?".

... o ...

"¿Este problema sería fácil de resolver, si solo el resto ya estuviera resuelto?".

Entonces, por ejemplo, factorial(n) es simple de resolver si conoce factorial(n-1) , lo que sugiere una solución recursiva.

Resulta que se pueden pensar muchos problemas de esa manera:

"Clasificar una lista de 1000 artículos parece difícil, pero si selecciono un número al azar, clasifico todos los números más pequeños que eso, luego selecciono todos los números más grandes que eso, he terminado". (Eventualmente se trata de ordenar listas de longitud 1)

...

"Calcular el camino más corto a un nodo es difícil, pero si pudiera conocer la distancia hasta allí desde cada uno de mis nodos adyacentes, sería fácil".

...

"Visitar todos los archivos de este árbol de directorios es difícil, pero puedo ver los archivos en el directorio base y los subdirectorios de amenazas de la misma manera".

Del mismo modo la Torre de Hanoi. La solución es fácil si lo dice así:

 To move a stack from a to c:
  If the stack is of size 1
      just move it.
  otherwise
      Move the stack minus its largest ring, to b (n-1 problem)
      Move the largest ring to c (easy)
      Move the stack on b to c (n-1 problem)

Hemos hecho que el problema parezca fácil al esbozar dos pasos aparentemente difíciles. Pero esos pasos son el mismo problema nuevamente, pero "uno más pequeño".

Puede resultarle útil pasar manualmente a través de un algoritmo recursivo utilizando trozos de papel para representar la pila de llamadas, como se describe en esta respuesta: Descripción del desenrollado de la pila en la recursión (recorrido del árbol)

Después de que se haya sentido más cómodo con la recursión, vuelva al pasado y piense si es la solución adecuada para un caso en particular. Aunque factorial() es una buena forma de demostrar el concepto de recursión, en la mayoría de los lenguajes una solución iterativa es más eficiente. Conozca la optimización de la recursividad de la cola , qué idiomas lo incluyen y por qué.

Answer 2

La recursión es una forma conveniente de implementar el paradigma Divide & Conquer: cuando necesitas resolver un problema dado, un enfoque poderoso es dividirlo en problemas de la misma naturaleza , pero con un tamaño más pequeño . Al repetir este proceso, terminará trabajando en problemas tan pequeños que pueden resolverse fácilmente por otro método.

La pregunta que debes hacerte es "¿puedo resolver este problema resolviendo partes de él?". Cuando la respuesta es positiva, aplica este esquema conocido:

• dividir el problema en subproblemas recursivamente, hasta que el tamaño sea pequeño,

• resolver los subproblemas por un método directo,

• fusionar las soluciones en el orden inverso.

Tenga en cuenta que la división se puede hacer en dos partes o más, y estas pueden equilibrarse o no.

Por ejemplo: ¿puedo ordenar una matriz de números realizando géneros parciales?

Respuesta 1: sí, si dejo el último elemento y clasifico el resto, puedo ordenar todo el conjunto insertando el último elemento en el lugar correcto. Este es un tipo de inserción.

Respuesta 2: sí, si encuentro el elemento más grande y lo muevo hasta el final, puedo ordenar todo el conjunto ordenando los elementos restantes. Este es un tipo de selección.

Respuesta 3: sí, si clasifico dos mitades de la matriz, puedo ordenar la matriz completa fusionando las dos secuencias, usando una matriz auxiliar para los movimientos. Esto es tipo de fusión.

Respuesta 4: sí, si participo la matriz usando un pivote, puedo ordenar toda la matriz ordenando las dos partes. Este es un tipo rápido.

En todos estos casos, resuelve el problema resolviendo subproblemas de la misma naturaleza y agregando algo de pegamento.

Answer 3

La recursividad es solo una forma de pensar, igual que iterativa. Cuando éramos niños en la escuela, no nos enseñaron a pensar recursivamente y ahí radica el problema real. Debes incorporar esa manera de pensar en tu arsenal, una vez que lo hagas, permanecerá allí para siempre.

La mejor manera de dominar:

Me pareció útil descubrir siempre los casos base primero, tal vez al principio no sean los más simples, pero una vez que comienzas a construir la recursividad sobre ese caso base, te darás cuenta de que puedes simplificarlo. La importancia de identificar el caso base es que primero se enfoca en lo que debe resolverse en su forma más simple (los casos más simples) y esto de alguna manera dibuja una hoja de ruta para el algoritmo futuro; segundo, se asegura de que el algoritmo se detenga . Tal vez no devuelva el resultado esperado, pero al menos se detiene, lo que siempre es alentador.

Además, siempre ayuda a determinar cómo una pequeña instancia de un problema lo ayudará a encontrar la solución de una instancia más grande del problema. Esto es, por ejemplo, cómo se puede construir la solución para la entrada n que ya tiene la solución de la entrada n-1 .

Resuelve todos los problemas que puedas pensar recursivamente . Sí, Hanoi Towers no es un buen ejemplo, sus soluciones recursivas son una solución muy inteligente . Intenta problemas más fáciles, problemas casi elementales.

Lista de problemas

1. Operaciones matemáticas: exponenciación y cada operación matemática que se te ocurra.
2. Manejo de cuerdas: Palindrome es un muy buen ejercicio. Encontrar palabras en una grilla también es útil.
3. Aprenda sobre las estructuras de datos de árbol: Esto en particular es IMO el mejor entrenamiento. Los árboles son estructuras de datos recursivas. Aprenda sobre sus recorridos (inorder, postorder, preorder, calcule su altura, su diámetro, etc.). Casi todas las operaciones en una estructura de datos similar a un árbol es un gran ejercicio.
4. Problemas combinatorios: muy importantes, combinaciones, permutaciones, etc.
5. Búsqueda de ruta: algoritmo de Lee, algoritmos de laberinto, etc.

Pero lo más importante es comenzar con problemas simples . Casi todos los problemas tienen una solución recursiva. Los problemas de matemáticas son geniales para entenderlo. Cada vez que vea un bucle for o un bucle while, convierta ese algoritmo en recursión.

Lenguaje de programación

La programación funcional depende en gran medida de la recursión. No creo que eso sirva de mucho ya que son intrínsecamente recursivos y pueden ser engorrosos para los usuarios que aún no entienden mucho la recursividad.

Use un lenguaje de programación simple, aquel con el que esté más familiarizado, preferiblemente uno que no ocupe demasiado su mente con molestias y punteros de memoria. Python es un muy buen comienzo en mi opinión. Es muy simple, no te molesta con tipeo o estructuras de datos complicadas. Siempre que el idioma te ayude a mantenerte enfocado solo en la recursión, será mejor.

Un último consejo, si no puede encontrar una solución a un problema, búsquelo en Internet o solicite ayuda, entienda lo que hace completamente y continúe con el otro. No dejes que te eludan, porque lo que estás tratando de hacer es incorporar esa forma de pensar a tu cabeza .

Para dominar la recursión , necesitas primero la recursión maestra :)

¡Espero que esto ayude!

Answer 4

Mi consejo: confíe en que la función recursiva "hace el trabajo" , es decir, cumple con sus especificaciones. Y sabiendo eso, puede crear una función que resuelva un problema mayor sin dejar de cumplir la especificación.

¿Cómo resuelves el problema de las torres de Hanoi? Supongamos que hay una función Hanoi (N) capaz de mover una pila de N discos sin infringir las reglas. Usando esta función, implementa fácilmente Hanoi ''(N + 1): realice Hanoi (N), mueva el siguiente disco y realice Hanoi (N) nuevamente.

Si Hanoi (N) funciona, entonces Hanoi ''(N + 1) también funciona, sin infringir las reglas. Para completar el argumento, debe asegurarse de que las llamadas recursivas terminen. En este caso, si puede resolver Hanoi (1) de forma no recursiva (lo cual es trivial), ya ha terminado.

Usando este enfoque, no tiene que preocuparse por cómo ocurrirán las cosas en realidad, se le garantiza que funciona. (Siempre que pase a instancias cada vez más pequeñas del problema).

Otro ejemplo: recorrido recursivo de un árbol binario. Asuma que la función Visit(root) hace el trabajo. Luego, if left -> Visit(left); if right -> Visit(right); print root if left -> Visit(left); if right -> Visit(right); print root if left -> Visit(left); if right -> Visit(right); print root hará el trabajo! Porque la primera llamada imprimirá el subárbol izquierdo (no se preocupe por cómo) y el segundo el subárbol derecho (no se preocupe por cómo), y también se imprimirá la raíz.

En este último caso, la terminación está garantizada por el hecho de que procesa subárboles cada vez más pequeños, hasta las hojas.

Otro ejemplo: Quicksort. Supongamos que tiene una función que ordena una matriz en el lugar, deje Quicksort. Lo usará de la siguiente manera: mueva los elementos pequeños antes que los elementos grandes, in situ, comparándolos con un valor de "pivote" bien elegido (en realidad, cualquier valor de la matriz puede hacerlo). Luego, clasifique los elementos pequeños por medio de la función Quicksort, y los elementos grandes de la misma manera, ¡y listo! No es necesario preguntarse la secuencia exacta de las particiones que tendrán lugar. La terminación está garantizada si evita subcampos vacíos.

Último ejemplo, el triángulo de Pascal. Usted sabe que un elemento es la suma de los dos superiores, con 1 en los lados. Entonces con los ojos cerrados, C(K, N)= 1 if K=0 or K=N, else C(K, N) = C(K-1, N-1) + C(K, N-1) . Eso es !

Answer 5

Para problemas complejos, le sugiero que haga el problema para tamaños de problema pequeños y vea qué tipos de patrones encuentra. Por ejemplo, en Towers of Hanoi, comienza con un tamaño de problema de uno, luego dos, luego tres, etc. En algún punto, probablemente comiences a ver un patrón, y te darás cuenta de que algo de lo que estás teniendo hacer es como lo que tenía que hacer en los problemas de menor tamaño, o que es lo suficientemente similar como para que pueda usar la misma técnica que antes pero con alguna variación.

Acabo de pasar por el problema de Towers of Hanoi y estudié mis propios pensamientos. Empecé con un problema de tamaño uno:

We have one disk on peg A. *** Move it to peg C. Done!

Ahora para dos.

We have two disks on peg A. I need to use peg B to get the first disk out of the way. *** Move from peg A to peg B Now I can do the rest *** Move from peg A to peg C *** Move from peg B to peg C Done!

Ahora para tres.

Las cosas comienzan a ponerse un poco más interesantes. La solución no es tan obvia. Sin embargo, he descubierto cómo mover dos discos de una clavija a otra, así que si pudiera mover dos discos de la clavija A a la clavija B, mueva un disco de la clavija A a la clavija C, y luego dos discos de la clavija B para fijar C, ¡estaría hecho! Mi lógica para el caso de dos discos funcionará, excepto que las clavijas son diferentes. Si ponemos la lógica en una función y hacemos parámetros para las clavijas, entonces podemos reutilizar la lógica.

def move2(from_peg,to_peg,other_peg):
   # We have two disks on from_peg
   # We need to use other_peg to get the first disk out of the way
   print ''Move from peg ''+from_peg+'' to peg ''+other_peg
   # Now I can do the rest
   print ''Move from peg ''+from_peg+'' to peg ''+to_peg
   print ''Move from peg ''+other_peg+'' to peg ''+to_peg

La lógica es entonces:

move2(''A'',''B'',''C'') print ''Move from peg A to peg C'' move2(''B'',''C'',''A'')

Puedo simplificar esto teniendo también una función move1:

def move1(from_peg,to_peg):
    print ''Move from ''+from_peg+'' to ''+to_peg

Ahora mi función move2 puede ser

def move2(from_peg,to_peg,other_peg):
   # We have two disks on from_peg
   # We need to use other_peg to get the first disk out of the way
   move1(from_peg,other_peg,to_peg)
   # Now I can do the rest
   move1(from_peg,to_peg)
   move1(other_peg,to_peg)

Ok, ¿qué tal cuatro?

Parece que puedo aplicar la misma lógica. Necesito sacar tres discos de la clavija A a la clavija B, luego de la A a la C, luego de la B a la C. Ya resolví mover tres, pero con las clavijas equivocadas, así que lo generalizaré:

def move3(from_peg,to_peg,other_peg):
   move2(from_peg,other_peg,to_peg)
   move1(from_peg,to_peg)
   move2(other_peg,to_peg,from_peg)

¡Guay! Y espera, move3 y move2 son bastante similares ahora, y eso tiene sentido. Para cualquier problema de tamaño podemos mover todos menos uno de los discos a la clavija B, luego mover un disco de A a C, luego mover todos los discos de la clavija B a la clavija C. Entonces nuestra función de movimiento puede tomar la cantidad de discos como un parámetro:

def move(n,from_peg,to_peg,other_peg):
    move(n-1,from_peg,other_peg,to_peg)
    move1(from_peg,to_peg)
    move(n-1,other_peg,to_peg,from_peg)

Esto se ve muy cerca, pero no funciona en el caso donde n == 1 porque terminamos llamando a move (0, ...). Entonces tenemos que manejar eso:

def move(n,from_peg,to_peg,other_peg):
    if n==1:
        move1(from_peg,to_peg)
    else:
        move(n-1,from_peg,other_peg,to_peg)
        move1(from_peg,to_peg)
        move(n-1,other_peg,to_peg,from_peg)

¡Excelente! ¿Qué tal un tamaño de problema de cinco? Simplemente llamamos mover (5, ''A'', ''C'', ''B''). Parece que cualquier tamaño de problema es lo mismo, por lo que nuestra función principal es simplemente:

def towers(n):
    move(n,''A'',''C'',''B'')

y hemos terminado!

Answer 6

la recursividad es difícil porque es una forma diferente de pensar, una que nunca nos presentaron cuando éramos más jóvenes.

de lo que dices que ya tienes el concepto, todo lo que realmente necesitas es solo practicarlo más. un lenguaje funcional definitivamente ayudaría; Te verás obligado a pensar en tus problemas recursivamente y, antes de que te des cuenta, la recursividad te parecerá muy natural

hay toneladas de ejercicios que puede hacer en relación con la recursión, tenga en cuenta que todo lo que se hace con un ciclo se puede hacer recursivamente también.

vea esta answer para obtener detalles acerca de las referencias y los probelmas del ejercicio