recursion - recursivo - recursividad informatica
Ejemplos de funciones recursivas (23)
¡Escribe un analizador de descenso recursivo !
¿Alguien puede sugerir ejemplos de programación que ilustren funciones recursivas? Están los viejos caballos habituales, como la serie Fibonacci y las torres de Hanoi , pero cualquier cosa que no sea, sería divertido.
¿Qué hay de revertir una cadena?
void rev(string s) {
if (!s.empty()) {
rev(s[1..s.length]);
}
print(s[0]);
}
Comprender esto ayuda a entender la recursión.
¿Qué hay de todo el procesamiento de listas , como:
- mapa (y andmap, ormap)
- fold (foldl, foldr)
- filtrar
- etc ...
¿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.
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 una instancia de File 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 ejemplo, FileUtils.deleteDirectory() de la biblioteca Commons IO ; ver el API doc & source .
Aquí hay un ejemplo que publiqué en este sitio hace un tiempo para generar recursivamente un árbol de menú: Ejemplo recursivo
Como otros ya han dicho, muchos ejemplos de recursión canónica son académicos.
Algunos usos prácticos que he encontrado en el pasado son:
1 - Navegando por una estructura de árbol, como un sistema de archivos o el registro
2 - Manipular controles de contenedor que pueden contener otros controles de contenedor (como Paneles o GroupBoxes)
Del mundo de las matemáticas, está 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 2 65536 - 3.
El 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 aún implementa el patrón de intérprete es una función ToString 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 de 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 explícitamente enumera lo anterior como un ejemplo de dicho patrón).
El ejemplo más peludo que conozco es Knuth''s Man o Boy Test . Además de la recursión, utiliza las funciones de Algol de definiciones de funciones anidadas (cierres), referencias de función y dualismo constante / función (llamada por nombre).
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;
}
Había una vez, y no hace mucho tiempo, que los niños de las escuelas primarias aprendían la recursividad usando Logo y Turtle Graphics. http://en.wikipedia.org/wiki/Turtle_graphics
La recursión también es excelente para resolver acertijos mediante una prueba exhaustiva. Hay un tipo de acertijo llamado "rellenar" (Google it) en el que se obtiene una cuadrícula como un crucigrama, y las palabras, pero no hay pistas, no hay cuadrados numerados. Una vez escribí un programa que usa recursividad para que un editor de crucigramas resolviera los acertijos para asegurarse de que la solución conocida fuera única.
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.
Las funciones recursivas son excelentes para trabajar con tipos de datos definidos recursivamente :
- Un número natural es cero o el sucesor de otro número natural
- Una lista es la lista vacía u otra lista con un elemento al frente
- Un árbol es un nodo con algunos datos y cero o más otros subárboles
Etc.
Mi favorito personal es la búsqueda binaria
Editar: También, cruce de árbol. Caminando por una estructura de archivos de carpetas, por ejemplo.
Mi tipo favorito, fusionar ordenar
(Favorito ya que puedo recordar el algoritmo y no es tan malo para el rendimiento)
Otro par de "sospechosos habituales" son Quicksort y MergeSort
Para understand recursion , primero se debe entender la recursion .
Traduzca un índice de columna de hoja de cálculo a un nombre de columna.
Es más complicado de lo que parece, porque las columnas de la hoja de cálculo no manejan el dígito ''0'' correctamente. Por ejemplo, si toma AZ como dígitos cuando aumenta de Z a AA sería como pasar de 9 a 11 o de 9 a 00 en lugar de 10 (dependiendo de si A es 1 o 0). ¡Incluso el ejemplo de Soporte de Microsoft se equivoca para algo superior a AAA!
La solución recursiva funciona porque puede recurse directamente en esos límites de nuevos dígitos. Esta implementación se encuentra en VB.Net y trata la primera columna (''A'') como índice 1.
Function ColumnName(ByVal index As Integer) As String
Static chars() As Char = {"A"c, "B"c, "C"c, "D"c, "E"c, "F"c, "G"c, "H"c, "I"c, "J"c, "K"c, "L"c, "M"c, "N"c, "O"c, "P"c, "Q"c, "R"c, "S"c, "T"c, "U"c, "V"c, "W"c, "X"c, "Y"c, "Z"c}
index -= 1 ''adjust index so it matches 0-indexed array rather than 1-indexed column''
Dim quotient As Integer = index / 26 ''normal / operator rounds. / does integer division''
If quotient > 0 Then
Return ColumnName(quotient) & chars(index Mod 26)
Else
Return chars(index Mod 26)
End If
End Function
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.
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:
A child couldn''t sleep, so her mother told a story about a little frog, who couldn''t sleep, so the frog''s mother told a story about a little bear, who couldn''t sleep, so bear''s mother told a story about a little weasel ...who fell asleep. ...and the little bear fell asleep; ...and the little frog fell asleep; ...and the child fell asleep.
La implementación de Gráficos por Guido van Rossum tiene algunas funciones recursivas en Python para encontrar caminos entre dos nodos en los gráficos.
- Factorial
- Recorrer un árbol en profundidad (en un sistema de archivos, un espacio de juego o cualquier otro caso)