recursion - recursivo - recursividad en java
Ejemplos del mundo real de recursión (30)
¿Cuáles son los problemas del mundo real en los que el enfoque recursivo es la solución natural además de la búsqueda en profundidad (DFS)?
(No considero Tower of Hanoi , número de Fibonacci o problemas factoriales del mundo real. Son un poco artificiales en mi mente).
Famoso ciclo de evaluación / aplicación de SICP
Aquí está la definición de eval:
(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 eval-sequence:
(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
Un ejemplo del mundo real de recursión
¿Qué hay de todo lo relacionado con una estructura de directorios en el sistema de archivos? Encontrar recursivamente archivos, 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());
}
}
}
}
Algunos buenos ejemplos de recursión se encuentran en lenguajes de programación funcionales . En los lenguajes de programación funcionales ( Erlang , Haskell , ML / OCaml / F# , etc.), es muy común que cualquier procesamiento de listas use recursividad.
Al tratar con listas en lenguajes de estilo OOP imperativos típicos, es muy común ver listas implementadas como listas vinculadas ([elemento1 -> elemento2 -> elemento3 -> elemento4]). Sin embargo, en algunos lenguajes de programación funcionales, usted encuentra que las listas se implementan recursivamente, donde el "encabezado" de la lista apunta al primer elemento en la lista, y el "final" 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 sumar una lista de números:
let rec Sum numbers =
match numbers with
| [] -> 0
| head::tail -> head + Sum tail
Esto básicamente dice "si nos llamaron con una lista vacía, devuelve 0" (lo que nos permite romper la recursión), de lo contrario, devuelve el valor de la cabeza + el valor de la suma llamada con los elementos restantes (por lo tanto, nuestra recursividad).
Por ejemplo, podría tener una lista de URLs , creo que separaría todas las URL a las que se vincula cada URL, y luego reduciría el número total de enlaces a / desde todas las URL para generar "valores" para una página (un enfoque que Google toma con PageRank y puede encontrarlo definido en el documento original de MapReduce ). Puede hacer esto para generar recuentos de palabras en un documento también. Y muchas, muchas, muchas otras cosas también.
Puedes extender este patrón funcional a cualquier tipo de código MapReduce donde puedas tomar una lista de algo, transformarlo y devolver algo más (ya sea otra lista o algún comando zip en la lista).
Análisis de un árbol de controles en Windows Forms o WebForms (.NET Windows Forms / ASP.NET ).
Aquí hay muchos ejemplos de mathy, pero querías un ejemplo del mundo real , así que con un poco de pensamiento, posiblemente sea lo mejor que puedo ofrecer:
Encuentra a una persona que ha contraído una infección contagiosa determinada, que no es mortal, y se arregla rápidamente (tipo A), excepto uno de cada 5 personas (llamaremos a este tipo B) que se infecta permanentemente con él y no muestra síntomas y simplemente actúa como esparcidor.
Esto crea oleadas de caos bastante molestas cuando el tipo B infecta una multitud de tipo A.
Su tarea es rastrear todo el tipo B e inmunizarlos para detener la columna vertebral de la enfermedad. Desafortunadamente, no puedes administrar una cura a nivel nacional a todos, porque las personas que son tipoas también son mortalmente alérgicas a la cura que funciona para el tipo B.
La forma en que harías esto sería un descubrimiento social, una persona infectada (Tipo A), elige todos sus contactos en la última semana, marcando cada contacto en un montón. Cuando prueba que una persona está infectada, agréguela a la cola de "seguimiento". Cuando una persona es de tipo B, agréguela al "seguimiento" en la cabecera (porque quiere detener esto rápidamente).
Después de procesar a una persona determinada, seleccione a la persona del frente de la cola y aplique la inmunización si es necesario. Obtenga todos sus contactos no visitados previamente, y luego realice una prueba para ver si están infectados.
Repita hasta que la fila de personas infectadas se vuelva 0, y luego espere otro brote.
(Bueno, esto es un poco iterativo, pero es una forma iterativa de resolver un problema recursivo, en este caso, primer cruce transversal de una base poblacional que intenta descubrir posibles caminos hacia los problemas, y además, las soluciones iterativas son a menudo más rápidas y efectivas , y elimino compulsivamente la recursividad en todas partes, se vuelve instintivo ... ¡maldita sea!)
Cálculos para finanzas / física, como promedios compuestos.
Deshabilitar / configurar solo lectura para todos los controles secundarios en un control de contenedor. Necesitaba hacer esto porque algunos de los controles de los niños 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);
}
}
El ejemplo de Matt Dillard es bueno. De manera más general, cualquier caminata de un árbol generalmente puede manejarse por recursión muy fácilmente. Por ejemplo, compilar árboles de análisis, caminar sobre XML o HTML, etc.
El mejor ejemplo que conozco es Quicksort , es mucho más simple con recursion. Echa un vistazo a:
shop.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 he escrito").
El razonamiento inductivo, el proceso de formación del concepto, es de naturaleza recursiva. Tu cerebro lo hace todo el tiempo, en el mundo real.
En mi trabajo, tenemos un sistema con una estructura de datos genéricos que se puede describir como un árbol. Eso significa que la recursividad es una técnica muy efectiva para trabajar con los datos.
Solucionarlo sin recurrencia requeriría una gran cantidad de código innecesario. El problema con la recursión es que no es fácil seguir lo que sucede. Realmente debes concentrarte cuando sigas el flujo de ejecución. Pero cuando funciona, el código es elegante y efectivo.
La gente a menudo clasifica pilas de documentos usando un método recursivo. Por ejemplo, imagine que está ordenando 100 documentos con nombres en ellos. Primero coloque los documentos en pilas en la primera letra, luego clasifique cada pila.
Buscar palabras en el diccionario a menudo se realiza mediante una técnica de búsqueda binaria, que es recursiva.
En las organizaciones, los jefes a menudo dan órdenes a los jefes de departamento, quienes a su vez dan órdenes a los gerentes, y así sucesivamente.
La multiplicación de números naturales es un ejemplo real de recursión:
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
La recursión se aplica a problemas (situaciones) donde puede dividirla (reducirla) en partes más pequeñas, y cada parte se ve similar al problema original.
Buenos ejemplos de dónde las cosas que contienen partes más pequeñas similares a ella son:
- estructura del á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 ve como la siguiente)
- grupos de objetos (un subgrupo es todavía un grupo de objetos)
La recursión es una técnica para seguir dividiendo el problema en pedazos cada vez más pequeños, hasta que una de esas piezas se vuelva lo suficientemente pequeña como para ser un pedazo de pastel. Por supuesto, después de que los descomponga, tendrá que "unir" los resultados nuevamente en el orden correcto para formar una solución total a su problema original.
Algunos algoritmos recursivos de ordenación, algoritmos de caminar árboles, algoritmos de mapa / reducir, dividir y vencer son todos ejemplos de esta técnica.
En la programación de computadoras, la mayoría de los lenguajes tipo devolución de llamadas basados en pila ya tienen las capacidades incorporadas para la recursión: es decir,
- divide el problema en pedazos más pequeños ==> llama a sí mismo en un subconjunto más pequeño de los datos originales),
- realizar un seguimiento de cómo se dividen las piezas ==> call stack,
- cose los resultados de vuelta ==> return basado en pila
La recursión se usa a menudo en implementaciones del algoritmo de Retroceso . Para una aplicación del "mundo real" de esto, ¿qué tal un solucionador de Sudoku ?
La recursión se usa en cosas como los árboles BSP para la detección de colisiones en el desarrollo de juegos (y otras áreas similares).
La recursividad es apropiada siempre que un problema se puede resolver dividiéndolo en subproblemas, que pueden usar el mismo algoritmo para resolverlos. Algoritmos en árboles y listas ordenadas son un ajuste natural. Muchos problemas en geometría computacional (y juegos en 3D) pueden resolverse de manera recursiva utilizando árboles de división de espacio binario (BSP), subdivisiones grasas u otras formas de dividir el mundo en subpartes.
La recursión también es apropiada cuando intentas 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 en las entradas, por lo general es fácil probar que la función es correcta (o no) usando la inducción matemática. A menudo es difícil de hacer esto con una función iterativa o con entradas que pueden mutar. Esto puede ser útil cuando se trata de cálculos financieros y otras aplicaciones donde la corrección es muy importante.
La retroalimentación se repite en una organización jerárquica.
El jefe superior le dice a los altos ejecutivos que recojan los comentarios de todos en la compañía.
Cada ejecutivo recopila sus informes directos y les dice que recopilen comentarios de sus informes directos.
Y en la línea.
Las personas sin informes directos, los nodos de las hojas en el árbol, dan su opinión.
La retroalimentación viaja de regreso al árbol con cada gerente agregando sus propios comentarios.
Finalmente, todos los comentarios lo hacen de nuevo al jefe superior.
Esta es la solución natural porque el método recursivo permite el filtrado en cada nivel: la recopilación de duplicados y la eliminación de comentarios ofensivos. El jefe superior podría enviar un correo electrónico global y hacer que cada empleado informe directamente a él / ella, pero están los problemas de "no puedes manejar la verdad" y "estás despedido", por lo que la recursividad funciona mejor aquí.
Las compañías telefónicas y de 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 atravesar este modelo cuando desea buscar todos los elementos primarios o secundarios.
Dado que la recursividad es costosa desde una perspectiva de procesamiento y memoria, este paso comúnmente solo se realiza cuando se cambia la topología y el resultado se almacena en un formato de lista preordenada modificado.
Lo mismo ocurre con el comentario sobre compiladores. Los nodos abstractos del árbol de sintaxis se prestan naturalmente a la recursión. Todas las estructuras de datos recursivas (listas vinculadas, árboles, gráficos, etc.) también se manejan más fácilmente con recurrencia. Creo que la mayoría de nosotros no usamos mucho la recursividad una vez que estamos fuera de la escuela debido a los tipos de problemas del mundo real, pero es bueno tenerlo en cuenta como una opción.
Los analizadores y compiladores se pueden escribir 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 simples y fáciles de implementar, por lo que siguen siendo comunes.
Requisito del mundo real que obtuve recientemente:
Requisito A: Implementar esta característica después de comprender a fondo el Requisito A.
Seguramente, muchos compiladores recurren mucho a la recursividad. Los lenguajes informáticos son intrínsecamente recursivos (es decir, puede incrustar sentencias ''if'' dentro de otras declaraciones ''if'', etc.).
Supongamos que está creando un CMS para un sitio web, donde sus páginas están en una estructura de árbol, con la raíz es la página de inicio.
Supongamos también que sus solicitudes {user | client | customer | boss} colocan un rastro de navegación en cada página para mostrar dónde se encuentra en el árbol.
Para cualquier página dada n, es posible que desee acercarse al padre de n, y a su padre, y así sucesivamente, de forma recursiva para crear una lista de nodos de respaldo hasta la raíz del árbol de páginas.
Por supuesto, está golpeando el archivo db varias veces por página en ese ejemplo, por lo que es posible que desee utilizar alias de SQL donde busque la tabla de páginas como a, y la tabla de páginas de nuevo como b, y únase a .id con b.parent para que la base de datos haga las uniones recursivas. Ha pasado un tiempo, así que mi sintaxis probablemente no sea útil.
Por otra parte, tal vez solo quiera calcular esto una vez y almacenarlo con el registro de la página, solo actualizándolo si mueve la página. Eso probablemente sea más eficiente.
De todos modos, ese es mi $ .02
Tengo un sistema que usa recursividad de cola pura en algunos lugares para simular una máquina de estado.
Usted tiene un árbol de organización que tiene N niveles profundos. Varios de los nodos están marcados y usted desea expandirse solo a aquellos nodos que se han verificado.
Esto es algo que realmente codifiqué. Es agradable y fácil con la recursión.
XML, o atravesando cualquier cosa que sea un árbol. Aunque, para ser honesto, casi nunca uso la recursividad en mi trabajo.
Quicksort , merge sort y la mayoría de los otros N-log N géneros.
- Analizando un archivo XML .
- Búsqueda eficiente en espacios multidimensionales. P.ej. quad-trees en 2D, oct-trees en 3D, kd-trees, etc.
- Agrupación jerárquica.
- Ahora que lo pienso, atravesar cualquier estructura jerárquica naturalmente se presta a la recursión.
- La metaprogramación de plantillas en C ++, donde no hay bucles y la recursión es la única forma.