Comprender la recursividad [cerrado]

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

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

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

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

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

Respuesta: si el jarrón no está vacío, sacas una flor y luego vacías un jarrón 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, sacas una flor y luego vacías un jarrón que contiene una flor.

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

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

¿Cómo se vacía un jarrón que no contiene flores?

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

Eso es repetitivo. Generalicémoslo:

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

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

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?

Bueno, sí, la recursividad se puede reemplazar con iteración, pero a menudo la recursividad es más elegante.

Hablemos de árboles. En informática, un árbol es una estructura formada por nodos , donde cada nodo tiene una cierta cantidad de hijos que también son nodos, o nulos. Un árbol binario es un árbol formado por nodos que tienen exactamente dos hijos, normalmente 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.

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

Para sumar el valor de cualquier nodo, agregaríamos el valor del propio nodo al valor de su hijo izquierdo, si lo hubiera, y al valor de su hijo derecho, si lo hubiera. Ahora recuerde 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í al valor de su hijo izquierdo, si lo hubiera, y al valor de su hijo derecho, si lo hubiera.

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 hubiera, y al valor de su hijo derecho, si lo hubiera.

¿Quizás ya has anticipado hacia 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.

Digamos que tenemos un árbol que se ve así (los números son valores, las barras diagonales apuntan a 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 ) ;

Ampliémoslo en su lugar. Dondequiera que 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 ;

¿Ves ahora cómo conquistamos una estructura de profundidad y "ramificación" arbitraria, al considerarla 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 única rama si/entonces y dos declaraciones de retorno simples que casi se escribieron solas, 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 jarrón anterior es un ejemplo de recursividad de cola . Todo lo que significa la recursividad de 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 era recursivo con la cola, porque aunque lo último que hicimos fue recurrir al hijo derecho, antes de hacerlo recurrimos al hijo 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 retenido será un carácter, no un número.

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

Lo que queremos hacer es imprimir el árbol en orden alfabético. Esto es fácil de hacer, dada la propiedad especial del árbol. Simplemente imprimimos el hijo izquierdo, luego el carácter del nodo y luego el hijo derecho.

No queremos simplemente imprimir lo queramos o no, así que le pasaremos a nuestra función algo para imprimir. Este será un objeto con una función print(char); No necesitamos preocuparnos de cómo funciona, sólo que cuando se llama a print, imprimirá algo, en alguna parte.

Veámoslo 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 de que ahora importa el orden de las operaciones, 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 sigamos transmitiéndola. Pasamos un puntero de nodo y una impresora a la función, y en cada llamada recursiva, los pasamos "hacia 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, con solo saber imprimir un solo nodo en orden alfabético. Lo cual era simplemente (porque nuestro árbol tenía la propiedad especial de ordenar los valores a la izquierda de los valores alfabéticamente posteriores) saber 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 sólo cómo hacer una parte del todo (y sabiendo cuándo dejar de recurrir).

Recordando que en la mayoría de los idiomas, operador || ("o") produce un cortocircuito 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, debido a que edité esta respuesta más de cuatro veces (para agregar el último ejemplo, pero principalmente para corregir errores tipográficos y pulirla; 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

Apr 04 '2009 21:04 tpdi