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 |
int static Factorial(int n){
si (n > 1)
devuelve n * Factorial(n - 1);
de lo contrario devuelve 1;
}
|
int x = 1;
para (int i = 2; i <= n; i++)
x = x * yo;
Console.WriteLine("%d", 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.
Problem
Defina una función
K(n) que devuelva el número de dígitos en un número natural dado
n como
\(\begin{ecuación*} K(n) = \begin{casos} 1 &\text{if n < 10}\\ K(n / 10) + 1 &\text{si n >= 10} \end{casos} \end{ecuación*}\).
Escribe una función recursiva para calcular el número de dígitos en un número natural
n usando la proporción anterior.
Запрещенные операторы: for;while;until