Ejemplos de recursividad del mundo real [cerrado]
https://stackoverflow.com/questions/105838
-
01-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Cuáles son mundo real ¿Problemas en los que un enfoque recursivo es la solución natural además de la búsqueda en profundidad (DFS)?
(No considero Torre de Hanoi, Número de Fibonacci, o problemas factoriales del mundo real.Son un poco artificiales en mi opinión.)
Solución
Hay muchos ejemplos matemáticos aquí, pero querías un mundo real ejemplo, así que, pensándolo un poco, esto es posiblemente lo mejor que puedo ofrecer:
Se encuentra una persona que ha contraído una determinada infección contagiosa, que no es mortal y se cura sola rápidamente (tipo A), excepto una de cada cinco personas (las llamaremos tipo B) que se infecta permanentemente con ella y no muestra ninguna infección. síntomas y simplemente actúa como esparcidor.
Esto crea oleadas de caos bastante molestas cuando el tipo B infecta a una multitud de tipos A.
Su tarea es localizar todos los tipos B e inmunizarlos para detener la columna vertebral de la enfermedad.Desafortunadamente, no se puede administrar una cura a nivel nacional para todos, porque las personas que son del tipo A también son alérgicas mortales a la cura que funciona para el tipo B.
La forma en que haría esto sería mediante descubrimiento social, dada una persona infectada (Tipo A), elija todos sus contactos en la última semana y marque cada contacto en un montón.Cuando pruebe que una persona está infectada, agréguela a la cola de "seguimiento".Cuando una persona es tipo B, agrégala al "seguimiento" al principio (porque quieres detener esto rápidamente).
Después de procesar a una persona determinada, seleccione a la persona del frente de la cola y aplique la vacuna si es necesario.Haga que todos sus contactos no hayan sido visitados anteriormente y luego realice una prueba para ver si están infectados.
Repita hasta que la cola de personas infectadas llegue a 0 y luego espere a que se produzca otro brote.
(Ok, esto es un poco iterativo, pero es una forma iterativa de resolver un problema recursivo; en este caso, el primer recorrido en amplitud de una base de población intenta descubrir caminos probables hacia los problemas y, además, las soluciones iterativas suelen ser más rápidas y efectivas. , y elimino compulsivamente la recursividad en todas partes hasta el punto de que se vuelve instintiva.....¡Maldita sea!)
Otros consejos
Un ejemplo del mundo real de recursividad
¿Qué tal cualquier cosa que involucre una estructura de directorios en el sistema de archivos?Buscar archivos de forma recursiva, eliminar archivos, crear directorios, etc.
Aquí hay una implementación de Java que imprime recursivamente el contenido de un directorio y sus subdirectorios.
import java.io.File;
public class DirectoryContentAnalyserOne implements DirectoryContentAnalyser {
private static StringBuilder indentation = new StringBuilder();
public static void main (String args [] ){
// Here you pass the path to the directory to be scanned
getDirectoryContent("C:\\DirOne\\DirTwo\\AndSoOn");
}
private static void getDirectoryContent(String filePath) {
File currentDirOrFile = new File(filePath);
if ( !currentDirOrFile.exists() ){
return;
}
else if ( currentDirOrFile.isFile() ){
System.out.println(indentation + currentDirOrFile.getName());
return;
}
else{
System.out.println("\n" + indentation + "|_" +currentDirOrFile.getName());
indentation.append(" ");
for ( String currentFileOrDirName : currentDirOrFile.list()){
getPrivateDirectoryContent(currentDirOrFile + "\\" + currentFileOrDirName);
}
if (indentation.length() - 3 > 3 ){
indentation.delete(indentation.length() - 3, indentation.length());
}
}
}
}
Ordenación rápida, fusionar ordenar, y la mayoría de los otros tipos N-log N.
El ejemplo de Matt Dillard es bueno.De manera más general, cualquier movimiento de un árbol puede manejarse mediante recursividad con mucha facilidad.Por ejemplo, compilar árboles de análisis, recorrer XML o HTML, etc.
La recursividad se utiliza a menudo en implementaciones del Algoritmo de retroceso.Para una aplicación de esto en el "mundo real", ¿qué tal una solucionador de sudokus?
La recursividad es apropiada siempre que un problema se pueda resolver dividiéndolo en subproblemas, que pueden utilizar el mismo algoritmo para resolverlos.Los algoritmos en árboles y listas ordenadas encajan perfectamente.Muchos problemas de geometría computacional (y juegos 3D) se pueden resolver de forma recursiva utilizando partición del espacio binario (BSP) árboles, subdivisiones gordas, u otras formas de dividir el mundo en subpartes.
La recursividad también es apropiada cuando se intenta garantizar la corrección de un algoritmo.Dada una función que toma entradas inmutables y devuelve un resultado que es una combinación de llamadas recursivas y no recursivas a las entradas, generalmente es fácil demostrar que la función es correcta (o no) mediante inducción matemática.A menudo es difícil hacer esto con una función iterativa o con entradas que pueden mutar.Esto puede resultar útil cuando se trata de cálculos financieros y otras aplicaciones donde la corrección es muy importante.
Seguramente muchos compiladores utilizan mucho la recursividad.Los lenguajes informáticos son inherentemente recursivos en sí mismos (es decir, se pueden incrustar declaraciones "si" dentro de otras declaraciones "si", etc.).
Deshabilitar/configurar controles de solo lectura para todos los niños en un control de contenedor.Necesitaba hacer esto porque algunos de los controles secundarios eran contenedores.
public static void SetReadOnly(Control ctrl, bool readOnly)
{
//set the control read only
SetControlReadOnly(ctrl, readOnly);
if (ctrl.Controls != null && ctrl.Controls.Count > 0)
{
//recursively loop through all child controls
foreach (Control c in ctrl.Controls)
SetReadOnly(c, readOnly);
}
}
Famoso ciclo de evaluación/aplicación de SICP
(fuente: mit.edu)
Aquí está la definición de evaluación:
(define (eval exp env)
(cond ((self-evaluating? exp) exp)
((variable? exp) (lookup-variable-value exp env))
((quoted? exp) (text-of-quotation exp))
((assignment? exp) (eval-assignment exp env))
((definition? exp) (eval-definition exp env))
((if? exp) (eval-if exp env))
((lambda? exp)
(make-procedure (lambda-parameters exp)
(lambda-body exp)
env))
((begin? exp)
(eval-sequence (begin-actions exp) env))
((cond? exp) (eval (cond->if exp) env))
((application? exp)
(apply (eval (operator exp) env)
(list-of-values (operands exp) env)))
(else
(error "Unknown expression type - EVAL" exp))))
Aquí está la definición de aplicar:
(define (apply procedure arguments)
(cond ((primitive-procedure? procedure)
(apply-primitive-procedure procedure arguments))
((compound-procedure? procedure)
(eval-sequence
(procedure-body procedure)
(extend-environment
(procedure-parameters procedure)
arguments
(procedure-environment procedure))))
(else
(error
"Unknown procedure type - APPLY" procedure))))
Aquí está la definición de secuencia de evaluación:
(define (eval-sequence exps env)
(cond ((last-exp? exps) (eval (first-exp exps) env))
(else (eval (first-exp exps) env)
(eval-sequence (rest-exps exps) env))))
eval -> apply -> eval-sequence -> eval
La recursividad se utiliza en cosas como árboles BSP para la detección de colisiones en el desarrollo de juegos (y otras áreas similares).
La gente suele clasificar pilas de documentos mediante un método recursivo.Por ejemplo, imagina que estás clasificando 100 documentos con nombres.Primero coloque los documentos en pilas por la primera letra y luego clasifique cada pila.
La búsqueda de palabras en el diccionario a menudo se realiza mediante una técnica similar a la búsqueda binaria, que es recursiva.
En las organizaciones, los jefes suelen dar órdenes a los jefes de departamento, quienes a su vez dan órdenes a los gerentes, y así sucesivamente.
Los analizadores y compiladores pueden escribirse en un método de descenso recursivo.No es la mejor manera de hacerlo, ya que herramientas como lex/yacc generan analizadores más rápidos y eficientes, pero conceptualmente son simples y fáciles de implementar, por lo que siguen siendo comunes.
Requisito del mundo real que obtuve recientemente:
Requisito A:Implemente esta característica después de comprender a fondo el Requisito A.
La recursividad se aplica a problemas (situaciones) en los que se puede dividir (reducir) en partes más pequeñas, y cada parte se parece al problema original.
Buenos ejemplos de cosas que contienen partes más pequeñas similares a sí mismas son:
- estructura de árbol (una rama es como un árbol)
- listas (parte de una lista sigue siendo una lista)
- contenedores (muñecas rusas)
- secuencias (parte de una secuencia se parece a la siguiente)
- grupos de objetos (un subgrupo sigue siendo un grupo de objetos)
La recursión es una técnica para seguir dividiendo el problema en partes cada vez más pequeñas, hasta que una de esas partes se vuelve lo suficientemente pequeña como para ser pan comido.Por supuesto, después de dividirlos, tendrás que "unir" los resultados nuevamente en el orden correcto para formar una solución total de tu problema original.
Algunos algoritmos de clasificación recursiva, algoritmos de recorrido de árboles, algoritmos de mapeo/reducción y divide y vencerás son ejemplos de esta técnica.
En programación de computadoras, la mayoría de los lenguajes de tipos de devolución de llamadas basados en pilas ya tienen capacidades integradas para la recursividad:es decir.
- dividir el problema en partes más pequeñas ==> llamarse a sí mismo en un subconjunto más pequeño de los datos originales),
- realizar un seguimiento de cómo se dividen las piezas ==> pila de llamadas,
- unir los resultados ==> retorno basado en pila
Tengo un sistema que usa puro recursión de cola en algunos lugares para simular una máquina de estados.
Algunos buenos ejemplos de recursividad se encuentran en programación funcional idiomas.En lenguajes de programación funcionales (erlang, Haskell, ml/OCaml/F#, etc.), es muy común que cualquier procesamiento de listas utilice la recursividad.
Cuando se trata de listas en lenguajes típicos imperativos de estilo programación orientada a objetos, es muy común ver listas implementadas como listas vinculadas ([elemento1 -> elemento2 -> elemento3 -> elemento4]).Sin embargo, en algunos lenguajes de programación funcionales, encontrará que las listas en sí se implementan de forma recursiva, donde el "encabezado" de la lista apunta al primer elemento de la lista y la "cola" apunta a una lista que contiene el resto de los elementos ( [elemento1 -> [elemento2 -> [elemento3 -> [elemento4 -> []]]]]).Es bastante creativo en mi opinión.
Este manejo de listas, cuando se combina con la coincidencia de patrones, es MUY poderoso.Digamos que quiero resumir una lista de números:
let rec Sum numbers =
match numbers with
| [] -> 0
| head::tail -> head + Sum tail
Básicamente, esto dice "si nos llamaron con una lista vacía, devolvemos 0" (lo que nos permite romper la recursividad); de lo contrario, devolvemos el valor de head + el valor de Sum llamado con los elementos restantes (de ahí nuestra recursividad).
Por ejemplo, podría tener una lista de URL, creo que separo todas las URL a las que enlaza cada URL y luego reduzco el número total de enlaces hacia/desde todas las URL para generar "valores" para una página (un enfoque que adopta Google con Rango de página y que puedes encontrar definido en el original Mapa reducido papel).También puedes hacer esto para generar recuentos de palabras en un documento.Y muchas, muchas, muchas cosas más también.
Puede extender este patrón funcional a cualquier tipo de Mapa reducido código donde puede tomar una lista de algo, transformarla y devolver algo más (ya sea otra lista o algún comando zip en la lista).
XML, o atravesar cualquier cosa que sea un árbol.Aunque, para ser honesto, casi nunca uso la recursividad en mi trabajo.
Bucles de retroalimentación en una organización jerárquica.
El jefe superior les dice a los altos ejecutivos que recopilen comentarios de todos en la empresa.
Cada ejecutivo reúne a sus subordinados directos y les dice que recopilen comentarios de sus subordinados directos.
Y así sucesivamente.
Las personas que no tienen subordinados directos (los nodos de las hojas del árbol) dan su opinión.
La retroalimentación regresa al árbol y cada gerente agrega su propia retroalimentación.
Al final, todos los comentarios llegan al jefe superior.
Esta es la solución natural porque el método recursivo permite filtrar en cada nivel: cotejar duplicados y eliminar comentarios ofensivos.el jefe superior podría envíe un correo electrónico global y haga que cada empleado le informe sus comentarios directamente, pero existen los problemas de "no puedes manejar la verdad" y "estás despedido", por lo que la recursividad funciona mejor aquí.
Supongamos que está creando un CMS para un sitio web, donde sus páginas están en una estructura de árbol, donde la raíz es, por ejemplo, la página de inicio.
Supongamos también que su {usuario|cliente|cliente|jefe} solicita que coloque una ruta de navegación en cada página para mostrar dónde se encuentra en el árbol.
Para cualquier página n determinada, es posible que desee desplazarse hasta el padre de n, y su padre, y así sucesivamente, de forma recursiva para crear una lista de nodos hasta la raíz del árbol de páginas.
Por supuesto, en ese ejemplo, accede a la base de datos varias veces por página, por lo que es posible que desee utilizar algún alias SQL en el que busque la tabla de páginas como a y la tabla de páginas nuevamente como b, y una a.id con b.parent para que hagas que la base de datos realice uniones recursivas.Ha pasado un tiempo, por lo que mi sintaxis probablemente no sea útil.
Por otra parte, es posible que desee calcular esto solo una vez y almacenarlo con el registro de la página, actualizándolo solo si mueve la página.Probablemente eso sería más eficiente.
De todos modos, ese es mi $.02
Tiene un árbol de organización que tiene N niveles de profundidad.Varios de los nodos están marcados y desea expandirse solo a aquellos nodos que han sido marcados.
Esto es algo que realmente codifiqué.Es agradable y fácil con la recursividad.
En mi trabajo tenemos un sistema con una estructura de datos genérica que puede describirse como un árbol.Eso significa que la recursividad es una técnica muy eficaz para trabajar con los datos.
Resolverlo sin recursividad requeriría una gran cantidad de código innecesario.El problema de la recursividad es que no es fácil seguir lo que sucede.Realmente tienes que concentrarte cuando sigues el flujo de ejecución.Pero cuando funciona, el código es elegante y eficaz.
Cálculos para finanzas/física, como promedios compuestos.
- Analizando un XML archivo.
- Búsqueda eficiente en espacios multidimensionales.MI.gramo.árboles cuádruples en 2D, árboles oct en 3D, árboles kd, etc.
- Agrupación jerárquica.
- Ahora que lo pienso, atravesar cualquier estructura jerárquica naturalmente se presta a la recursividad.
- Metaprogramación de plantillas en C++, donde no hay bucles y la recursividad es la única forma.
Analizando un árbol de controles en Formularios de Windows o WebForms (.NET Windows Forms / ASP.NET).
El mejor ejemplo que conozco es ordenación rápida, es mucho más sencillo con la recursividad.Echa un vistazo a:
tienda.oreilly.com/product/9780596510046.do
www.amazon.com/Beautiful-Code-Leading-Programmers-Practice/dp/0596510047
(Haga clic en el primer subtítulo debajo del capítulo 3:"El código más hermoso que jamás haya escrito").
Las compañías de teléfono y cable mantienen un modelo de su topología de cableado, que en realidad es una gran red o gráfico.La recursividad es una forma de recorrer este modelo cuando desea encontrar todos los elementos principales o secundarios.
Dado que la recursividad es costosa desde la perspectiva del procesamiento y la memoria, este paso generalmente solo se realiza cuando se cambia la topología y el resultado se almacena en un formato de lista preordenada modificada.
El razonamiento inductivo, el proceso de formación de conceptos, es de naturaleza recursiva.Tu cerebro lo hace todo el tiempo, en el mundo real.
Lo mismo ocurre con el comentario sobre los compiladores.Los nodos del árbol de sintaxis abstracta se prestan naturalmente a la recursividad.Todas las estructuras de datos recursivas (listas enlazadas, árboles, gráficos, etc.) también se manejan más fácilmente con la recursividad.Creo que la mayoría de nosotros no usamos mucho la recursividad una vez que dejamos la escuela debido a los tipos de problemas del mundo real, pero es bueno tenerlo en cuenta como una opción.
La multiplicación de números naturales es un ejemplo de recursividad del mundo real:
To multiply x by y
if x is 0
the answer is 0
if x is 1
the answer is y
otherwise
multiply x - 1 by y, and add x
