¿Cuándo usar la recursividad?

¿Cuándo son algunas instancias (relativamente) básicas (piense en estudiantes de CS de primer año de nivel universitario) cuando uno usaría la recursividad en lugar de solo un bucle?

He enseñado C ++ a estudiantes universitarios durante aproximadamente dos años y he cubierto la recursividad. Desde mi experiencia, sus preguntas y sentimientos son muy comunes. En el extremo, algunos estudiantes ven la recursividad como difícil de entender, mientras que otros quieren usarla para casi todo.

Creo que Dave lo resume bien: úsalo donde sea apropiado. Es decir, úselo cuando se sienta natural. Cuando enfrente un problema en el que encaja bien, lo más probable es que lo reconozca: parecerá que ni siquiera puede encontrar una solución iterativa. Además, la claridad es un aspecto importante de la programación. Otras personas (¡y usted también!) Deberían poder leer y comprender el código que produce. Creo que es seguro decir que los bucles iterativos son más fáciles de entender a primera vista que la recursividad.

No sé qué tan bien conoce la programación o la informática en general, pero creo firmemente que no tiene sentido hablar sobre funciones virtuales, herencia o sobre conceptos avanzados aquí. A menudo he comenzado con el ejemplo clásico de calcular los números de Fibonacci. Encaja bien aquí, ya que los números de Fibonacci se definen de forma recursiva . Esto es fácil de entender y no requiere ninguna suposición características de la lengua. Después de que los estudiantes hayan adquirido una comprensión básica de la recursividad, hemos analizado nuevamente algunas funciones simples que hemos desarrollado anteriormente. Aquí hay un ejemplo:

¿Una cadena contiene un carácter ?$x$

Así es como lo hicimos antes: iterar la cadena y ver si algún índice contiene .$x$

bool find(const std::string& s, char x)
{
   for(int i = 0; i < s.size(); ++i)
   {
      if(s[i] == x)
         return true;
   }

   return false;
}

La pregunta es entonces, ¿ podemos hacerlo recursivamente? Claro que podemos, aquí hay una manera:

bool find(const std::string& s, int idx, char x)
{
   if(idx == s.size())
      return false;

   return s[idx] == x || find(s, ++idx);
}

La siguiente pregunta natural es, entonces, ¿deberíamos hacerlo así? Probablemente no. ¿Por qué? Es más difícil de entender y es más difícil de encontrar. Por lo tanto, también es más propenso a errores.

Las soluciones a algunos problemas se expresan de forma más natural mediante la recursividad.

Por ejemplo, suponga que tiene una estructura de datos de árbol con dos tipos de nodos: hojas, que almacenan un valor entero; y ramas, que tienen un subárbol izquierdo y derecho en sus campos. Suponga que las hojas están ordenadas, de modo que el valor más bajo está en la hoja más a la izquierda.

Supongamos que la tarea es imprimir los valores del árbol en orden. Un algoritmo recursivo para hacer esto es bastante natural:

class Node { abstract void traverse(); }
class Leaf extends Node { 
  int val; 
  void traverse() { print(val); }
} 
class Branch extends Node {
  Node left, right;
  void traverse() { left.traverse(); right.traverse(); }
}

Escribir código equivalente sin recursión sería mucho más difícil. ¡Intentalo!

En términos más generales, la recursividad funciona bien para algoritmos en estructuras de datos recursivos como árboles, o para problemas que naturalmente pueden dividirse en subproblemas. Echa un vistazo, por ejemplo, divide y vencerás algoritmos .

Si realmente desea ver la recursividad en su entorno más natural, entonces debería mirar un lenguaje de programación funcional como Haskell. En dicho lenguaje, no existe una construcción en bucle, por lo que todo se expresa mediante recursividad (o funciones de orden superior, pero esa es otra historia, una que también vale la pena conocer).

Tenga en cuenta también que los lenguajes de programación funcionales realizan una recursión de cola optimizada. Esto significa que no establecen un marco de pila a menos que no lo necesiten --- esencialmente, la recursión se puede convertir en un bucle. Desde una perspectiva práctica, puede escribir código de manera natural, pero obtener el rendimiento del código iterativo. Para el registro, parece que los compiladores de C ++ también optimizan las llamadas de cola , por lo que no hay una sobrecarga adicional de usar la recursividad en C ++.

De alguien que prácticamente vive en la recursión , intentaré arrojar algo de luz sobre el tema.

Cuando se lo presenta por primera vez a la recursión, aprende que es una función que se llama a sí misma y se demuestra básicamente con algoritmos como el recorrido del árbol. Más adelante encontrará que se usa mucho en programación funcional para lenguajes como LISP y F #. Con el F # que escribo, la mayoría de lo que escribo es recursivo y coincidencia de patrones.

Si aprende más sobre la programación funcional como F #, aprenderá que las listas F # se implementan como listas enlazadas individualmente, lo que significa que las operaciones que acceden solo al encabezado de la lista son O (1), y el acceso al elemento es O (n). Una vez que aprende esto, tiende a recorrer los datos como una lista, construyendo una nueva lista en orden inverso y luego invirtiendo la lista antes de regresar de la función que es muy efectiva.

Ahora, si comienza a pensar en esto, pronto se dará cuenta de que las funciones recursivas empujarán un marco de pila cada vez que se realiza una llamada a la función y pueden causar un desbordamiento de la pila. Sin embargo, si construye su función recursiva para que pueda realizar una llamada de cola y el compilador admite la capacidad de optimizar el código para la llamada de cola. es decir .NET OpCodes.Tailcall Field no provocará un desbordamiento de la pila. En este punto, comienza a escribir cualquier bucle como una función recursiva, y cualquier decisión como una coincidencia; los días de ify whileahora son historia.

Una vez que te mueves a AI usando el retroceso en idiomas como PROLOG, entonces todo es recursivo. Si bien esto requiere pensar de una manera bastante diferente del código imperativo, si PROLOG es la herramienta adecuada para el problema, lo libera de la carga de tener que escribir muchas líneas de código y puede reducir drásticamente la cantidad de errores. Ver: cliente de Amzi eoTek

Para volver a su pregunta de cuándo usar la recursividad; Una forma en que miro la programación es con hardware en un extremo y conceptos abstractos en el otro extremo. Cuanto más cercano al hardware está el problema, más pienso en lenguajes imperativos ify while, cuanto más abstracto es el problema, más pienso en lenguajes de alto nivel con recursividad. Sin embargo, si comienza a escribir código de sistema de bajo nivel y tal, y desea verificar que sea válido, entonces encontrará soluciones útiles como demostradores de teoremas , que dependen en gran medida de la recursividad.

Si miras a Jane Street , verás que usan el lenguaje funcional OCaml . Si bien no he visto ninguno de sus códigos, al leer sobre lo que mencionan sobre su código, están pensando de manera recursiva.

EDITAR

Como está buscando una lista de usos, le daré una idea básica de qué buscar en el código y una lista de usos básicos que se basan principalmente en el concepto de catamorfismo que está más allá de lo básico.

Para C ++: si define una estructura o una clase que tiene un puntero a la misma estructura o clase, entonces se debe considerar la recursividad para los métodos transversales que usan los punteros.

El caso simple es una lista unidireccional vinculada. Procesaría la lista comenzando en la cabeza o la cola y luego atravesaría recursivamente la lista utilizando los punteros.

Un árbol es otro caso en el que a menudo se usa la recursividad; tanto que si ves un recorrido del árbol sin recurrencia, deberías empezar a preguntarte por qué. No está mal, pero es algo que debe tenerse en cuenta en los comentarios.

Los usos comunes de la recursividad son:

• clasificación
• buscando
• mapa
• doblez
• filtrar

Para darle un caso de uso que sea menos arcano que los que se dan en las otras respuestas: la recursividad se mezcla muy bien con las estructuras de clase tipo árbol (orientadas a objetos) que se derivan de una fuente común. Un ejemplo de C ++:

class Expression {
public:
    // The "= 0" means 'I don't implement this, I let my subclasses do that'
    virtual int ComputeValue() = 0;
}

class Plus : public Expression {
private:
    Expression* left
    Expression* right;
public:
    virtual int ComputeValue() { return left->ComputeValue() + right->ComputeValue(); }
}

class Times : public Expression {
private:
    Expression* left
    Expression* right;
public:
    virtual int ComputeValue() { return left->ComputeValue() * right->ComputeValue(); }
}

class Negate : public Expression {
private:
    Expression* expr;
public:
    virtual int ComputeValue() { return -(expr->ComputeValue()); }
}

class Constant : public Expression {
private:
    int value;
public:
    virtual int ComputeValue() { return value; }
}

El ejemplo anterior utiliza la recursividad: ComputeValue se implementa de forma recursiva. Para que el ejemplo funcione, utiliza funciones virtuales y herencia. No sabe exactamente cuáles son las partes izquierda y derecha de la clase Plus, pero no le importa: es algo que puede calcular su propio valor, que es todo lo que necesita saber.

La ventaja crucial del enfoque anterior es que cada clase se encarga de sus propios cálculos . Se separan por completo las diferentes implementaciones de todas las subexpresiones posibles: no tienen conocimiento del funcionamiento del otro. Esto facilita el razonamiento sobre el programa y, por lo tanto, hace que el programa sea más fácil de comprender, mantener y ampliar.

El primer ejemplo utilizado para enseñar la recursividad en mi clase de programación inicial fue una función para enumerar todos los dígitos en un número por separado en orden inverso.

void listDigits(int x){
     if (x <= 0)
        return;
     print x % 10;
     listDigits(x/10);
}

O algo así (voy de memoria aquí y no estoy probando). Además, cuando ingrese a clases de nivel superior, usará la recursividad MUCHO, especialmente en algoritmos de búsqueda, algoritmos de clasificación, etc.

Por lo tanto, puede parecer una función inútil en el lenguaje ahora, pero es muy muy útil a largo plazo.