Recursión sin factorial, números de Fibonacci, etc.

46

Casi todos los artículos que puedo encontrar sobre recursión incluyen los ejemplos de Números factoriales o de Fibonacci, que son:

  1. Matemáticas
  2. Inútil en la vida real

¿Hay algunos ejemplos interesantes de código no matemáticos para enseñar recursión?

Estoy pensando en los algoritmos de dividir y conquistar, pero generalmente involucran estructuras de datos complejas.

    
pregunta lazyCrab 18.04.2015 - 13:17

17 respuestas

106

Las estructuras de directorios / archivos son el mejor ejemplo de un uso para la recursión, porque todos los entienden antes de que comiences, pero cualquier cosa que involucre estructuras similares a árboles servirá.

void GetAllFilePaths(Directory dir, List<string> paths)
{
    foreach(File file in dir.Files)
    {
        paths.Add(file.Path);
    }

    foreach(Directory subdir in dir.Directories)
    {
        GetAllFilePaths(subdir, paths)
    }
}

List<string> GetAllFilePaths(Directory dir)
{
    List<string> paths = new List<string>();
    GetAllFilePaths(dir, paths);
    return paths;
}
    
respondido por el pdr 13.09.2011 - 15:03
50

Busca cosas que involucren estructuras de árboles. Un árbol es relativamente fácil de agarrar, y la belleza de una solución recursiva se manifiesta mucho más pronto que con las estructuras de datos lineales como las listas.

Cosas para pensar:

  • sistemas de archivos - esos son básicamente árboles; una buena tarea de programación sería buscar todas las imágenes .jpg en un directorio determinado y todos sus subdirectorios
  • ancestro: dado un árbol genealógico, encuentra el número de generaciones que tienes que subir para encontrar un antepasado común; o compruebe si dos personas en el árbol pertenecen a la misma generación; o compruebe si dos personas en el árbol pueden casarse legalmente (depende de la jurisdicción :)
  • Documentos similares a HTML: convierta entre la representación en serie (texto) de un documento y un árbol DOM; realizar operaciones en subconjuntos de un DOM (tal vez incluso implementar un subconjunto de xpath?); ...

Todos estos están relacionados con escenarios reales del mundo real, y todos pueden usarse en aplicaciones de importancia real.

    
respondido por el tdammers 13.09.2011 - 13:00
40

enlace

  • modelando una infección contagiosa
  • generando geometría
  • gestión de directorios
  • clasificación

enlace

  • trazado de rayos
  • ajedrez
  • código fuente de análisis (gramática del idioma)

enlace

  • búsqueda BST
  • Torres de Hanoi
  • búsqueda en palíndromo

enlace

  • Ofrece una bonita historia en inglés que ilustra la recursividad de un cuento antes de irse a dormir.
respondido por el mskfisher 23.05.2017 - 13:33
22

Aquí hay algunos problemas más prácticos que me vienen a la mente:

  • Combinar clasificación
  • Búsqueda binaria
  • Recorrido, inserción y eliminación en árboles (utilizado en gran medida en aplicaciones de base de datos)
  • generador de permutaciones
  • solucionador de Sudoku (con seguimiento)
  • Corrector ortográfico (de nuevo con retroceso)
  • Análisis de sintaxis (.e.g, un programa que convierte el prefijo en notación de postfijo)
respondido por el Daniel Scocco 13.09.2011 - 13:12
11

QuickSort sería el primero que salta a la mente. La búsqueda binaria también es un problema recursivo. Más allá de eso, hay clases enteras de problemas que hacen que las soluciones caigan casi gratis cuando empiezas a trabajar con recursión.

    
respondido por el Zachary K 13.09.2011 - 12:56
8

Ordenar, definido recursivamente en Python.

def sort( a ):
    if len(a) == 1: return a
    part1= sort( a[:len(a)//2] )
    part2= sort( a[len(a)//2:] )
    return merge( part1, part2 )

Combinar, definido recursivamente.

def merge( a, b ):
    if len(b) == 0: return a
    if len(a) == 0: return b
    if a[0] < b[0]:
        return [ a[0] ] + merge(a[1:], b)
    else:
        return [ b[0] ] + merge(a, b[1:]) 

Búsqueda lineal, definida recursivamente.

def find( element, sequence ):
    if len(sequence) == 0: return False
    if element == sequence[0]: return True
    return find( element, sequence[1:] )

Búsqueda binaria, definida recursivamente.

def binsearch( element, sequence ):
    if len(sequence) == 0: return False
    mid = len(sequence)//2
    if element < mid: 
        return binsearch( element, sequence[:mid] )
    else:
        return binsearch( element, sequence[mid:] )
    
respondido por el S.Lott 13.09.2011 - 15:26
6

En cierto sentido, la recursión tiene que ver con dividir y conquistar soluciones, es decir, reducir el espacio del problema a uno más pequeño para ayudar a encontrar la solución a un problema simple, y luego volver a reconstruir el problema original para componer la respuesta correcta .

Algunos ejemplos que no involucran matemáticas para enseñar recursión (al menos los problemas que recuerdo de mis años universitarios):

Estos son ejemplos de uso de Backtracking para resolver el problema.

Otros problemas son los clásicos del dominio de Inteligencia Artificial: Uso de la búsqueda en profundidad primero, pathfinding, planificación.

Todos esos problemas involucran algún tipo de estructura de datos "compleja", pero si no quieres enseñarlo con matemáticas (números), tus opciones pueden ser más limitadas. Yoy puede querer comenzar a enseñar con una estructura de datos básica, como una Lista vinculada. Por ejemplo, representando los números naturales usando una lista:

0 = lista vacía 1 = lista con un nodo. 2 = lista con 2 nodos. ...

luego defina la suma de dos números en términos de esta estructura de datos como esta: Vacío + N = N Nodo (X) + N = Nodo (X + N)

    
respondido por el Gabriel 05.04.2012 - 14:18
5

Towers of Hanoi es una buena herramienta para ayudar a aprender la recursión.

Hay muchas soluciones para él en la web en muchos idiomas diferentes.

    
respondido por el Oded 13.09.2011 - 12:58
5

Un detector de palíndromo:

Comience con una cadena: "ABCDEEDCBA" Si se inicia & los caracteres finales son iguales, luego repare y marque "BCDEEDCB", etc ...

    
respondido por el NWS 13.09.2011 - 13:13
5

Un algoritmo de búsqueda binario suena como lo que quieres.

    
respondido por el Sardathrion 12.05.2012 - 20:22
4

En los lenguajes de programación funcional, cuando no hay funciones de orden superior, se usa la recursión en lugar de los bucles imperativos para evitar el estado mutable.

F # es un lenguaje funcional impuro que permite ambos estilos, así que los compararé aquí. Lo siguiente suma todos los números en una lista.

Imperative Loop with Mutable Variable

let xlist = [1;2;3;4;5;6;7;8;9;10]
let mutable sum = 0
for x in xlist do
    sum <- sum + x

Bucle recursivo sin estado mutable

let xlist = [1;2;3;4;5;6;7;8;9;10]
let rec loop sum xlist = 
    match xlist with
    | [] -> sum
    | x::xlist -> loop (sum + x) xlist
let sum = loop 0 xlist

Tenga en cuenta que este tipo de agregación se se captura en la función de orden superior List.fold y se puede escribir como List.fold (+) 0 xlist o incluso más simplemente con la función de conveniencia List.sum como solo List.sum xlist .

    
respondido por el Stephen Swensen 13.09.2011 - 17:15
3

He usado mucho la recursión en la IA del juego. Escribiendo en C ++, utilicé una serie de aproximadamente 7 funciones que se llaman entre sí en orden (la primera función tiene la opción de omitir todas esas funciones y, en su lugar, se llama una cadena de 2 funciones más). La función final en cualquiera de las cadenas volvió a llamar a la primera función hasta que la profundidad restante que quería buscar fuera a 0, en cuyo caso la función final llamaría a mi función de evaluación y devolvería la puntuación de la posición.

Las múltiples funciones me permitieron derivarme fácilmente según las decisiones del jugador o los eventos aleatorios en el juego. Haría uso del paso por referencia siempre que podía, porque estaba transmitiendo estructuras de datos muy grandes, pero debido a la forma en que estaba estructurado el juego, era muy difícil tener un "movimiento de deshacer" en mi búsqueda, por lo que Usaría el paso por valor en algunas funciones para mantener mis datos originales sin cambios. Debido a esto, cambiar a un enfoque basado en bucles en lugar de un enfoque recursivo resultó demasiado difícil.

Puede ver un resumen muy básico de este tipo de programa, consulte enlace

    
respondido por el David Stone 13.09.2011 - 18:18
3

Un ejemplo realmente bueno de la vida real en los negocios es algo que se llama "Lista de materiales". Estos son los datos que representan todos los componentes que conforman un producto terminado. Por ejemplo, usemos una bicicleta. Una bicicleta tiene manillares, ruedas, un cuadro, etc. Y cada uno de esos componentes puede tener subcomponentes. por ejemplo, la rueda puede tener radios, un vástago de válvula, etc. Por lo general, estos están representados en una estructura de árbol.

Ahora, para consultar cualquier información agregada sobre la lista de materiales o para cambiar elementos en una lista de materiales, muchas veces recurre a la recursión.

    class BomPart
    {
        public string PartNumber { get; set; }
        public string Desription { get; set; }
        public int Quantity { get; set; }
        public bool Plastic { get; set; }
        public List<BomPart> Components = new List<BomPart>();
    }

Y una muestra recursiva de muestra ...

    static int ComponentCount(BomPart part)
    {
        int subCount = 0;
        foreach(BomPart p in part.Components)
            subCount += ComponentCount(p);
        return part.Quantity * Math.Max(1,subCount);

    }

Obviamente, la clase BomPart tendría muchos más campos. Es posible que deba averiguar cuántos componentes plásticos tiene, cuánto trabajo requiere construir una parte completa, etc. Sin embargo, todo esto vuelve a la utilidad de la Recursión en una estructura de árbol.

    
respondido por el deepee1 13.09.2011 - 21:00
-1

Las relaciones familiares son buenos ejemplos porque todos los entienden de manera intuitiva:

ancestor(joe, me) = (joe == me) 
                    OR ancestor(joe, me.father) 
                    OR ancestor(joe, me.mother);
    
respondido por el Caleb 13.09.2011 - 21:16
-1

Un trabajo de recursión interior bastante inútil pero que funciona bien es recursivo strlen() :

size_t strlen( const char* str )
{
    if( *str == 0 ) {
       return 0;
    }
    return 1 + strlen( str + 1 );
}

No matemática - una función muy simple. Por supuesto, no lo implementas recursivamente en la vida real, pero es una buena demostración de recursión.

    
respondido por el sharptooth 14.09.2011 - 12:13
-2

Otro problema de recursión en el mundo real con el que los estudiantes pueden relacionarse es construir su propio rastreador web que extrae información de un sitio web y sigue todos los enlaces dentro de ese sitio (y todos los enlaces de esos enlaces, etc.).

    
respondido por el GregW 13.09.2011 - 18:22
-2

Resolví un problema con un patrón de caballero (en un tablero de ajedrez) usando un programa recursivo. Se suponía que debías mover al caballero para que tocara todos los cuadrados, excepto unos pocos cuadrados marcados.

Usted simplemente:

mark your "Current" square
gather a list of free squares that are valid moves
are there no valid moves?
    are all squares marked?
        you win!
for each free square
    recurse!
clear the mark on your current square.
return.    

Se pueden trabajar muchos tipos de escenarios de "reflexión anticipada" probando posibilidades futuras en un árbol como este.

    
respondido por el Bill K 13.09.2011 - 22:07

Lea otras preguntas en las etiquetas