¿Qué es un buen ejemplo de recursión que no sea la generación de una secuencia de Fibonacci?

Las otras respuestas mencionan varios algoritmos, lo cual está completamente bien, pero si desea un ejemplo un poco más "concreto", podría enumerar todos los archivos en algún directorio y sus subdirectorios. El sistema de archivos jerárquico es un ejemplo bien conocido de una estructura recursiva (árbol), y podría mostrar la búsqueda de profundidad y amplitud primero utilizando este ejemplo concreto.

Mi ejemplo favorito para la recursión son las Torres de Hanoi: Para mover una pila de piezas del polo A al polo B, se mueve todo lo que está por encima de la pieza más baja al polo que no es A o B, luego se mueve la pieza más baja a B, y luego se mueve la pila que se pone en el "polo ayudante" en la parte superior de la pieza más baja. Para el primer y tercer paso, siga esta instrucción recursivamente. Vea el enlace para una explicación más larga:)

Compruebe si hay un palyndrome :

bool recursivePalindrome(std::string str, unsigned int index = 0) {
    if (index > str.length()/2) return true;
    else if (str[index] == str[str.length()-index-1])
        return recursivePalindrome(str, ++index);
    else return false;
}

O en una nota menos seria:)

void StackOverflow()
{
   StackOverflow();
}

¿Qué tal encontrar factorial.

int GetFactorial(int n )
{
  if ( n==0) return 1;
  return n*GetFactorial(n-1);
}

La idea es, factorial se define recursivamente como el producto de n y factorial de (n-1). Y de la definición recursiva, obtienes tu recursión.

Recorrer la jerarquía de carpetas de un árbol de directorios como parte de un sistema de archivos es un buen ejemplo del mundo real. Mira esto para publicar un ejemplo de C++:

¿Por qué tengo problemas para eliminar directorios recursivamente?

• La mayoría de los otros ejemplos dados aquí son ejemplos matemáticos que en realidad solo re-ilustran la misma aplicación de la recursión.
• Las variantes de búsqueda y ordenación son buenos ejemplos de algoritmos, pero a menudo son demasiado complicadas para los principiantes.
• Torres de Hanoi es un clásico, pero bastante artificial en realidad.

================

El ejemplo que uso para demostrar el poder simple de la recursión es el procesamiento recursivo de archivos en un directorio arbol.

Aquí hay un ejemplo de C#

void ProcessFiles( string sFolder )
{
    foreach( string f in Directory.GetFiles( sFolder ) )
    {
        DoSomethingTo( f );
    }
    foreach( string d in Directory.GetDirectories( sFolder ))
    {
        ProcessFiles( d );
    }
}

Merge sort es un buen ejemplo de un algoritmo que es más fácil de leer y entender cuando se implementa recursivamente.

Aquí hay una pequeña versión de pseudocódigo de alto nivel de Merge Sort:

def merge_sort(List sortlist)
    if sortlist.length <= 1 return sortlist
    split sortlist into leftlist and rightlist
    return merge(merge_sort(leftlist), merge_sort(rightlist))   

def merge(List leftlist, List rightlist)
    while(leftlist and rightlist not empty)
        compare leftlist.first to rightlist.first
        pop lowest value off its list and append to resultlist
    append any remains of leftlist onto resultlist
    append any remains of rightlist onto resultlist
    return resultlist

Una versión iterativa de esto sería mucho más complicada de escribir y visualizar.

Hay varias muestras:

Números catalanes :

T(n) = Sum(T(i)*T(n-i)) for all 1 <= i < n

Función Ackermann :

A(x,y) = y+1 (if x = 0)
A(x,y) = A(x-1,1) (if y=0)
A(x,y) = A(x-1, A(x,y-1)) otherwise.

Problema de laberinto simple

Encontrar el problema de la trayectoria Hamiltoniana

Factorial.

Y puedes ver la página de wiki para otras referencias.

Los buenos ejemplos de recursión a menudo están relacionados con casos en los que la estructura de datos subyacente o el problema en sí es recursivo : árboles, gráficos, algoritmos que utilizan el enfoque divide y vencerás (como muchos tipos), analizador de gramáticas recursivas (como expresiones aritméticas comunes), encontrar estrategia para partidas de dos jugadores similares al ajedrez (para un ejemplo simple considere Nim), problemas combinatorios, etc.

Pruebe la búsqueda binaria recursiva: http://www.fredosaurus.com/notes-cpp/algorithms/searching/rbinarysearch.html

O una ordenación rápida recursiva: http://www.dreamincode.net/forums/topic/72311-recursive-quicksort-algorithm /

Estos son solo dos pequeños ejemplos en un vasto mundo de funciones recursivas.

La evaluación de expresiones aritméticas se puede hacer recursiva o iterativamente usando una pila. Puede ser bastante instructivo comparar los dos enfoques.

Mi suegra tomó un curso introductorio en C. Tenía un problema con la tarea, algo así como:

Tienes una barra de metal (longitud len), y un número de órdenes (n) para cortar el metal en varias longitudes. Quieres maximizar la cantidad de metal que se utiliza, pero no puede exceder la longitud total.

El instructor sugirió iterar de 1 a 2**n en binario, excluyendo un orden si su bit correspondiente era 0 e incluyendo un orden si su bit era 1, manteniendo un registro de la suma máxima. Su propuesta se ejecutaría en tiempo polinómico.

Existe otra solución usando un algoritmo recursivo de mochila. Puede iterar hacia abajo desde len a 1 y hacer una búsqueda en profundidad para encontrar recursivamente la suma de longitudes.

Un área diferente en la que he usado recursión fue para Huffman coding (para comprimir una cadena), pero esto no tiene la sensación intuitiva del problema de la mochila.

La recursión es una maravilla concepto que es radicalmente diferente. Los mejores deseos en el aprendizaje o la enseñanza.

Función de Ackermann:

/* undefined if m and n are negative */
uint32 ackermann( uint32 m, uint32 n )
{
  if( m < 0 && n < 0 ) { exit(1); /* invalid m and n */ }

  if( m == 0 ){ return n + 1; }

  if( m > 0 && n == 0 ){ return ackermann( m - 1, 1 ); }

  if( m > 0 && n > 0 ){ return ackermann( m - 1, ackermann(m, n - 1) ); }
}

Las comparaciones múltiples de m > 0 son redundantes (y pueden simplificarse). Dejándolos como están, sin embargo, muestra la definición estándar de la función Ackermann.

Pero uno no tiene que ir tan lejos del borde matemático para encontrar funciones recursivas interesantes que no sean los números de Fibonnaci.

Tiene la función de mayor denominador común (GDC), quicksort y el algoritmo de búsqueda binaria siempre típico.

Cualquier cosa que tenga una jerarquía. Por ejemplo, enumerar todos los empleados debajo de su jefe.

La recursión encuentra sus fundamentos en la inducción matemática, y debe ser enseñada como tal.

Definir funciones por inducción puede exponerse claramente con el procesamiento de listas. Hay muchas cosas que decir sobre fold por ejemplo.

Luego, pasar a los árboles.

No es C++, obviamente, pero el concepto es sonido:

PHP atravesando recursivamente arrays multidimensionales anidados:

public function recurse_me($collection) {
    foreach ($collection as $value) {
        if (is_array($value)) {
            $this->recurse_me($value);
        } else {
            // process value.
        }
    }
}

Recuerdo que yo entendírecursión escribiendo un programa, que busca escaleras de palabras. En un diccionario.

El ejemplo académico es el factorial

N!

Cálculo. En la vida real, obtienes libros de matemáticas.

Hay algoritmos de ordenación que se basan en la recursión.

Y luego, está la búsqueda binaria que se implementa con recursión.

El triángulo de Pascal

Heap sort es también un buen ejemplo. Puedes leer sobre ello en "Introducción a los algoritmos" de Cormen, Rivest y otros. Gran libro, espero que encuentres un montón de interesante allí.

Muchas operaciones en estructuras de tipo nodo vinculado pueden ser recursivas. Otros han mencionado BSTs, pero si no quieres tener que explicar cuáles son, considera buscar el valor más alto en una lista lineal sin clasificar:

int MaxValue(Node node)
{
    if (node == null)
        return 0;

    if (node.Next == null)
        return node.Value;

    int maxNext = MaxValue(node.Next);
    return node.Value > maxNext ? node.Value : maxNext;
}

Las listas (en este caso, las listas enlazadas) son muy fáciles de explicar en términos del mundo real; su audiencia ni siquiera tiene que tener un fondo de programación. Simplemente puede describirlo como un grupo de cuadros sin clasificar, o una lista de números.