¿Recursos para mejorar su comprensión de la recursión? [cerrado]

13

Sé lo que es la recursión (cuando un parche vuelve a aparecer dentro de sí mismo, típicamente una función que se llama a sí misma en una de sus líneas, después de una ruptura condicional ... ¿no?), y puedo entender las funciones recursivas si las estudio detenidamente . Mi problema es que, cuando veo nuevos ejemplos, al principio siempre estoy confundido. Si veo un bucle, un mapeo, compresión, anidación, llamadas polimórficas, etc., sé lo que está sucediendo con solo mirarlo. Cuando veo un código recursivo, mi proceso de pensamiento suele ser 'wtf is this?' seguido de "oh, es recursivo", seguido de "supongo que debe funcionar, si dicen que sí".

Entonces, ¿tiene algún consejo / plan / recursos para desarrollar habilidades en esta área? La recursión es un concepto un tanto extraño, por lo que pienso que la forma de abordarlo puede ser igualmente extraña e inobjetiva.

    
pregunta Andrew M 11.03.2011 - 23:06

9 respuestas

10

Comience con algo simple y trace con lápiz y papel. Seriosuly. Un buen lugar para comenzar son los algoritmos de recorrido de árboles, ya que son mucho más fáciles de manejar utilizando la recursión que la iteración regular. No tiene que ser un ejemplo complicado, pero es algo simple y con el que puedes trabajar.

Sí, es extraño y, a veces, contraintuitivo, pero una vez que hace clic, una vez que dices "¡Eureka!" ¡Te preguntarás cómo no lo entendiste antes! ;) Sugerí árboles porque son (IMO) la estructura más fácil de entender en recursión, y es fácil trabajar con lápiz y papel. ;)

    
respondido por el FrustratedWithFormsDesigner 11.03.2011 - 23:22
5

Recomiendo Scheme, usando el libro The Little Lisper. Una vez que hayas terminado, entenderás la recursión, en el fondo. Casi garantizado.

    
respondido por el jcomeau_ictx 12.03.2011 - 02:16
4

Definitivamente sugiero SICP. Además, debe consultar los videos introductorios del curso aquí ; Son increíblemente alucinantes.

Otro camino, no tan estrictamente relacionado con la programación, es leer Gödel, Escher, Bach: una Eterna Trenza Dorada de Hofstadter. Una vez que lo superas, la recursión se verá tan natural como la aritmética. Además, estará convencido de que P = nP y que querrá construir máquinas pensantes, pero es un efecto secundario que es tan pequeño en comparación con los beneficios.

    
respondido por el cbrandolino 12.03.2011 - 09:29
2

Esencialmente, todo se reduce a la práctica ... Tome problemas generales (clasificación, búsqueda, problemas matemáticos, etc.) y vea si puede ver una forma en que esos problemas pueden resolverse si aplica una sola función varias veces. .

Por ejemplo, la ordenación rápida opera porque mueve el elemento en una lista en dos mitades y luego se aplica nuevamente a cada una de esas mitades. Cuando se produce la clasificación inicial, no le preocupa que las dos mitades se ordenen en ese punto. Más bien es tomar el elemento de pivote y colocar todos los elementos más pequeños que ese elemento en un lado y todos los elementos más grandes o iguales en el otro lado. ¿Tiene sentido cómo puede recurrirse a sí mismo en ese punto para ordenar las dos nuevas listas más pequeñas? Son listas también. Sólo más pequeño. Pero todavía tienen que ser ordenados.

El poder detrás de la recursión es la noción de dividir y conquistar. Divida un problema repetidamente en problemas más pequeños que son idénticos en su naturaleza pero simplemente más pequeños. Si hace eso lo suficiente, eventualmente llega a un punto donde la única pieza restante ya está resuelta, entonces simplemente trabaja para salir del circuito y el problema está resuelto. Estudie los ejemplos que mencionó hasta que los entienda . Puede tomar un tiempo pero eventualmente se volverá más fácil. ¡Luego trata de tomar otros problemas y haz una función recursiva para resolverlos! Buena suerte!

EDITAR: También debo agregar que un elemento clave para la recursión es la capacidad garantizada de la función para poder detenerse. Esto significa que el desglose del problema original debe reducirse continuamente y, finalmente, debe haber un punto de parada garantizado (un punto en el que el nuevo subproblema puede resolverse o ya resuelto).

    
respondido por el Kenneth 11.03.2011 - 23:24
2

Personalmente creo que tu mejor apuesta es a través de la práctica.

Aprendí recursión con LOGO. Podrías usar LISP. La recursión es natural en esos idiomas. De lo contrario, puede compararlo con el estudio de series y series matemáticas donde exprese lo que sigue basándose en lo que vino antes, es decir, u (n + 1) = f (u (n)), o series más complejas donde tiene múltiples variables y múltiples dependencias, por ejemplo u (n) = g (u (n-1), u (n-2), v (n), v (n-1)); v (n) = h (u (n-1), u (n-2), v (n), v (n-1)) ...

Así que mi sugerencia sería que encuentre "problemas" de recursión estándar simples (en su expresión) e intente implementarlos en el idioma que elija. La práctica te ayudará a aprender a pensar, leer y expresar esos "problemas". Tenga en cuenta que a menudo algunos de estos problemas se pueden expresar a través de la iteración, pero la recursión puede ser una forma más elegante de resolverlos. Uno de ellos es el cálculo de los números factoriales.

Los "problemas" gráficos que encuentro hacen que sea más fácil de ver. Así que busque los copos de Koch, Fibonacci, la curva del dragón y los fractales en general. Pero también mire el algoritmo de ordenación rápida ...

Es necesario bloquear algunos programas (bucles sin fin, uso tentativo de recursos infinitos) y condiciones de finalización inadecuadas (para obtener resultados inesperados) antes de que lo vea todo. E incluso cuando lo consigas, seguirás cometiendo esos errores, pero con menos frecuencia.

    
respondido por el asoundmove 11.03.2011 - 23:35
2

Estructura e interpretación de los programas informáticos

Es el el libro utilizado para el aprendizaje, no solo de recursión, sino de programación en general en varias universidades. Es uno de esos libros fundamentales que proporciona más información a medida que adquieres más experiencia y más la lees.

    
respondido por el dietbuddha 12.03.2011 - 09:19
0

Tanto como me gusta SICP y Gödel, Escher, Bach: una trenza dorada eterna , LISP de Touretzky : Una introducción amable a la computación simbólica También hace un buen trabajo introduciendo recursión.

El concepto básico es este: primero, debes saber cuándo finaliza tu función recursiva, para que pueda devolver un resultado. Luego, debe saber cómo tomar el caso sin terminar, y reducirlo a algo en lo que pueda recurrir. Para el ejemplo de factorial (N) tradicional, ha terminado cuando N & lt = = 1, y el caso no finalizado es N * factorial (N-1).

Para un ejemplo mucho más feo, hay función de Ackermann A (m, n).

A(0,n) = n+1.                                   This is the terminal case.
A(m,0) = A(m-1,1) if m > 0.                     This is a simple recursion.
A(m,n) = A(m-1, A(m, n-1)) if m > 0 and n > 0.  This one is ugly.
    
respondido por el John R. Strohm 16.04.2013 - 00:36
0

Sugiero jugar con algunos lenguajes funcionales de estilo ML como OCaml o Haskell. Encontré que la sintaxis de coincidencia de patrones realmente me ayudó a entender incluso las funciones recursivas relativamente complicadas, ciertamente mucho mejor que las declaraciones if y cond de Scheme. (Aprendí Haskell y Scheme al mismo tiempo.)

Aquí hay un ejemplo trivial para el contraste:

(define (fib n)
   (cond [(= n 0) 0]
         [(= n 1) 1]
         [else (+ (fib (- n 1)) (fib (- n 2)))]))

y con coincidencia de patrones:

fib 0 = 0
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

Este ejemplo realmente no hace justicia a la diferencia, nunca tuve problemas con ninguna de las dos versiones de la función. Es solo para ilustrar cómo se ven las dos opciones. Una vez que llegas a funciones mucho más complejas, usando cosas como listas y árboles, la diferencia se vuelve mucho más pronunciada.

Recomiendo especialmente a Haskell porque es un lenguaje simple con una sintaxis muy agradable. También hace que sea mucho más fácil trabajar con ideas más avanzadas como corecursion :

fibs = 0 : 1 : zipWith (+) fibs (drop 1 fibs)
fib n = fibs !! n

(No entenderás el código anterior hasta que juegues un poco con Haskell, pero puedes estar seguro de que es básicamente mágico: P.) Seguro que podrías hacer lo mismo con las transmisiones en Scheme, pero es mucho más natural en Haskell.

    
respondido por el Tikhon Jelvis 16.04.2013 - 00:57
0

Está agotado, pero si puedes encontrarlo, "Recursive Algorithms" de Richard Lorentz no es más que recursión. Cubre los conceptos básicos de recursión, así como algoritmos recursivos específicos.

Los ejemplos están en Pascal, pero no son tan grandes que la elección del idioma sea molesta.

    
respondido por el Wayne Conrad 16.04.2013 - 01:27

Lea otras preguntas en las etiquetas