Usos "necesarios" de la recursividad en idiomas imperativos

Question

Recientemente he visto en un par de lugares diferentes comentarios como: "Aprendí acerca de la recursividad en la escuela, pero nunca la he usado o sentido la necesidad desde entonces. " (La recursión parece ser un ejemplo popular de "aprendizaje de libros" entre un cierto grupo de programadores).

Bueno, es cierto que en lenguajes imperativos como Java y Ruby [1], generalmente utilizamos iteración y evitamos la recursión, en parte debido al riesgo de desbordamientos de pila, y en parte porque es el estilo al que la mayoría de los programadores en esos idiomas están acostumbrados.

Ahora sé que, estrictamente hablando, no hay usos "necesarios" de la recursividad en dichos idiomas: siempre se puede reemplazar de alguna manera la recursión con iteración, sin importar cuán complejas sean las cosas. Por "necesario" aquí, estoy hablando de lo siguiente:

¿Puede pensar en algún ejemplo particular de código en dichos idiomas donde la recursión era mucho mejor que la iteración (por motivos de claridad, eficiencia u otra) que Usaste recursividad de todos modos, y convertir a iteración hubiera sido una gran pérdida.

Recursively walking trees ha sido mencionado varias veces en las respuestas: ¿qué fue exactamente sobre su uso particular que hizo que la recursión fuera mejor que usar un iterador definido por la biblioteca, si hubiera estado disponible?

[1]: Sí, sé que estos también son lenguajes orientados a objetos. Sin embargo, eso no es directamente relevante para esta pregunta.

Answer 1

En mi trabajo, la recursividad rara vez se utiliza para nada algorítmico. Cosas como factoriales, etc. se resuelven de forma mucho más legible (y eficiente) utilizando bucles simples. Cuando aparece, generalmente se debe a que está procesando algunos datos de naturaleza recursiva. Por ejemplo, los nodos en una estructura de árbol podrían procesarse recursivamente.

Si escribiera un programa para recorrer los nodos de un árbol binario, por ejemplo, podría escribir una función que procesara un nodo y se autoproclamara para procesar cada uno de sus elementos secundarios. Esto sería más efectivo que tratar de mantener todos los diferentes estados para cada nodo hijo a medida que los recorría.

Answer 2

Tengo una lista de informes. Estoy usando indizadores en mi clase que contiene esta lista. Los informes se recuperan por sus nombres de pantalla usando los indexadores. En el indexador, si el informe para ese nombre de pantalla no existe, carga el informe y se llama recursivamente a sí mismo.

public class ReportDictionary 
    { 
     private static List<Report> _reportList = null; 

     public ReportColumnList this[string screenName] 
     { 
      get 
      { 
       Report rc = _reportList.Find(delegate(Report obj) { return obj.ReportName == screenName; }); 

       if (rc == null) 
       { 
        this.Load(screenName); 
        return this[screenName]; // Recursive call 
       } 
       else 
        return rc.ReportColumnList.Copy(); 
      } 
      private set 
      { 
       this.Add(screenName, value); 
      } 
     } 

    } 

Esto se puede hacer sin recursion usando algunas líneas adicionales de código.

Answer 3

Se trata de los datos que está procesando.

Escribí un analizador simple para convertir una cadena en una estructura de datos, es probable que sea el único ejemplo en 5 años de trabajo en Java, pero creo que fue la forma correcta de hacerlo.

La cadena era la siguiente:

"{ index = 1, ID = ['A', 'B', 'C'], data = {" + 
    "count = 112, flags = FLAG_1 | FLAG_2 }}" 

La mejor abstracción de esto era un árbol, donde todos los nodos hoja son tipos de datos primitivos, y las ramas podría ser matrices u objetos. Este es el problema recursivo típico, una solución no recursiva es posible pero mucho más compleja.

Answer 4

Cuando usted está caminando cualquier tipo de estructura de árbol, por ejemplo

• analizar una gramática usando un analizador sintáctico descendente recursivo
• caminar un árbol DOM (por ejemplo Analizada HTML o XML)

también, cada método toString() que llama a toString() de los miembros del objeto se puede considerar recursivo también. Todos los algoritmos de serialización de objetos son recursivos.

Answer 5

El ejemplo más conocido es probablemente el algoritmo de quicksort desarrollado por C.A.R. Hoare.

Otro ejemplo es atravesar un árbol de directorios para encontrar un archivo.

Answer 6

No hay usos "necesarios" de recursividad. Todos los algoritmos recursivos se pueden convertir a iterativos. Me parece recordar que una pila es necesaria, pero no puedo recordar la construcción exacta de la parte superior de mi cabeza.

En términos prácticos, si usted no está utilizando la recursividad para el siguiente (incluso en los lenguajes imperativos) que está un poco loco:

1. recorrido del árbol
2. gráficos
3. Lexing/Parsing
4. Ordenando

Answer 7

recursión siempre se puede reescribir como iteración con una pila externa. Sin embargo, si está seguro de que no se arriesga a una recursión muy profunda que podría generar un stackoverflow, la recursión es una opción muy conveniente.

Un buen ejemplo es atravesar una estructura de directorios en un sistema operativo conocido. Por lo general, usted sabe qué tan profundo puede ser (la longitud máxima de la ruta es limitada) y, por lo tanto, no tendrá un stackoverflow. Hacer lo mismo a través de la iteración con una pila externa no es tan conveniente.

Answer 8

En mi opinión, los algoritmos recursivos son un ajuste natural cuando la estructura de datos también es recursiva.

def traverse(node, function): 
    function(this) 
    for each childnode in children: 
     traverse(childnode, function) 

No entiendo por qué querría escribir eso de forma iterativa.

Answer 9

Se dijo "cualquier árbol". Puedo ser muy cauteloso, y sé que las pilas son grandes hoy en día, pero todavía no usaré la recursión en un árbol típico. Sin embargo, lo haría en un balanced tree.