algorithm - recursivas - Entendiendo la recursión

recursividad de cola ejemplos (20)

¿Cómo vacías un jarrón que contiene cinco flores?

Respuesta: si el jarrón no está vacío, saca una flor y luego vacía un jarrón que contiene cuatro flores.

¿Cómo vacías un jarrón que contiene cuatro flores?

Respuesta: si el jarrón no está vacío, saca una flor y luego vacía un jarrón que contiene tres flores.

¿Cómo vacías un jarrón que contiene tres flores?

Respuesta: si el jarrón no está vacío, saca una flor y luego vacía un jarrón que contiene dos flores.

¿Cómo vacías un jarrón que contiene dos flores?

Respuesta: si el jarrón no está vacío, saca una flor y luego vacía un jarrón que contiene una flor.

¿Cómo vacías un jarrón que contiene una flor?

Respuesta: si el jarrón no está vacío, saca una flor y luego vacía un jarrón que no contiene flores.

¿Cómo vacías un jarrón sin flores?

Respuesta: si el jarrón no está vacío, saca una flor, pero el jarrón está vacío, así que ya está.

Eso es repetitivo. Vamos a generalizarlo:

¿Cómo vacías un jarrón que contiene N flores?

Respuesta: si el jarrón no está vacío, saca una flor y luego vacía un jarrón que contiene N-1 flores.

Hmm, ¿podemos ver eso en código?

void emptyVase( int flowersInVase ) { if( flowersInVase > 0 ) { // take one flower and emptyVase( flowersInVase - 1 ) ; } else { // the vase is empty, nothing to do } }

Hmm, ¿no podríamos haberlo hecho en un bucle for?

Por qué, sí, la recursión se puede reemplazar con iteración, pero a menudo la recursión es más elegante.

Hablemos de árboles. En informática, un árbol es una estructura formada por nodos , donde cada nodo tiene un número de hijos que también son nodos, o nulos. Un árbol binario es un árbol hecho de nodos que tienen exactamente dos hijos, típicamente llamados "izquierda" y "derecha"; De nuevo los hijos pueden ser nodos, o nulos. Una raíz es un nodo que no es el hijo de ningún otro nodo.

Imagina que un nodo, además de sus hijos, tiene un valor, un número, e imagina que deseamos sumar todos los valores en algún árbol.

Para sumar el valor en cualquier nodo, agregaríamos el valor del propio nodo al valor de su hijo izquierdo, si lo hubiera, y el valor de su hijo derecho, si lo hubiera. Ahora recuerda que los hijos, si no son nulos, también son nodos.

Entonces, para sumar el hijo izquierdo, agregaríamos el valor del nodo hijo en sí mismo al valor de su hijo izquierdo, si lo hubiera, y el valor de su hijo derecho, si lo hubiera.

Entonces, para sumar el valor del hijo izquierdo izquierdo, agregaríamos el valor del nodo hijo en sí mismo al valor de su hijo izquierdo, si lo hubiera, y al valor de su hijo derecho, si lo hubiera.

Tal vez has anticipado a dónde voy con esto, y te gustaría ver algún código? DE ACUERDO:

struct node { node* left; node* right; int value; } ; int sumNode( node* root ) { // if there is no tree, its sum is zero if( root == null ) { return 0 ; } else { // there is a tree return root->value + sumNode( root->left ) + sumNode( root->right ) ; } }

Observe que, en lugar de probar explícitamente a los hijos para ver si son nulos o nodos, simplemente hacemos que la función recursiva devuelva cero para un nodo nulo.

Entonces, digamos que tenemos un árbol que se ve así (los números son valores, las barras inclinadas apuntan a los niños y @ significa que el puntero apunta a nulo):

5 / / 4 3 // // 2 1 @ @ // // @@ @@

Si llamamos a sumNode en la raíz (el nodo con valor 5), devolveremos:

return root->value + sumNode( root->left ) + sumNode( root->right ) ; return 5 + sumNode( node-with-value-4 ) + sumNode( node-with-value-3 ) ;

Vamos a ampliar que en su lugar. En cualquier lugar donde veamos sumNode, lo reemplazaremos con la expansión de la declaración de retorno:

sumNode( node-with-value-5); return root->value + sumNode( root->left ) + sumNode( root->right ) ; return 5 + sumNode( node-with-value-4 ) + sumNode( node-with-value-3 ) ; return 5 + 4 + sumNode( node-with-value-2 ) + sumNode( node-with-value-1 ) + sumNode( node-with-value-3 ) ; return 5 + 4 + 2 + sumNode(null ) + sumNode( null ) + sumNode( node-with-value-1 ) + sumNode( node-with-value-3 ) ; return 5 + 4 + 2 + 0 + 0 + sumNode( node-with-value-1 ) + sumNode( node-with-value-3 ) ; return 5 + 4 + 2 + 0 + 0 + 1 + sumNode(null ) + sumNode( null ) + sumNode( node-with-value-3 ) ; return 5 + 4 + 2 + 0 + 0 + 1 + 0 + 0 + sumNode( node-with-value-3 ) ; return 5 + 4 + 2 + 0 + 0 + 1 + 0 + 0 + 3 + sumNode(null ) + sumNode( null ) ; return 5 + 4 + 2 + 0 + 0 + 1 + 0 + 0 + 3 + 0 + 0 ; return 5 + 4 + 2 + 0 + 0 + 1 + 0 + 0 + 3 ; return 5 + 4 + 2 + 0 + 0 + 1 + 3 ; return 5 + 4 + 2 + 1 + 3 ; return 5 + 4 + 3 + 3 ; return 5 + 7 + 3 ; return 5 + 10 ; return 15 ;

¿Ahora vemos cómo conquistamos una estructura de profundidad arbitraria y "ramificación", considerándola como la aplicación repetida de una plantilla compuesta? Cada vez que a través de nuestra función sumNode, tratamos con un solo nodo, usando una rama singe if / then, y dos simples declaraciones de retorno que casi las escribieron, directamente de nuestra especificación.

How to sum a node: If a node is null its sum is zero otherwise its sum is its value plus the sum of its left child node plus the sum of its right child node

Ese es el poder de la recursión.

El ejemplo de jarrón de arriba es un ejemplo de recursión de la cola . Todo lo que significa la recursión de la cola es que en la función recursiva, si recurrimos (es decir, si volvemos a llamar a la función), eso fue lo último que hicimos.

El ejemplo del árbol no fue la cola recursiva, porque aunque lo último que hicimos fue recursar al niño correcto, antes de hacerlo recursamos al niño izquierdo.

De hecho, el orden en el que llamamos a los hijos y agregamos el valor del nodo actual no importó en absoluto, porque la adición es conmutativa.

Ahora veamos una operación donde el orden sí importa. Usaremos un árbol binario de nodos, pero esta vez el valor mantenido será un carácter, no un número.

Nuestro árbol tendrá una propiedad especial, que para cualquier nodo, su carácter viene después (en orden alfabético) del personaje que tiene su hijo izquierdo y antes (en orden alfabético) del personaje que tiene su hijo derecho.

Lo que queremos hacer es imprimir el árbol por orden alfabético. Eso es fácil de hacer, dada la propiedad especial del árbol. Simplemente imprimimos el niño izquierdo, luego el carácter del nodo, luego el niño derecho.

No solo queremos imprimir sin querer, así que le pasaremos algo a nuestra función para imprimir. Este será un objeto con una función de impresión (char); no tenemos que preocuparnos por cómo funciona, solo que cuando se llama imprimir, imprimirá algo, en algún lugar.

Veamos eso en código:

struct node { node* left; node* right; char value; } ; // don''t worry about this code class Printer { private ostream& out; Printer( ostream& o ) :out(o) {} void print( char c ) { out << c; } } // worry about this code int printNode( node* root, Printer& printer ) { // if there is no tree, do nothing if( root == null ) { return ; } else { // there is a tree printNode( root->left, printer ); printer.print( value ); printNode( root->right, printer ); } Printer printer( std::cout ) ; node* root = makeTree() ; // this function returns a tree, somehow printNode( root, printer );

Además del orden de operaciones que ahora importa, este ejemplo ilustra que podemos pasar cosas a una función recursiva. Lo único que tenemos que hacer es asegurarnos de que en cada llamada recursiva, continuamos transmitiéndolo. Pasamos un indicador de nodo y una impresora a la función, y en cada llamada recursiva, los pasamos "abajo".

Ahora si nuestro árbol se ve así:

k / / h n // // a j @ @ // // @@ i@ // @@

¿Qué imprimiremos?

From k, we go left to h, where we go left to a, where we go left to null, where we do nothing and so we return to a, where we print ''a'' and then go right to null, where we do nothing and so we return to a and are done, so we return to h, where we print ''h'' and then go right to j, where we go left to i, where we go left to null, where we do nothing and so we return to i, where we print ''i'' and then go right to null, where we do nothing and so we return to i and are done, so we return to j, where we print ''j'' and then go right to null, where we do nothing and so we return to j and are done, so we return to h and are done, so we return to k, where we print ''k'' and then go right to n where we go left to null, where we do nothing and so we return to n, where we print ''n'' and then go right to null, where we do nothing and so we return to n and are done, so we return to k and are done, so we return to the caller

Así que si solo miramos las líneas nos imprimimos:

we return to a, where we print ''a'' and then go right to we return to h, where we print ''h'' and then go right to we return to i, where we print ''i'' and then go right to we return to j, where we print ''j'' and then go right to we return to k, where we print ''k'' and then go right to we return to n, where we print ''n'' and then go right to

Vemos que imprimimos "ahijkn", que de hecho está en orden alfabético.

Conseguimos imprimir un árbol completo, en orden alfabético, solo al saber cómo imprimir un solo nodo en orden alfabético. Lo que era justo (porque nuestro árbol tenía la propiedad especial de ordenar valores a la izquierda de los valores alfabéticamente posteriores) saber imprimir el elemento secundario izquierdo antes de imprimir el valor del nodo, y t para imprimir el elemento secundario derecho después de imprimir el valor del nodo.

Y ese es el poder de la recursión: ser capaz de hacer cosas enteras al saber solo cómo hacer una parte del todo (y saber cuándo dejar de hacerlo).

Recordando que en la mayoría de los idiomas, operador || ("o") cortocircuitos cuando su primer operando es verdadero, la función recursiva general es:

void recurse() { doWeStop() || recurse(); }

Luc M comenta:

Por lo tanto, debe crear una insignia para este tipo de respuesta. ¡Felicidades!

Gracias, Luc! Pero, en realidad, porque edité esta respuesta más de cuatro veces (para agregar el último ejemplo, pero principalmente para corregir errores tipográficos y pulirlo, escribir en un pequeño teclado de netbook es difícil), no puedo obtener más puntos por ello. . Lo que de alguna manera me desalienta a poner tanto esfuerzo en futuras respuestas.

Vea mi comentario aquí sobre eso: https://stackoverflow.com/questions/128434/what-are-community-wiki-posts-in-stackoverflow/718699#718699

Estoy teniendo grandes problemas para entender la recursión en la escuela. Cuando el profesor habla de eso, parece que lo entiendo, pero tan pronto como lo pruebo por mi cuenta, me quema el cerebro por completo.

Intenté resolver Towers of Hanoi toda la noche y me dejé boquiabierto. Mi libro de texto tiene solo unas 30 páginas en recursión, por lo que no es demasiado útil. ¿Alguien sabe de libros o recursos que puedan ayudar a aclarar este tema?

¿Qué libro estás usando?

El libro de texto estándar sobre algoritmos que es realmente bueno es Cormen & Rivest. Mi experiencia es que enseña bastante bien la recursión.

La recursión es una de las partes más difíciles de entender de la programación, y aunque requiere instinto, puede aprenderse. Pero necesita una buena descripción, buenos ejemplos y buenas ilustraciones.

Además, 30 páginas en general son muchas, 30 páginas en un solo lenguaje de programación son confusas. No intente aprender la recursión en C o Java, antes de entender la recursión en general de un libro general.

Ay. Intenté descubrir las Torres de Hanoi el año pasado. Lo complicado de TOH es que no es un simple ejemplo de recursión: tiene recursiones anidadas que también cambian los roles de las torres en cada llamada. La única manera de entenderlo era, literalmente, visualizar el movimiento de los anillos en el ojo de mi mente y verbalizar lo que sería la llamada recursiva. Empezaría con un solo anillo, luego dos, luego tres. En realidad ordené el juego en internet. Me tomó tal vez dos o tres días romper mis cerebros para conseguirlo.

Creo que este método tan simple debería ayudarte a entender la recursión. El método se llamará a sí mismo hasta que cierta condición sea verdadera y luego regresará:

function writeNumbers( aNumber ){ write(aNumber); if( aNumber > 0 ){ writeNumbers( aNumber - 1 ); } else{ return; } }

Esta función imprimirá todos los números desde el primer número que lo alimentará hasta 0. Así:

writeNumbers( 10 ); //This wil write: 10 9 8 7 6 5 4 3 2 1 0 //and then stop because aNumber is no longer larger then 0

Lo que sucede de manera grave es que writeNumbers (10) escribirá 10 y luego llamará a writeNumbers (9) que escribirá 9 y luego a writeNumber (8) etc. Hasta que writeNumbers (1) escriba 1 y luego llame a writeNumbers (0) que escribirá 0 butt no llamará a writeNumbers (-1);

Este código es esencialmente el mismo que:

for(i=10; i>0; i--){ write(i); }

Entonces, ¿por qué usar la recursión podría preguntarse, si un bucle for hace esencialmente lo mismo? Bueno, en su mayoría usas recursión cuando deberías anidar para bucles, pero no sabrás qué tan profundo están anidados. Por ejemplo, al imprimir elementos de matrices anidadas:

Esta función podría tomar una matriz que podría estar anidada en 100 niveles, mientras que escribir un bucle for requeriría que lo anidara 100 veces:

for(i=0; i<nestedArray.length; i++){ if(typeof nestedArray[i] == ''Array''){ for(a=0; i<nestedArray[i].length; a++){ if(typeof nestedArray[i][a] == ''Array''){ for(b=0; b<nestedArray[i][a].length; b++){ //This would be enough for the nestedAaray we have now, but you would have //to nest the for loops even more if you would nest the array another level write( nestedArray[i][a][b] ); }//end for b }//endif typeod nestedArray[i][a] == ''Array'' else{ write( nestedArray[i][a] ); } }//end for a }//endif typeod nestedArray[i] == ''Array'' else{ write( nestedArray[i] ); } }//end for i

Como puedes ver el método recursivo es mucho mejor.

Cuando trabajo con soluciones recursivas, siempre trato de:

Establezca primero el caso base, es decir, cuando n = 1 en una solución a factorial
Trate de llegar a una regla general para todos los demás casos

También hay diferentes tipos de soluciones recursivas, existe el enfoque de dividir y vencer que es útil para los fractales y muchos otros.

También ayudaría si pudieras trabajar en problemas más simples primero solo para entenderlo. Algunos ejemplos están resolviendo el factorial y generando el número n de fibonacci.

Para referencias, recomiendo altamente Algorithms por Robert Sedgewick.

Espero que ayude. Buena suerte.

Ejemplo simple recursivo en Common Lisp :

MYMAP aplica una función a cada elemento en una lista.

1) una lista vacía no tiene ningún elemento, por lo que devolvemos la lista vacía - () y NIL ambos son la lista vacía.

2) aplique la función a la primera lista, llame a MYMAP para el resto de la lista (la llamada recursiva) y combine ambos resultados en una nueva lista.

(DEFUN MYMAP (FUNCTION LIST) (IF (NULL LIST) () (CONS (FUNCALL FUNCTION (FIRST LIST)) (MYMAP FUNCTION (REST LIST)))))

Veamos la ejecución trazada. Al entrar en una función, los argumentos se imprimen. Al SALIR de una función, se imprime el resultado. Para cada llamada recursiva, la salida se sangrará en el nivel.

Este ejemplo llama a la función SIN en cada número en una lista (1 2 3 4).

Este es nuestro resultado :

(0.841471 0.9092975 0.14112002 -0.75680256)

En realidad, utiliza la recursión para reducir la complejidad de su problema. Usted aplica la recursión hasta que alcanza un caso básico simple que puede resolverse fácilmente. Con esto podrás resolver el último paso recursivo. Y con esto, todos los otros pasos recursivos hasta su problema original.

Esto es más una queja que una pregunta. ¿Tienes una pregunta más específica sobre la recursión? Como la multiplicación, no es una cosa sobre la que la gente escriba mucho.

Hablando de multiplicación, piensa en esto.

Pregunta:

¿Qué es un * b?

Responder:

Si b es 1, es a. De lo contrario, es a + a * (b-1).

¿Qué es un * (b-1)? Vea la pregunta anterior para una manera de resolverlo.

Intentaré explicarlo con un ejemplo.

Tu sabes que n ¿medio? Si no: http://en.wikipedia.org/wiki/Factorial

3! = 1 * 2 * 3 = 6

aquí va un pseudocódigo

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

Así que intentémoslo:

factorial(3)

es n 0?

¡no!

así que profundizamos más con nuestra recursión:

3 * factorial(3-1)

3-1 = 2

es 2 == 0?

¡no!

¡Así que vamos más allá! 3 * 2 * factorial (2-1) 2-1 = 1

es 1 == 0?

¡no!

¡Así que vamos más allá! 3 * 2 * 1 * factorial (1-1) 1-1 = 0

es 0 == 0?

¡sí!

tenemos un caso trivial

entonces tenemos 3 * 2 * 1 * 1 = 6

espero que te hayan ayudado

La manera verdaderamente matemática de considerar la construcción de una función recursiva sería la siguiente:

1: Imagina que tienes una función que es correcta para f (n-1), compilación f tal que f (n) sea correcta. 2: Generación f, tal que f (1) es correcta.

Así es como puede probar que la función es correcta, matemáticamente, y se llama Induction . Es equivalente a tener diferentes casos base, o funciones más complicadas en múltiples variables). También es equivalente a imaginar que f (x) es correcta para todas las x

Ahora para un ejemplo "simple". Construye una función que pueda determinar si es posible tener una combinación de monedas de 5 centavos y 7 centavos para hacer x centavos. Por ejemplo, es posible tener 17 centavos por 2x5 + 1x7, pero es imposible tener 16 centavos.

Ahora imagine que tiene una función que le dice si es posible crear x centavos, siempre y cuando x <n. Llame a esta función can_create_coins_small. Debería ser bastante simple imaginar cómo hacer la función para n. Ahora construye tu función:

bool can_create_coins(int n) { if (n >= 7 && can_create_coins_small(n-7)) return true; else if (n >= 5 && can_create_coins_small(n-5)) return true; else return false; }

El truco aquí es darse cuenta de que el hecho de que can_create_coins funcione para n, significa que puede sustituir can_create_coins por can_create_coins_small, dando:

bool can_create_coins(int n) { if (n >= 7 && can_create_coins(n-7)) return true; else if (n >= 5 && can_create_coins(n-5)) return true; else return false; }

Una última cosa que hacer es tener un caso base para detener la recursión infinita. Tenga en cuenta que si está intentando crear 0 centavos, es posible que no tenga monedas. Añadiendo esta condición da:

bool can_create_coins(int n) { if (n == 0) return true; else if (n >= 7 && can_create_coins(n-7)) return true; else if (n >= 5 && can_create_coins(n-5)) return true; else return false; }

Se puede probar que esta función siempre regresará, usando un método llamado descenso infinito , pero eso no es necesario aquí. Puedes imaginar que f (n) solo llama a valores más bajos de n, y que eventualmente siempre llegará a 0.

Para usar esta información para resolver su problema de la Torre de Hanoi, creo que el truco es asumir que tiene una función para mover n-1 tabletas de a a b (para cualquier a / b), tratando de mover n tablas de a a b .

Los niños utilizan implícitamente la recursión, por ejemplo:

Viaje por carretera a Disney World

¿Ya llegamos? (No)
¿Ya llegamos? (Pronto)
¿Ya llegamos? (Casi ...)
¿Ya llegamos? (SHHHH)
¿Ya llegamos?(!!!!!)

En ese punto el niño se duerme ...

Esta función de cuenta atrás es un ejemplo simple:

function countdown() { return (arguments[0] > 0 ? ( console.log(arguments[0]),countdown(arguments[0] - 1)) : "done" ); } countdown(10);

La ley de Hofstadter aplicada a proyectos de software también es relevante.

La esencia del lenguaje humano es, según Chomsky, la capacidad de los cerebros finitos para producir lo que él considera que son gramáticas infinitas. Con esto él quiere decir no solo que no hay un límite superior en lo que podemos decir, sino que no hay un límite superior en el número de oraciones que tiene nuestro idioma, no hay un límite superior en el tamaño de una oración en particular. Chomsky ha afirmado que la herramienta fundamental que subyace a toda esta creatividad del lenguaje humano es la recurrencia: la capacidad de una frase para volver a aparecer dentro de otra frase del mismo tipo. Si digo "la casa del hermano de Juan", tengo un sustantivo, "casa", que aparece en una frase nominal, "casa del hermano", y esa frase nominal aparece en otra frase nominal, "la casa del hermano de Juan". Esto tiene mucho sentido, y es una propiedad interesante del lenguaje humano.

Referencias

Recursión y pensamiento humano

Para comprender la recursión, todo lo que tiene que hacer es mirar en la etiqueta de su botella de champú:

function repeat() { rinse(); lather(); repeat(); }

El problema con esto es que no hay condición de terminación, y la recursión se repetirá indefinidamente, o hasta que se quede sin champú o agua caliente (condiciones de terminación externas, similares a hacer estallar la pila).

Para explicar la recursión a un niño de seis años, primero explíquelo a un niño de cinco años y luego espere un año.

En realidad, este es un contraejemplo útil, porque su llamada recursiva debería ser más simple, no más difícil. Sería aún más difícil explicar la recursión a un niño de cinco años, y aunque podría detener la recursión en 0, no tiene una solución simple para explicar la recursión a un niño de cero años.

Para resolver un problema usando la recursión, primero divídalo en uno o más problemas más simples que pueda resolver de la misma manera, y luego, cuando el problema sea lo suficientemente simple como para resolverlo sin más recursiones, puede regresar a niveles más altos.

De hecho, esa fue una definición recursiva de cómo resolver un problema con recursión.

Recursion

El método A, llama al método A llama al método A. Finalmente, uno de estos métodos A no llamará y saldrá, pero es recursivo porque algo se llama a sí mismo.

Ejemplo de recursión donde quiero imprimir cada nombre de carpeta en el disco duro: (en c #)

public void PrintFolderNames(DirectoryInfo directory) { Console.WriteLine(directory.Name); DirectoryInfo[] children = directory.GetDirectories(); foreach(var child in children) { PrintFolderNames(child); // See we call ourself here... } }

Si quiere un libro que explique la recursión en términos sencillos, eche un vistazo a Gödel, Escher, Bach: Una trenza dorada eterna de Douglas Hofstadter, específicamente el Capítulo 5. Además de la recursión, hace un buen trabajo de explicación. una serie de conceptos complejos en informática y matemáticas de manera comprensible, con una explicación basada en otra. Si no has tenido mucha exposición a este tipo de conceptos antes, puede ser un libro bastante alucinante.

Tu cerebro explotó porque entró en una recursión infinita. Ese es un error común de principiante.

Lo creas o no, ya entiendes la recursión, solo estás siendo arrastrado por una metáfora común pero defectuosa para una función: una pequeña caja con cosas que entran y salen.

Piense en lugar de una tarea o un procedimiento, como "descubra más sobre la recursión en la red". Eso es recursivo y no tienes ningún problema con eso. Para completar esta tarea podría:

a) Read a Google''s result page for "recursion" b) Once you''ve read it, follow the first link on it and... a.1)Read that new page about recursion b.1)Once you''ve read it, follow the first link on it and... a.2)Read that new page about recursion b.2)Once you''ve read it, follow the first link on it and...

Como puede ver, ha estado haciendo cosas recursivas durante mucho tiempo sin ningún problema.

¿Por cuánto tiempo seguirías haciendo esa tarea? ¿Para siempre hasta que tu cerebro explote? Por supuesto que no, se detendrá en un punto determinado, siempre que crea que ha completado la tarea.

No es necesario que especifique esto cuando le pida que "descubra más sobre la recursión en la red", porque es un ser humano y puede inferirlo por sí mismo.

La computadora no puede inferir, por lo que debe incluir un final explícito: "descubra más sobre la recursión en la red, HASTA que lo entienda o haya leído un máximo de 10 páginas ".

También inferiste que deberías comenzar en la página de resultados de Google por "recursión", y de nuevo eso es algo que una computadora no puede hacer. La descripción completa de nuestra tarea recursiva también debe incluir un punto de inicio explícito:

"Obtenga más información sobre la recursión en la red, HASTA que lo entienda o haya leído un máximo de 10 páginas y comience en www.google.com/search?q=recursion "

Para asimilarlo todo, te sugiero que pruebes alguno de estos libros:

Common Lisp: Una introducción suave a la computación simbólica. Esta es la explicación no matemática más linda de la recursión.
El pequeño intrigante.

Una función recursiva es como un resorte que comprime un poco en cada llamada. En cada paso, pones un poco de información (contexto actual) en una pila. Cuando se llega al paso final, se libera el resorte, ¡y se recopilan todos los valores (contextos) a la vez!

No estoy seguro de que esta metáfora sea efectiva ... :-)

De todos modos, más allá de los ejemplos clásicos (factorial, que es el peor de los ejemplos, ya que es ineficiente y fácil de aplanar, Fibonacci, Hanoi ...) que son un poco artificiales (rara vez, si es que los uso, en casos de programación reales), es Es interesante ver dónde se usa realmente.

Un caso muy común es caminar un árbol (o una gráfica, pero los árboles son más comunes, en general).
Por ejemplo, una jerarquía de carpetas: para enumerar los archivos, se itera en ellos. Si encuentra un subdirectorio, la función que lista los archivos se llama a sí misma con la nueva carpeta como argumento. Al regresar de la lista de esta nueva carpeta (y sus subcarpetas), retoma su contexto, al siguiente archivo (o carpeta).
Otro caso concreto es cuando se dibuja una jerarquía de componentes GUI: es común tener contenedores, como paneles, para sostener componentes que también pueden ser paneles, o componentes compuestos, etc. La rutina de pintura llama recursivamente la función de pintura de cada componente, que Llama a la función de pintura de todos los componentes que contiene, etc.

No estoy seguro si soy muy claro, pero me gusta mostrar el uso de material didáctico en el mundo real, ya que fue algo con lo que me encontré en el pasado.

Una función recursiva es simplemente una función que se llama a sí misma tantas veces como sea necesario. Es útil si necesita procesar algo varias veces, pero no está seguro de cuántas veces realmente se requerirá. En cierto modo, podría pensar en una función recursiva como un tipo de bucle. Sin embargo, como un bucle, necesitarás especificar las condiciones para que el proceso se rompa, de lo contrario se volverá infinito.

http://javabat.com es un lugar divertido y emocionante para practicar la recursión. Sus ejemplos comienzan bastante ligeros y funcionan a través de extensos (si quieren llegar tan lejos). Nota: Su enfoque es aprender practicando. Aquí hay una función recursiva que escribí para simplemente reemplazar un bucle for.

El bucle for:

public printBar(length) { String holder = ""; for (int index = 0; i < length; i++) { holder += "*" } return holder; }

Aquí está la recursión para hacer lo mismo. (Observe que sobrecargamos el primer método para asegurarnos de que se usa como en el ejemplo anterior). También tenemos otro método para mantener nuestro índice (similar a la forma en que la declaración for lo hace por usted anteriormente). La función recursiva debe mantener su propio índice.

public String printBar(int Length) // Method, to call the recursive function { printBar(length, 0); } public String printBar(int length, int index) //Overloaded recursive method { // To get a better idea of how this works without a for loop // you can also replace this if/else with the for loop and // operationally, it should do the same thing. if (index >= length) return ""; else return "*" + printBar(length, index + 1); // Make recursive call }

Para hacer una historia corta, la recursión es una buena manera de escribir menos código. En el último printBar notamos que tenemos una sentencia if. SI se ha alcanzado nuestra condición, saldremos de la recursión y volveremos al método anterior, que regresa al método anterior, etc. Si envié una barra de impresión (8), obtendré ********. Espero que con un ejemplo de una función simple que haga lo mismo que un bucle for, tal vez esto ayude. Aunque puedes practicar esto más en Java Bat.

Piensa en una abeja obrera. Intenta hacer miel. Hace su trabajo y espera que otras abejas obreras hagan el resto de la miel. Y cuando el panal está lleno, se detiene.

Piénsalo como magia. Tiene una función que tiene el mismo nombre que la que intenta implementar y cuando le asigna el subproblema, la resuelve por usted y lo único que debe hacer es integrar la solución de su parte con la solución. te dio.

Por ejemplo, queremos calcular la longitud de una lista. Llamemos a nuestra función magical_length y a nuestro ayudante mágico con magical_length. Sabemos que si le damos a la sublista que no tiene el primer elemento, nos dará la longitud de la sublista por la magia. Entonces, lo único que debemos pensar es cómo integrar esta información con nuestro trabajo. La longitud del primer elemento es 1 y magic_counter nos da la longitud de la sub-lista n-1, por lo que la longitud total es (n-1) + 1 -> n

int magical_length( list ) sublist = rest_of_the_list( list ) sublist_length = magical_length( sublist ) // you can think this function as magical and given to you return 1 + sublist_length

Sin embargo, esta respuesta es incompleta porque no consideramos qué sucede si damos una lista vacía. Pensamos que la lista que tenemos siempre tiene al menos un elemento. Por lo tanto, debemos pensar cuál debería ser la respuesta si se nos da una lista vacía y la respuesta es obviamente 0. Entonces, agregue esta información a nuestra función y esto se denomina condición base / borde.

int magical_length( list ) if ( list is empty) then return 0 else sublist_length = magical_length( sublist ) // you can think this function as magical and given to you return 1 + sublist_length