Recursividad

Primero aprende demostración inductiva en demostraciones

Si estás aquí, es porque ya mas o menos tienes un vago concepto de lo que es una recursividad. Vamos a tratar de aclarar los temas poco a poco.

Primero fantasear, despues delegar y luego ejecutar. Así es como veo la recursividad. Imaginemos que tenemos la ardua labor de llevar 100 costales de cemento de un punto a a un punto b. No te gustaría hacerlo solo; es más, no te gustaría hacer nada. ¿Cómo podemos realizar la labor? Fácil, primero consigues a 10 chalanes, y les encargas lo siguiente: "Tu labor será conseguir 10 chalanes y que cada uno cargue un saco de cemento".

Hasta ahora todo bien, sin embargo te acaban de timar. Si prestas atención a nuestro encargo, veremos que nunca en ningún momento pones a cargar a los chalanes los bultos, entonces haces una modificación: "Si observamos detenidamente nuestro encargo inicial, nos damos cuenta de que nunca especificamos que los chalanes debían cargar los bultos de cemento. Así que, hacemos una modificación y les comunicamos a los chalanes: 'Tu labor será conseguir 10 chalanes y que cada uno cargue un saco de cemento de un punto a otro, asegurándote de que todos los sacos lleguen al destino final'.

Ahora, cada chalán tiene una tarea clara y específica. Pero aquí está la magia de la recursividad: no queremos cargar directamente los 100 sacos nosotros mismos, y tampoco queremos que los 10 chalanes lo hagan uno por uno, ya que eso podría ser ineficiente.

Entonces, recurrimos nuevamente a la delegación y les decimos a los 10 chalanes: 'Ahora, cada uno de ustedes consiga 10 chalanes más y delegue la misma tarea: cargar un saco de cemento de un punto a otro'. Así, la carga se divide aún más, y todos tienen una tarea más manejable.

Este proceso continúa de manera recursiva hasta que llegamos a un nivel donde la tarea es lo suficientemente pequeña y manejable para cada individuo. En última instancia, cada chalán solo tiene que preocuparse por cargar un saco de cemento de un punto a otro.

Finalmente, ejecutamos el plan y observamos cómo se realiza la tarea de manera eficiente gracias a la recursividad y la delegación inteligente. Cada nivel de chalanes se encarga de coordinar a un grupo más pequeño, logrando que los 100 sacos de cemento lleguen a su destino de manera efectiva y sin que tengamos que cargar un solo saco nosotros mismos."

Básicamente eso es un algoritmo Recursivo.

Para hacer un algoritmo recursivo debemos de cumplir ciertas normas:

1. Debe ser posible descomponer el problema original en instancias más simples del mismo problema.

2. Una vez que se ha resuelto cada uno de estos subproblemas más simples, debe ser posible combinar estas soluciones para producir una solución al problema original.

3. A medida que el problema grande se descompone en subproblemas sucesivamente menos complejos, esos subproblemas deben volverse tan simples eventualmente que puedan resolverse sin más subdivisión.

¿Y cómo demostramos su correctitud?

La correctitud de un algoritmo recursivo se verifica demostrando dos propiedades fundamentales: la condición base y la relación recursiva.

A continuación, proporcionaré un ejemplo simple de un algoritmo recursivo junto con su explicación: