Pregunta Ejemplos de funciones recursivas [cerrado]


¿Alguien puede sugerir ejemplos de programación que ilustren funciones recursivas? Están los viejos caballos habituales, como Serie Fibonacci y Torres de Hanoi, pero cualquier cosa aparte de ellos sería divertido.


31
2017-09-24 12:16


origen


Respuestas:


Esta ilustración está en inglés, en lugar de un lenguaje de programación real, pero es útil para explicar el proceso de una manera no técnica:

Un niño no podía dormir, entonces su madre contó una historia sobre una rana pequeña,
  quien no podía dormir, entonces la madre de la rana contó una historia sobre un pequeño oso,
     quien no pudo dormir, entonces la madre de oso contó una historia sobre una pequeña comadreja
       ... que se durmió
     ... y el osito se durmió;
  ... y la pequeña rana se durmió;
... y el niño se durmió.

109
2017-09-24 12:20



A fin de que entender  recursión, uno debe primero entender recursión.


28
2017-09-24 20:44



La regla de oro para la recursión es, "Usar recursión, si y solo si en cada iteración su tarea se divide en dos o más tareas similares ".

Así que Fibonacci no es un buen ejemplo de aplicación de recursión, mientras que Hanoi es una buena opción.

Así que la mayoría de los buenos ejemplos de recursión son cruces de árboles en diferentes situaciones.

Por ejemplo: cruce de gráficos: el requisito de que el nodo visitado nunca se vuelva a visitar de manera efectiva hace que el gráfico sea un árbol (un árbol es un gráfico conectado sin ciclos simples)

algoritmos de dividir y conquistar (clasificación rápida, clasificación por fusión): las partes después de "dividir" constituyen nodos secundarios, "conquistar" constituyen los bordes desde el nodo padre hasta los nodos secundarios.


16
2018-02-27 11:21



¿Qué tal probar una cuerda por ser un palíndromo?

bool isPalindrome(char* s, int len)
{
  if(len < 2)
    return TRUE;
  else
    return s[0] == s[len-1] && isPalindrome(&s[1], len-2);
}

Por supuesto, podrías hacer eso con un ciclo de manera más eficiente.


15
2017-09-24 13:42



Escribe un analizador de descenso recursivo!


13
2017-09-24 12:19



Otra pareja de "sospechosos habituales" son Ordenación rápida y MergeSort


10
2017-09-24 12:23



Del mundo de las matemáticas, hay la función de Ackermann:

Ackermann(m, n)
{
  if(m==0)
    return n+1;
  else if(m>0 && n==0)
    return Ackermann(m-1, 1);
  else if(m>0 && n>0)
    return Ackermann(m-1, Ackermann(m, n-1));
  else
    throw exception; //not defined for negative m or n
}

Siempre termina, pero produce resultados extremadamente grandes incluso para entradas muy pequeñas. Ackermann (4, 2), por ejemplo, devuelve 265536 - 3.


8
2017-09-24 13:36



los patrón de diseño del intérprete es un buen ejemplo porque muchas personas no detectan la recursión. El código de ejemplo enumerado en el artículo de Wikipedia ilustra bien cómo se puede aplicar esto. Sin embargo, un enfoque mucho más básico que todavía implementa el patrón de intérprete es una ToString función para listas anidadas:

class List {
    public List(params object[] items) {
        foreach (object o in items)
            this.Add(o);
    }

    // Most of the implementation omitted …
    public override string ToString() {
        var ret = new StringBuilder();
        ret.Append("( ");
        foreach (object o in this) {
            ret.Append(o);
            ret.Append(" ");
        }
        ret.Append(")");
        return ret.ToString();
    }
}

var lst = new List(1, 2, new List(3, 4), new List(new List(5), 6), 7);
Console.WriteLine(lst);
// yields:
// ( 1 2 ( 3 4 ) ( ( 5 ) 6 ) 7 )

(Sí, sé que no es fácil detectar el patrón del intérprete en el código anterior si espera una función llamada Eval ... pero en realidad, el patrón del intérprete no nos dice cómo se llama la función o incluso qué hace y el libro de GoF enumera explícitamente lo anterior como un ejemplo de dicho patrón).


6
2017-09-24 12:57



En mi opinión, es bueno saber la recursividad, pero la mayoría de las soluciones que podrían utilizar la recursión también se pueden hacer mediante iteración, y la iteración es mucho más eficiente.

Dicho esto aquí es una forma recursiva de encontrar un control en un árbol anidado (como ASP.NET o Winforms):

public Control FindControl(Control startControl, string id)
{
      if (startControl.Id == id)
           return startControl

      if (startControl.Children.Count > 0)
      {
           foreach (Control c in startControl.Children)
           {
                return FindControl(c, id);
           }
      }
      return null;
}

6
2017-09-24 13:50



Aquí hay un ejemplo pragmático del mundo de los sistemas de archivos. Esta utilidad cuenta recursivamente los archivos en un directorio especificado. (No recuerdo por qué, pero en realidad tenía una necesidad de algo así hace mucho tiempo ...)

public static int countFiles(File f) {
    if (f.isFile()){
        return 1;
    }

    // Count children & recurse into subdirs:
    int count = 0;
    File[] files = f.listFiles();
    for (File fileOrDir : files) {
        count += countFiles(fileOrDir);
    }
    return count;
}

(Tenga en cuenta que en Java a File instancia puede representar un archivo normal o un directorio. Esta utilidad excluye directorios del recuento).

Un ejemplo común en el mundo real sería, por ej. FileUtils.deleteDirectory() desde el Commons IO biblioteca; ver el API doc & fuente.


6
2018-05-04 13:17



Un ejemplo del mundo real es el problema del "costo de la factura de materiales".

Supongamos que tenemos una empresa de fabricación que fabrica productos finales. Cada producto es descriptible por una lista de sus partes y el tiempo requerido para ensamblar esas partes. Por ejemplo, fabricamos taladros eléctricos de mano desde una carcasa, motor, mandril, interruptor y cable, y demora 5 minutos.

Dado un costo laboral por minuto estándar, ¿cuánto cuesta fabricar cada uno de nuestros productos?

Ah, por cierto, algunas partes (por ejemplo, el cable) se compran, por lo que sabemos su costo directamente.

Pero nosotros fabricamos algunas de las partes nosotros mismos. Fabricamos un motor de una carcasa, un estator, un rotor, un eje y cojinetes, y demora 15 minutos.

Y hacemos que el estator y el rotor salgan de estampados y cables, ...

Por lo tanto, determinar el costo de un producto terminado en realidad equivale a atravesar el árbol que representa todas las relaciones de la totalidad de la lista de piezas en nuestros procesos. Eso está muy bien expresado con un algoritmo recursivo. Ciertamente también se puede hacer iterativamente, pero la idea central se mezcla con la contabilidad del bricolaje, por lo que no está tan claro lo que está sucediendo.


4
2018-02-03 13:49