Un procedimiento o función puede contener una llamada a otro procedimiento dentro de él. Incluso, la subrutina puede llamarse a sí misma. En este caso, a la computadora no le importa. También, como siempre, ejecuta consistentemente los comandos que conoce de arriba a abajo.
Si recuerdas las matemáticas, ahí podrás conocer el principio de inducción matemática. Es el siguiente:
algún enunciado es verdadero para todo n natural si
1. es válido para n = 1 y
2. de la validez del enunciado para cualquier n = k natural arbitrario se sigue que es verdadero para n = k+1.
En programación, esta técnica se llama recursión
La recursividad es una forma de definir un conjunto de objetos en términos del propio conjunto, basándose en casos base simples dados.
Recursivo también se denominará un procedimiento (función) que se llama a sí mismo directamente o a través de otros procedimientos y funciones
Un ejemplo de un procedimiento recursivo:
vacío Rec(int a)
{
si (a>0) Rec(a-1);
cout << a;
}
Esquemáticamente, el trabajo de recursividad se puede representar mediante un diagrama de flujo
Se ejecuta el procedimiento Rec() con el parámetro 3. Luego, dentro del procedimiento con el parámetro 3, se llama al procedimiento con el parámetro 2, y así sucesivamente, hasta que se llama al procedimiento con el parámetro 0. Cuando el procedimiento con el parámetro 0 se llama al parámetro 0, la llamada recursiva ya no ocurrirá y el procedimiento con el parámetro 0 imprimirá el número 0 y terminará. Luego, el control se transfiere nuevamente al procedimiento con el parámetro 1, también termina su trabajo imprimiendo el número 1, y así sucesivamente. antes del procedimiento con el parámetro 3.
Todos los procedimientos llamados se almacenan en la memoria hasta que completan su trabajo. El número de procedimientos concurrentes se llama profundidad de recurrencia.
|
Recursión. Simulación de bucle
Hemos visto que la recursividad es la ejecución repetida de instrucciones contenidas en una subrutina. Y esto, a su vez, es similar al trabajo del ciclo. Hay lenguajes de programación en los que la construcción de bucle está completamente ausente, por ejemplo, Prolog.
Intentemos simular el trabajo del bucle for.
El bucle for contiene una variable de contador de pasos. En una subrutina recursiva, dicha variable se puede pasar como parámetro.
// Procedimiento LoopImitation() con dos parámetros.
// Primer parámetro – contador de pasos, segundo parámetro – número total de pasos.
void LoopImitation(int i, int n)
{
cout << "Hola N" << yo << fin; // Operador a repetir para cualquier valor de i
if (i < n) // Hasta que el contador de bucle sea igual a n,
{ // llama a una nueva instancia del procedimiento, con el parámetro i+1 (pasa al siguiente valor i).
LoopImitation(i + 1, n);
}
}
|
Recursión e iteración
Para comprender la recursividad, debe comprender la recursividad...
Iteración en programación - un pasode un proceso cíclico de procesamiento de datos.
A menudo, los algoritmos iterativos en el paso actual (iteración) utilizan el resultado de la misma operación o acción calculada en los pasos anteriores. Un ejemplo de tales cálculos es el cálculo de las relaciones de recurrencia.
Un ejemplo simple de un valor recursivo es el factorial: \(N!=1 \cdot 2 \cdot 3 \cdot \ ... \ \cdot N\).
El cálculo del valor en cada paso (iteración) es \(N=N \cdot i\) . Al calcular el valor de \(N\), tomamos el valor ya almacenado \(N\).< br />
El factorial de un número también se puede describir usando la fórmula recurrente:
\(\begin{ecuación*} n!= \begin{casos} 1 &\text{n <= 1,}\\ (n-1)! \cdot n &\text{n > 1.} \end{casos} \end{ecuación*}\)
Puede notar que esta descripción no es más que una función recursiva.
Aquí, la primera línea ( \(n <= 1\)) es el caso base (condición de terminación de recursividad) y la segunda línea es la transición al siguiente paso. < br />
| Función factorial recursiva |
Algoritmo iterativo |
|
factorial int(int n)
{
si (n > 1)
devuelve n * Factorial(n - 1);
de lo contrario devuelve 1;
}
|
x = 1;
para (i = 2; i <= n; i++)
x = x * yo;
cout << x;
|
Debe entenderse que las llamadas a funciones implican una sobrecarga adicional, por lo que un cálculo factorial no recursivo será un poco más rápido.
Conclusión: donde puede escribir un programa con un algoritmo iterativo simple, sin recursión, entonces necesita escribir sin recursión. Pero aun así, existe una gran clase de problemas en los que el proceso computacional se implementa solo mediante recursividad.
Por otro lado, los algoritmos recursivos suelen ser más comprensibles.
Tarea
En el alfabeto de la lengua de la tribu "Tumba-Yumba"; cuatro letras: "K", "L", "M" y "N". Debe mostrar todas las palabras que constan de n letras que se pueden construir a partir de las letras de este alfabeto.
El problema es un problema normal de fuerza bruta que se puede reducir a un problema más pequeño.
Sustituiremos secuencialmente las letras por la palabra.
La primera posición de una palabra puede ser una de las 4 letras del alfabeto (K. L, M, N).
Pongamos la letra K primero. Luego, para obtener todas las variantes con la primera letra K, debe enumerar todas las combinaciones posibles de letras en las posiciones restantes de n - 1 y así sucesivamente. (ver imagen).
 Así, el problema se reduce a resolver cuatro problemas de longitud n - 1.
Iterar sobre n caracteres recursivamente
w[0]='K'; // iterar sobre los últimos caracteres L-1
w[0]='L'; // iterar sobre los últimos caracteres L-1
w[0]='M'; // iterar sobre los últimos caracteres L-1
w[0]='N'; // iterar sobre los últimos caracteres L-1
w - una cadena de caracteres que almacena la palabra de trabajo.
Así, tenemos recursividad. Podemos disponer la solución del problema en forma de procedimiento recursivo.
¿Queda por determinar cuándo terminará la recursividad? Cuando todos los caracteres están configurados, es decir, el número de caracteres configurados es n. En este caso, debe mostrar la palabra resultante en la pantalla y salir del procedimiento.
El programa C++ se verá así.
#incluir<iostream>
utilizando el espacio de nombres estándar;
void TumbaWords( cadena A, cadena &w, int N )
// w - parámetro modificable (resultado de cadena)
// Al procedimiento TumbaWords se le pasa el alfabeto como cadena de caracteres,
// la palabra palabra y el número de caracteres ya establecidos (antes de – 0).
{
ent yo;
if (N == w.tamaño())
{
// si ya se han establecido todos los caracteres en la palabra,
// entonces es necesario generar una cadena y finalizar el procedimiento
cout << w<< fin;
devolver;
}
for ( i = 1; i < A.tamaño(); i ++ )
{
// si la condición anterior es falsa (es decir, no todos los caracteres están espaciados,
// luego en el bucle repasamos todos los caracteres del alfabeto y
// coloca alternativamente el carácter en el primer espacio libre
w[N] = A[i];
TumbaPalabras ( A, w, N+1 );
}
}
principal()
{
interno;
palabra de cadena;
interno;
cin>> norte;
palabra.redimensionar(n); // aumenta la cadena al tamaño n
TumbaPalabras( "KLMN", palabra, 0 );
}
TENGA EN CUENTA que w es un parámetro mutable (cadena de resultado)!
|
|