Imagen Escrita: Recursividad

De Casiopea

Recurrencia, recursión o recursividad es la forma en la cual se especifica un proceso basado en su propia definición. Siendo un poco más precisos, y para evitar el aparente círculo sin fin en esta definición:

Un problema que pueda ser definido en función de su tamaño, sea este N, pueda ser dividido en instancias más pequeñas (< N) del mismo problema y se conozca la solución explícita a las instancias más simples, lo que se conoce como casos base, se puede aplicar inducción sobre las llamadas más pequeñas y suponer que estas quedan resueltas.

En programación, una función recursiva debe incorporar un mecanismo de escape que limite su recursividad para evitar el problema de parada o de incomputabilidad.

Ejemplos

Función Inicial no Recursiva


void setup() {
  size(700, 500);
  smooth();
  background(255);
}

void drawY(float x, float y, float big) {

  pushMatrix();
  {
    translate(x, y);               // redefino el origen
    line(0, 0, 0, -big/2);         // tronco
    line(0, -big/2, -big/2, -big); // brazo izquierdo
    line(0, -big/2, big/2, -big);  // brazo derecho
  }
  popMatrix();
}

void draw() {                      // debo dejar la función "draw"
                                   // para que corra el motor
}

void mouseReleased() {
  drawY(mouseX, mouseY, mouseX);   // dibuja en la la posición del mouse
}                                  // el tamaño queda definido por la posción X

Función Recursiva


void setup() {
  size(700, 500);
  smooth();
  background(255);
}

void drawTree(float x, float y, float big, int levels) {
  pushMatrix();
  {
    translate(x, y);

    line(0, 0, 0, -big/2);         // tronco
    line(0, -big/2, -big/2, -big); // brazo izquierdo
    line(0, -big/2, big/2, -big);  // brazo derecho

    // recursividad
    if (levels > 0) {
      drawTree(-big/2, -big, big*0.8, levels - 1); // Y izquierda
      drawTree(big/2, -big, big*0.8, levels - 1);  // Y derecha
    }
  }
  popMatrix();
}

void draw() {
}

void mouseReleased() {
  drawTree(mouseX, mouseY, random(20, 100), round(random(3, 6)));
}