Casi todos los artículos que puedo encontrar sobre recursión incluyen los ejemplos de Números factoriales o de Fibonacci, que son:
¿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.
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;
}
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:
Todos estos están relacionados con escenarios reales del mundo real, y todos pueden usarse en aplicaciones de importancia real.
Aquí hay algunos problemas más prácticos que me vienen a la mente:
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.
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:] )
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)
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.
Un detector de palíndromo:
Comience con una cadena: "ABCDEEDCBA" Si se inicia & los caracteres finales son iguales, luego repare y marque "BCDEEDCB", etc ...
Un algoritmo de búsqueda binario suena como lo que quieres.
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 .
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
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.
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);
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.
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.).
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.
Lea otras preguntas en las etiquetas recursion