la recursión es el proceso de definir un problema (o la solución a un problema) en términos de (una versión más simple de) sí mismo.

por ejemplo, podemos definir la operación «Encuentra tu camino a casa» como:

  1. Si estás en casa, deja de moverte.

  2. da un paso hacia casa.

  3. «Encuentra tu camino a casa».

Aquí la solución para encontrar el camino a casa es de dos pasos (tres pasos). Primero, no vamos a casa si ya estamos en casa., En segundo lugar, hacemos una acción muy simple que hace que nuestra situación sea más fácil de resolver. Finalmente, rehacemos todo el algoritmo.

el ejemplo anterior se llama recursión de cola. Aquí es donde la última sentencia llama al algoritmo recursivo. La recursión de cola se puede traducir directamente en bucles.

¿Cómo escribirías un «algoritmo» recursivo para encontrar el cuadrado del Templo?

otro ejemplo de recursión sería encontrar el valor máximo en una lista de números. El valor máximo en una lista es el primer número o el mayor de los números restantes., Así es como escribiríamos el pseudocódigo del algoritmo:

partes de un algoritmo recursivo

todos los algoritmos recursivos deben tener lo siguiente:

  1. caso Base (es decir, cuándo detenerse)

  2. trabajar hacia el caso Base

  3. llamada recursiva (es decir, llamarnos a nosotros mismos)

el «trabajo hacia el caso base» es donde hacemos el problema más simple (por ejemplo, dividir la lista en dos partes, cada una más pequeña que la original). La llamada recursiva, es donde usamos el mismo algoritmo para resolver una versión más simple del problema., El caso base es la solución al problema» más simple » posible (por ejemplo, el caso base en el problema ‘encontrar el número más grande en una lista’ sería si la lista tuviera solo un número… y por definición si solo hay un número, es el más grande).

ejemplo Simple: agregue tres números

agregar tres números es equivalente a agregar los dos primeros números y luego agregar estos dos números nuevamente.

(Nota, en Matlab, se puede llamar a una función sin todos los argumentos. La función nargin le dice al ordenador cuántos valores se especificaron., Por lo tanto add_numbers(1) tendría un nargin de 1; add_numbers(1,1) tendría un nargin de 2; add_numbers(1,1,1) tendría un nargin de 3.)

identificar las 3 partes del algoritmo recursivo:

todo algoritmo recursivo debe tener las siguientes tres etapas:

por qué funciona la recursión

en un algoritmo recursivo, la computadora «recuerda» cada estado anterior del problema. Esta información es » retenida «por la computadora en la» pila de activación » (es decir, dentro de cada espacio de trabajo de funciones).

Cada función tiene su propio espacio de trabajo por llamada de la función.,

ejemplo de laberinto:

considere una cuadrícula rectangular de habitaciones, donde cada habitación puede o no tener puertas en los lados Norte, Sur, Este y Oeste.

¿Cómo encontrar la manera de salir de un laberinto? Aquí hay un posible «algoritmo» para encontrar la respuesta:

para cada puerta en la habitación actual, si la puerta conduce a la salida, tome esa puerta.

el» truco » aquí es, por supuesto, ¿cómo sabemos si la puerta conduce a una habitación que conduce a la salida? La respuesta es que no lo hacemos, pero podemos dejar que la computadora lo averigüe por nosotros.

¿Cuál es la parte recursiva del algoritmo anterior?, Es la «puerta conduce fuera del laberinto». ¿Cómo sabemos si una puerta sale del laberinto? Lo sabemos porque dentro de la habitación de al lado (pasando por la puerta), hacemos la misma pregunta, ¿cómo salimos del laberinto?

lo que pasa es que el ordenador «recuerda» todos los «qué pasaría si». ¿Qué pasa si tomo la primera puerta, Qué pasa si tomo la segunda puerta, Qué pasa si tomo la puerta de al lado, etc. Y para cada puerta posible por la que se puede mover, la computadora recuerda esos qué pasaría si, y para cada puerta después de eso, y después de eso, etc, hasta que se encuentre el final.

Aquí hay una implementación de código cercana a la Real.,

Pregunta: ¿Cuál es el caso base anterior?

respuesta: (Esa fue una pregunta capciosa) no hay ningún caso base en el código. Es necesario comprobar al principio si la habitación es la salida. Si lo es, ¡no hay recursión! 

  function success = find_way_out( maze, room ) if room is exit → return true room ← mark as visited % rest of code ... end

pregunta: ¿Cómo marca la habitación como visitada?

Respuesta: Hay varias técnicas. Si la habitación es una estructura (u objeto), puede agregar la dirección del campo visitado a la habitación. (por ejemplo, habitación.visited = true;) si no está utilizando objetos, podría tener una matriz de banderas booleanas que sea del mismo tamaño / forma que el laberinto y usar estos valores.,

pregunta: ¿hay otros problemas con el algoritmo anterior?

respuesta: La respuesta a eso se puede encontrar pensando en la siguiente pregunta: ¿Qué pasaría si el laberinto fuera una cuadrícula gigante de habitaciones rectangulares de idéntico tamaño, cada una con puertas en cada pared? Imaginen que van al norte por la primera puerta, luego al este por la puerta de las habitaciones contiguas, luego al sur por la puerta de las habitaciones, y luego al oeste por la puerta de las habitaciones. ¿Dónde acabará? ¡De vuelta a donde empezaste! Peor aún, es posible que continúe haciendo este bucle para siempre. ¿Cómo resolvería un intrépido aventurero este problema?,

una respuesta a eso es usar un pedazo de tiza y poner una X grande en el piso de cada habitación que entras. Por lo tanto, cuando vuelves a una habitación con una X en el suelo, sabes que no necesitas entrar. En el caso del programa, se debe usar una bandera booleana «visto» o «visitado». Cada habitación tiene una bandera. Cada habitación comienza con la bandera que se establece en false. Cuando visitas una habitación, pones la bandera en true., Finalmente, en el» caso base»tiene una línea como: 

  function success = find_way_out( maze, room ) % exit chack if room is visited → return false % rest of code ... end

la recursión se puede aplicar igualmente bien a los algoritmos informáticos:

algunos ejemplos relacionados con la computadora incluyen: agregar una lista de números, calcular la secuencia de Fibonacci, calcular un Factorial y Sudoku.

bucles y recursión de cola

algunos algoritmos recursivos son muy similares a los bucles. Estos algoritmos se llaman «cola recursiva» porque la última instrucción en el algoritmo es «reiniciar» el algoritmo. Los algoritmos recursivos de cola se pueden traducir directamente en bucles.