Comprensión de la recursión [cerrada]

Tengo grandes problemas para entender la recursividad en la escuela. Cada vez que el profesor está hablando de eso, parece que lo entiendo, pero tan pronto como lo intento por mi cuenta, me deja sin aliento.

Intenté resolver Towers of Hanoi toda la noche y me voló la cabeza por completo. 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?

¿Cómo se vacía un florero que contiene cinco flores?

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

¿Cómo se vacía un florero 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 se vacía un florero que contiene tres flores?

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

¿Cómo se vacía 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 se vacía un florero 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 se vacía un florero que no contiene 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 se vacía un florero que contiene N flores?

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

Hmm, ¿podemos ver eso en el 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 haber hecho eso 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 compuesta de 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"; nuevamente los hijos pueden ser nodos o nulos. Una raíz es un nodo que no es hijo de ningún otro nodo.

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

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

Por lo tanto, para sumar el elemento secundario izquierdo, agregaríamos el valor del nodo secundario en sí al valor de su elemento secundario izquierdo, si lo hay, y el valor de su elemento secundario derecho, si lo hay.

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

¿Quizás has anticipado a dónde voy con esto, y te gustaría ver algún código? OKAY:

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.

Supongamos que tenemos un árbol que se ve así (los números son valores, las barras apuntan a elementos secundarios y @ significa que el puntero apunta a nulo):

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

Si llamamos 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 ) ;

Expandamos eso en su lugar. Dondequiera que veamos sumNode, lo reemplazaremos con la expansión de la declaración de devolución:

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 vea cómo conquistamos una estructura de profundidad arbitraria y "ramificación", al considerarla como la aplicación repetida de una plantilla compuesta. cada vez a través de nuestra función sumNode, tratamos con un solo nodo, usando una sola rama if / then, y dos declaraciones de retorno simples que casi escribieron las mismas, directamente desde 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 recursividad.

El ejemplo de florero anterior es un ejemplo de recursión de cola . Todo lo que significa la recursividad de cola es que en la función recursiva, si recurrimos (es decir, si llamamos a la función nuevamente), eso fue lo último que hicimos.

El ejemplo del árbol no fue recursivo de la cola, porque a pesar de que lo último que hicimos fue recurrir al niño correcto, antes de hacerlo, recurrimos 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 suma es conmutativa.

Ahora veamos una operación donde el orden sí importa. Usaremos un árbol binario de nodos, pero esta vez el valor contenido 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 en orden alfabético. Eso es fácil de hacer, dada la propiedad especial del árbol. Simplemente imprimimos el elemento secundario izquierdo, luego el carácter del nodo, luego el elemento secundario derecho.

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

Veamos eso en el 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, continuemos transmitiéndola. Pasamos un puntero 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

Entonces, si solo miramos las líneas donde 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.

Logramos imprimir un árbol completo, en orden alfabético, simplemente sabiendo cómo imprimir un solo nodo en orden alfabético. Lo cual era justo (porque nuestro árbol tenía la propiedad especial de ordenar los valores a la izquierda de los valores alfabéticamente posteriores) sabiendo imprimir el hijo izquierdo antes de imprimir el valor del nodo, e imprimir el hijo derecho después de imprimir el valor del nodo.

Y ese es el poder de la recursividad: ser capaz de hacer cosas enteras sabiendo solo cómo hacer una parte de la totalidad (y saber cuándo dejar de recurrir).

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:

SO debería 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, es difícil escribir en un pequeño teclado de netbook), no puedo obtener más puntos por ello . Lo que me desalienta un poco de poner tanto esfuerzo en futuras respuestas.

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

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 hacia abajo 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 procedimiento, como "descubra más sobre la recursividad en la red". Eso es recursivo y no tienes ningún problema. Para completar esta tarea, puede:

a) Lea la página de resultados de Google para "recursión"
b) Una vez que lo hayas leído, sigue el primer enlace y ...
a.1) Lea esa nueva página sobre recursividad 
b.1) Una vez que lo haya leído, siga el primer enlace y ...
a.2) Lea esa nueva página sobre recursividad 
b.2) Una vez que lo haya leído, siga el primer enlace y ...

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

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

No es necesario especificar esto cuando le pida que "descubra más sobre la recursividad en la red", porque usted es un ser humano y puede inferirlo usted mismo.

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

También dedujo que debe comenzar en la página de resultados de Google para "recurrencia", y nuevamente eso es algo que una computadora no puede hacer. La descripción completa de nuestra tarea recursiva también debe incluir un punto de partida explícito:

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

Para entenderlo todo, le sugiero que pruebe cualquiera de estos libros:

• Lisp común: una suave introducción a la computación simbólica. Esta es la explicación no matemática más linda de la recursividad.
• El pequeño intrigante.

Para comprender la recursividad, todo lo que tiene que hacer es mirar la etiqueta de su botella de champú:

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

El problema con esto es que no hay una 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 volar su pila).

Si desea un libro que explique bien la recursividad en términos simples, eche un vistazo a Gödel, Escher, Bach: An Eternal Golden Braid de Douglas Hofstadter, específicamente el Capítulo 5. Además de la recursión, hace un buen trabajo al explicar Una serie de conceptos complejos en informática y matemáticas de una manera comprensible, con una explicación basada en otra. Si no ha tenido mucha exposición a este tipo de conceptos antes, puede ser un libro bastante alucinante.

Esto es más una queja que una pregunta. ¿Tienes una pregunta más específica sobre la recursividad? Al igual que la multiplicación, no es algo sobre lo que la gente escribe mucho.

Hablando de multiplicación, piense en esto.

Pregunta:

¿Qué es a * b?

Responder:

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

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

Creo que este método muy simple debería ayudarlo a comprender la recursividad. El método se llamará a sí mismo hasta que cierta condición sea verdadera y luego devolverá:

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

Esta función imprimirá todos los números del primer número que lo alimentará hasta 0. Por lo tanto:

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 ocurre en el bajo es que writeNumbers (10) escribirá 10 y luego llamará a writeNumbers (9) que escribirá 9 y luego llamará 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 preguntar, si un ciclo for hace esencialmente lo mismo. Bueno, la mayoría de las veces usa la recursividad cuando tendría que anidar para bucles, pero no sabrá qué tan profundos están anidados. Por ejemplo, al imprimir elementos de matrices anidadas:

var nestedArray = Array('Im a string', 
                        Array('Im a string nested in an array', 'me too!'),
                        'Im a string again',
                        Array('More nesting!',
                              Array('nested even more!')
                              ),
                        'Im the last string');
function printArrayItems( stringOrArray ){
 if(typeof stringOrArray === 'Array'){
   for(i=0; i<stringOrArray.length; i++){ 
     printArrayItems( stringOrArray[i] );
   }
 }
 else{
   write( stringOrArray );
 }
}

printArrayItems( stringOrArray );
//this will write:
//'Im a string' 'Im a string nested in an array' 'me too' 'Im a string again'
//'More nesting' 'Nested even more' 'Im the last string'

Esta función podría tomar una matriz que podría anidarse en 100 niveles, mientras que escribir un bucle for requeriría anidarlo 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 puede ver, el método recursivo es mucho mejor.

En realidad, utiliza la recursividad para reducir la complejidad de su problema en cuestión. Aplica la recursividad hasta llegar a un caso base simple que se puede resolver fácilmente. Con esto puedes resolver el último paso recursivo. Y con esto, todos los demás pasos recursivos hasta su problema original.

Trataré de explicarlo con un ejemplo.

Sabes lo que n! ¿medio? Si no es así: 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))
}

Entonces probémoslo:

factorial(3)

es n 0?

¡No!

entonces profundizamos con nuestra recursividad:

3 * factorial(3-1)

3-1 = 2

es 2 == 0?

¡No!

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

es 1 == 0?

¡No!

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

es 0 == 0?

¡si!

tenemos un caso trivial

entonces tenemos 3 * 2 * 1 * 1 = 6

espero que te haya ayudado

Recursividad

Método A, llamadas Método A llamadas Método A. Eventualmente, uno de estos métodos A no llamará y saldrá, pero es una recursión 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...
    }
}

¿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 recursividad.

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

Además, 30 páginas en general es mucho, 30 páginas en un solo lenguaje de programación es confuso. No intente aprender la recursividad en C o Java, antes de comprender la recursividad en general de un libro general.

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 se necesitarán realmente. En cierto modo, podrías pensar en una función recursiva como un tipo de bucle. Sin embargo, como un bucle, deberá 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 son extensos (si quieres 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 recursividad para hacer lo mismo. (tenga en cuenta que sobrecargamos el primer método para asegurarnos de que se use como se indicó anteriormente). 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 resumir, la recursividad es una buena manera de escribir menos código. En el último aviso de printBar, tenemos una declaración 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 printBar (8), obtengo ********. Espero que con un ejemplo de una función simple que haga lo mismo que un bucle for, tal vez esto ayude. Sin embargo, puedes practicar esto más en Java Bat.

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

1: Imagine que tiene una función que es correcta para f (n-1), cree f de tal manera que f (n) sea correcta. 2: Construir f, de modo que f (1) sea correcto.

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

Ahora para un ejemplo "simple". Cree 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 imposible tener 16 centavos.

Ahora imagine que tiene una función que le indica si es posible crear x centavos, siempre que 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á tratando de crear 0 centavos, eso es posible al no tener monedas. Agregar 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 demostrar 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 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 .

Ejemplo recursivo simple 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 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)))))

Miremos la ejecución rastreada. Al ingresar una función, se imprimen los argumentos. 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 de una lista (1 2 3 4).

Command: (mymap 'sin '(1 2 3 4))

1 Enter MYMAP SIN (1 2 3 4)
| 2 Enter MYMAP SIN (2 3 4)
|   3 Enter MYMAP SIN (3 4)
|   | 4 Enter MYMAP SIN (4)
|   |   5 Enter MYMAP SIN NIL
|   |   5 Exit MYMAP NIL
|   | 4 Exit MYMAP (-0.75680256)
|   3 Exit MYMAP (0.14112002 -0.75680256)
| 2 Exit MYMAP (0.9092975 0.14112002 -0.75680256)
1 Exit MYMAP (0.841471 0.9092975 0.14112002 -0.75680256)

Este es nuestro resultado :

(0.841471 0.9092975 0.14112002 -0.75680256)

Para explicar la recursividad a un niño de seis años, primero explíquele 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 recursividad a un niño de cinco años, y aunque podría detener la recursividad en 0, no tiene una solución simple para explicar la recursividad a un niño de cero años.

Para resolver un problema utilizando la recursividad, primero subdividirlo en uno o más problemas más simples que puede resolver de la misma manera, y luego, cuando el problema es lo suficientemente simple como para resolver sin más recursividad, puede volver a los niveles superiores.

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

Los niños usan implícitamente la recursividad, por ejemplo:

Viaje por carretera a Disney World

¿Ya llegamos? (No)

¿Ya llegamos? (Pronto)

¿Ya llegamos? (Casi ...)

¿Ya llegamos? (SHHHH)

¿Ya llegamos?(!!!!!)

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

Esta función de cuenta regresiva 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 infinitas gramáticas. Con esto 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 la cantidad 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 recursividad: la capacidad de que una frase vuelva a aparecer dentro de otra frase del mismo tipo. Si digo "Casa del hermano de John", tengo un sustantivo, "casa", que aparece en una frase nominal, "casa del hermano", y esa frase nominal aparece en otra frase nominal, "Casa del hermano de John". Esto tiene mucho sentido, y '

Referencias

• Recursión y pensamiento humano

Cuando trabajo con soluciones recursivas, siempre trato de:

• Establezca el caso base primero, es decir, cuando n = 1 en una solución factorial
• Trate de llegar a una regla general para cualquier otro caso

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

También sería útil si pudieras trabajar en problemas más simples primero solo para acostumbrarte. Algunos ejemplos están resolviendo el factorial y generando el enésimo número de Fibonacci.

Para referencias, recomiendo Algoritmos de Robert Sedgewick.

Espero que ayude. Buena suerte.

Ay. Traté de descubrir las Torres de Hanoi el año pasado. Lo difícil de TOH es que no es un simple ejemplo de recursión: tiene recursiones anidadas que también cambian el papel de las torres en cada llamada. La única forma en que podía tener sentido era visualizar literalmente el movimiento de los anillos en el ojo de mi mente y verbalizar cuál sería la llamada recursiva. Comenzaría con un solo anillo, luego dos, luego tres. Realmente ordené el juego en internet. Me llevó unos dos o tres días romperme el cerebro para conseguirlo.

Una función recursiva es como un resorte que comprime un poco en cada llamada. En cada paso, coloca un poco de información (contexto actual) en una pila. Cuando se alcanza el paso final, se libera el resorte, ¡recogiendo 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 ejemplo, ya que es ineficiente y fácil de aplanar, Fibonacci, Hanoi ...) que son un poco artificiales (rara vez, si alguna vez, 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 un gráfico, pero los árboles son más comunes, en general).
Por ejemplo, una jerarquía de carpetas: para enumerar los archivos, debe iterar sobre ellos. Si encuentra un subdirectorio, la función que enumera los archivos se llama a sí misma con la nueva carpeta como argumento. Cuando regresa de la lista de esta nueva carpeta (¡y sus subcarpetas!), Reanuda 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 contener 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 real del material de enseñanza, ya que era algo con lo que me tropecé en el pasado.

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.

Piensa como magia. Tiene una función que tiene el mismo nombre que la que está tratando de implementar y cuando le da el subproblema, lo 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 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 arte de 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 sublista n-1, por lo tanto, 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 está incompleta porque no consideramos lo que 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 llama condición de 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