Aquí hay un artículo que tengo en mi blog personal. Puedo compartir el enlace, pero no estoy tan seguro si esto rompe las reglas de publicación, así que estoy copiando y pegando.
¿Qué es la recursión? Por favor tengan paciencia conmigo
Este será un artículo breve y técnico, así que tengan paciencia con mi mal inglés y mi estilo de escritura. El idioma también es un medio de comunicación y, a veces, no logra transmitir la comprensión, por lo que voy a volcar el concepto en inglés simple lo mejor que pueda.
Simple pero confuso
La recursión es de hecho un tema confuso (especialmente para los estudiantes) aunque es simple. Los conceptos simples no son necesariamente fáciles de implementar porque depende en qué medida el concepto sigue directamente la forma natural de pensar. Creo que la razón principal por la cual la recursión es confusa es que no sigue una forma natural directa de pensar como el caso en la iteración. Proporcionaré un ejemplo para demostrar el concepto de recursión y espero que ayude a los lectores a dominar la habilidad de pensar de forma recursiva, pero antes de saltar al tema correctamente, definamos más o menos lo que significa una función desde una perspectiva de programación.
Una función es una función
En lenguajes de procedimiento como C o Pascal, el código fuente se compone de funciones o procedimientos. Por otro lado, los lenguajes orientados a objetos como C ++ tienen funciones (llamadas métodos) pero están incrustadas dentro de las definiciones de clase. Independientemente de los detalles de implementación (recursión, iteración, complejidad, rendimiento, etc.), una función no es más que un bloque de código que recibe cero o más parámetros y devuelve algún tipo de salida. Por ejemplo, la siguiente función recibe dos parámetros enteros A y B y devuelve la suma de los dos enteros.
int Sum (int A, int B)
{
devolver A + B;
}
Llamar a esta función es sencillo. Simplemente proporcione la entrada requerida y reciba la salida esperada. En el caso de las funciones recursivas, no es diferente, simplemente llame a una función con la entrada adecuada y reciba algo de salida esperada, lo que lo hace diferente y confuso.
Funciones recursivas
Se debe invocar una función recursiva por primera vez desde la definición de función externa, sin embargo, se sigue llamando desde la definición de función interna hasta que alcanza una condición de detención. Desde la perspectiva de la computadora, si una función se llama a sí misma o llama a otra función, sigue siendo una llamada de función regular siempre que invoque el nombre de función correcto y especifique los parámetros de entrada requeridos.
Divide y conquistaras
Sé que todavía no expliqué la parte confusa, ¿por qué incluso se molestaría en llamar a la función desde su definición en primer lugar? La recursión sigue una técnica de diseño de algoritmo bien conocida llamada divide y vencerás, que significa dividir un problema en subproblemas del mismo tipo o relacionados hasta que el subproblema sea lo suficientemente simple como para ser resuelto directamente. Las soluciones a los problemas secundarios se combinan para dar una solución al problema original. Entonces, ¿cómo divide y vencerás se relaciona con una función que se llama a sí misma? En la primera llamada a la función recursiva, proporciona la entrada a tamaño completo, en el momento en que la función comienza a invocarse, debe proporcionar una entrada de tamaño más pequeño, sigue proporcionando un tamaño más pequeño en cada llamada hasta que la entrada sea lo suficientemente simple como para resolverla. El paso final es combinar todas las soluciones en una única gran solución.
Ejemplo
Admito que todavía estoy hablando de manera abstracta. Las palabras aún están secas, así que intentemos entender la recursividad usando un ejemplo mientras pensamos en voz alta. El ejemplo factorial es excelente, pero creo que suena aburrido encontrar este ejemplo en cada artículo que habla sobre la recursividad. Voy a discutir un ejemplo que es más fácil de resolver usando la iteración, sin embargo, lo resolveremos usando la recursividad para mejorar nuestras habilidades para pensar de forma recursiva.
Considera este ejemplo. Dada una matriz de enteros, encuentre el número máximo en la matriz. Este problema se puede resolver de forma iterativa recorriendo la matriz elemento por elemento y comparando el elemento actual con el máximo actual mientras se actualiza el máximo siempre que el elemento actual sea más grande. Esta es la forma natural de pensar, usted asume que el primer elemento es el máximo y luego verifica cada elemento en la matriz para ver si es más grande o no. Pensar de forma recursiva no sigue una forma tan natural, pero es un poco diferente. ¿Aún recuerdas la técnica de dividir y conquistar? Si es así, eso es recurrencia de una forma u otra. Apliquemos divide y vencerás a este problema.
Una forma de hacerlo es dividir la matriz en dos mitades y luego encontrar el máximo de la primera mitad y luego el máximo de la segunda mitad y luego devolver el máximo más grande (ya que tenemos dos máximos). La primera llamada a la función recursiva opera en toda la matriz, luego las llamadas posteriores operan en mitades de la matriz y así sucesivamente hasta el punto en que operamos en un solo elemento. Considere la siguiente matriz de enteros
4, 3, 1, 7, 2, 8, 6, 10, 5, 9
Comenzamos con una matriz de 10 elementos, luego dos matrices de 5 elementos, luego 4 matrices de 2 o 3 elementos, luego 8 matrices de uno o dos elementos. Como puede ver una vez que la matriz se reduce a una matriz de uno o dos elementos, es muy fácil encontrar el número máximo. Si la matriz tiene solo un elemento, el máximo es el elemento mismo. Si la matriz consta de dos elementos, el máximo es el elemento más grande. Eche un vistazo a la figura a continuación comenzando desde la parte inferior de la rama izquierda del árbol:
7> 2, entonces se toma 7
7> 1, entonces se toma 7
4> 3, entonces se toma 4
7> 4, entonces se toma 7
Luego, desde la parte inferior de la rama derecha del árbol:
9> 5, entonces se toma 9
10> 9, entonces se toma 10
8> 6, entonces se toma 8
10> 8, entonces se toma 10
Y finalmente tomamos el máximo más grande de las ramas izquierda y derecha 10> 7, por lo que 10 es el elemento máximo en la matriz
Basándonos en el ejemplo anterior, intentemos caracterizar la anatomía general de una función recursiva.
- Necesitamos un caso base para la entrada para que la función deje de llamarse más allá de ese punto. En nuestro ejemplo, el caso base es cuando la matriz tiene solo un elemento en ese caso, solo devuelve el elemento en sí como máximo.
- El segundo problema al que debemos prestar atención es que la entrada o el tamaño del problema deben reducirse cada vez que la función se llama a sí misma. En nuestro ejemplo, comenzamos con una matriz completa y luego con media matriz hasta que proporcionamos una matriz que consta de un solo elemento. Si el tamaño de entrada no se reduce, no se alcanzará el caso base, lo que hace que la función recursiva desborde la memoria de la pila.
- Las soluciones deben combinarse para producir la solución final. En nuestro ejemplo, el máximo en el lado izquierdo del árbol de recursión fue 7, mientras que el máximo en el lado derecho del árbol de recursión fue 10. Comparamos esos dos números y devolvemos el más grande.
Apliquemos las reglas anteriores y salgamos con una función recursiva:
int max (int A [], int i, int j)
{
//Caso base
si (i == j)
{
devolver A [i];
}
// Calcular la posición del elemento medio
int m = (i + j) / 2;
// Llamando a la misma función con tamaño reducido
int left_max = max (A, i, m);
int right_max = max (A, m + 1, j);
// Combinando soluciones
if (left_max> right_max)
{
return left_max;
}
más
{
return right_max;
}
}
Como puede ver, acabamos de implementar las tres reglas mencionadas anteriormente. Tenga en cuenta lo siguiente:
- I y J representan índices de matriz inicial y final. La primera vez que llama a la función recursiva, proporciona I = 0 y J = longitud de la matriz
- Una vez que calcule la posición del elemento medio, entonces el índice de inicio I = 0 y J = m para la rama izquierda, mientras que I = m + 1 y J = longitud de la matriz para la rama derecha. Así es como reducimos el tamaño de entrada jugando con los valores de I y J
- Cuando I == J esto significa que estamos apuntando a un único elemento que es el caso base
- Una vez que se calculan los valores máximo izquierdo y derecho, combinamos las dos soluciones devolviendo la más grande.
Así que aquí está el trato. Si desea mejorar sus habilidades de recursividad, entonces necesita practicar más sobre esas reglas. Antes de finalizar este artículo, déjenme ser claro sobre lo siguiente
- La recursión no significa exactamente dividir y conquistar. Es al revés, dividir y conquistar es una técnica de diseño de algoritmos que utiliza la recursividad
- Divide y vencerás se puede usar para diseñar algoritmos rápidos, como la búsqueda binaria y la ordenación por fusión. En nuestro ejemplo, no mejoramos el rendimiento simplemente porque operamos en ambas ramas del árbol. Comparando esto con la búsqueda binaria, en cada llamada a la función recursiva operamos en una rama del árbol
Por lo tanto, tenga en cuenta que el objetivo principal de este artículo es comprender el concepto de recursión, no cómo diseñar algoritmos rápidos. Espero que este artículo sea útil, pero estoy seguro de que no hay nada como practicar
