Cómo identificar la recursividad en un problema de programación

Muchas gracias por A2A.

¡¡¡¡¡¡¡¡ALERTA!!!!!!!!
Este artículo puede ser un poco aburrido, pero obtendrá la esencia de la recurrencia, estoy seguro de eso.

Permítame darle una explicación detallada de esto, comenzando por lo que realmente significa recursividad y luego pasando al tema en cuestión, que es cómo identificar la recursividad en un problema de programación. La recursión básicamente significa definir un problema en términos de sí mismo.

La mayoría de las estrategias algorítmicas utilizadas para resolver problemas de programación tienen contrapartes fuera del dominio de la informática. Cuando realiza una tarea repetidamente, está utilizando la iteración. Cuando tomas una decisión, ejerces control condicional. Debido a que estas operaciones son familiares, la mayoría de las personas aprenden a usar las declaraciones de control para, while y
si con relativamente pocos problemas. Pero para resolver algunos de los sofisticados problemas en la programación, necesitamos el poder de la recursividad.

El mejor ejemplo para explicar el uso de la recursión es el problema factorial y la serie de Fibonacci.

************************ FACTORIAL ************************* ****

Deje que el factorial de un número ‘n’ se pueda definir como

¡norte! = n * (n-1) !. Deje que la función que calcula el factorial de un número n se defina por F (n). Entonces puedo escribir la fórmula anterior como
F (n) = n * F (n-1) . Ahora esto aquí es claramente, RECURSIÓN. Entonces, todo lo que tenemos que hacer ahora es encontrar F (n-1) que puede desglosarse aún más en
F (n-1) = n-1 * F (n-2). Ahora esto continuará hasta que el valor de n se convierta en 0 y todos sepamos que 0. es 1. Entonces este se convierte en el caso base para la recursividad. El código para el problema es el siguiente.

  int factorial (int num)
 {
       si (num == 0)
         retorno 1;
     
       más
         return num * factorial (num - 1);
 }

*********************** NÚMERO DE FIBONACCI *********************

Ahora considerando otro problema popular que puede resolverse por recursión y que es encontrar el enésimo número de Fibonacci . La serie de Fibonacci es 1 1 2 3 5 8 13 21 … es decir, el número actual es la suma de dos anteriores.
Definamos la función que descubre el enésimo número de Fibonacci por F (n). Entonces, la función puede desglosarse como

F (n) = F (n-1) + F (n-2)

Ahora, de nuevo, esto es una recursión porque dividimos el problema cada vez más grande en un problema más pequeño que tiene las mismas características pero es más fácil de resolver ya que es más pequeño. Aquí nuevamente, podemos ver el caso base para el problema. cuando n = 1 o cuando n = 2 tenemos F (n) = 1. Este es un árbol de recursión que obtenemos para el problema de Fibonacci para un valor dado de n.
*********************** MINESWEEPER ************************

Otro problema interesante que me encanta resolver por recurrencia es el problema del buscaminas. Ahora, la lógica de “hacer clic” depende de lo que se haga en la pregunta (como el número mínimo de movimientos, etc.), pero una vez que haya seleccionado una casilla, las casillas restantes se abrirán “RECURSIVAMENTE”. Me gusta llamar a esto como operación de inundación. La operación general del juego es: –

Puede hacer clic en cualquier celda para revelarlo. Si la celda revelada contiene una mina, entonces el juego termina y tú pierdes. De lo contrario, la celda revelada contendrá un dígito entre 0 y 8, inclusive, que corresponde al número de celdas vecinas que contienen minas. Dos celdas son vecinas si comparten una esquina o un borde. Además, si la celda revelada contiene un 0, entonces todos los vecinos de la celda revelada también se revelan automáticamente, de forma recursiva. Cuando se revelan todas las celdas que no contienen minas, el juego termina y tú ganas.

Ahora supongamos que hace clic en un cuadro con dimensiones (i, j). Entonces, lo que debemos hacer es abrir este cuadro y verificar de forma recursiva sus 8 vecinos

(i + 1, j)
(i + 1, j + 1)
(i + 1, j-1)
(i-1, j)
(i-1, j + 1)
(i-1, j-1)
(i, j-1)
(i, j + 1)
también para ver si se pueden abrir o no. El punto a tener en cuenta aquí es que en ningún momento debemos ir más allá del límite que se nos ha dado para la cuadrícula.

*********************** Knight’s tour ************************* ******

Este es otro problema clásico que se puede resolver mediante recursividad y retroceso. El problema del recorrido del caballero se define de la siguiente manera

El recorrido de un caballero es una secuencia de movimientos de un caballero en un tablero de ajedrez de modo que el caballero visita cada casilla solo una vez. Si el caballero termina en una casilla que es el movimiento de un caballero desde la casilla inicial (de modo que pueda recorrer el tablero nuevamente de inmediato, siguiendo el mismo camino), el recorrido está cerrado, de lo contrario está abierto.

Ahora, una vez más, este problema se puede resolver mediante recursividad. Aquí hay un pseudocódigo autoexplicativo para el mismo.

  Si se visitan todos los cuadrados 
       imprime la solución
 Más
 a) Agregue uno de los siguientes movimientos al vector de solución y 
 Verifique recursivamente si este movimiento lleva a una solución. 
 (Un Caballero puede hacer un máximo de ocho movimientos. Elegimos uno de los 8 movimientos en este paso). 

  b) Si el movimiento elegido en el paso anterior no conduce
  a una solución, luego elimine este movimiento de la solución
  vector e intente otros movimientos alternativos.    

 c) Si ninguna de las alternativas funciona, devuelve falso
 (Devolver falso eliminará el elemento agregado previamente
  en recursividad y si la llamada inicial devuelve falso
  de recursividad entonces "no existe solución").

****************** El problema clásico del laberinto ******************

Si tienes espacio para un problema más, ¡entonces lee en mate! Este es uno de los mejores dominios problemáticos manejados por recursividad. El laberinto se puede definir de cualquier manera, pero el problema finalmente se reduce a que, dado un laberinto, ¿debemos determinar si existe o no un camino? Entonces, una vez más, cambiamos a la recursividad y probamos todos los caminos posibles y usamos el retroceso y la poda en el camino y así es como determinamos si el laberinto dado es solucionable o no.

Feliz codificación !!!
Espero que esto ayude. 🙂

Aakash Anuj ha escrito una excelente discusión sobre cómo se ve la recursión y no repetiré sus puntos innecesariamente. Pero sí quiero tomarme un tiempo para explicar un problema con la redacción de su pregunta.
La recursión es una de las muchas formas de resolver problemas computacionales.
¿Es un método poderoso para resolver problemas? Sí, tanto es así que si alguna vez llega a aprender un lenguaje puramente funcional como LISP (o sus descendientes), verá que todos los problemas se resuelven mediante la recursión; por ejemplo, el problema de encontrar el último elemento de una lista usa la recursividad. Ahora, si está acostumbrado a C o Java, simplemente almacenará los datos en una matriz y usará un índice para obtener el último elemento. Es muy improbable que intentes la recursividad. Pero un programador de LISP encontrará que es natural usar la recursividad.
Como señaló Aakash Anuj, siempre hay soluciones alternativas que no utilizan la recursividad. Mencionó la programación dinámica. También encontrará libros de texto de ciencias de la computación que explican cómo la recursión puede ser reemplazada por soluciones alternativas utilizando pilas y / o iteraciones.
Lo que quiero decir es que no hay recurrencia en ningún problema de programación. Es simplemente una estrategia para resolver un problema de programación.

La recursión es una forma de iteración. Un problema que parece complejo debe resolverse con una solución más simple y recursiva.

Algunas leyes impulsan la creación de algoritmos recursivos:

1. Un algoritmo recursivo debe tener un caso base. Esto, el caso base es una condición que permite que el algoritmo “deje de recurrir”, es decir, un problema lo suficientemente pequeño como para resolverlo directamente. Sin embargo, en un problema de recursión puede haber múltiples casos base. Debe buscar un caso base en el problema.
2. Un algoritmo recursivo debe cambiar su estado y moverse hacia el caso base .

Por ejemplo, en el problema de exploración del laberinto, digamos que un mouse explora un laberinto, podría haber los siguientes casos básicos:

• El ratón chocó contra una pared. Dado que un cuadrado está ocupado por una pared, no se pueden realizar más exploraciones.
• El mouse ha encontrado un cuadrado que ya ha sido explorado.
• El mouse ha encontrado una salida.
• Se ha explorado un cuadrado en las 4 direcciones, sin éxito.

3. Finalmente, el algoritmo recursivo debe llamarse recursivamente.

Si puede visualizar una solución / algoritmo para el problema que pueda ajustarse a las leyes anteriores, entonces ha identificado la recursividad después de comprender las diversas condiciones del problema.