Hogar › Internet › Recursiones: ¿qué es? Recursión en programación (ejemplos). PageRank recursivo de Google. Calcular los números de Fibonacci

Recursiones: ¿qué es? Recursión en programación (ejemplos). PageRank recursivo de Google. Calcular los números de Fibonacci

Del latín recursio (retorno). En general, este es el nombre que se le da al proceso de repetir elementos de manera “autosimilar”.

Un ejemplo sorprendente de recursividad son los muñecos nido. Definición recursiva: “una muñeca anidada es una muñeca de madera hueca desmontable que contiene una muñeca más pequeña en su interior”. Esto es recursividad en ruso. Y si no fuera por el límite de las capacidades de los maestros, la matrioska ideal se profundizaría en sí misma hasta el nivel atómico. O incluso más profundo. Lefty simplemente no tenía una mira pequeña lo suficientemente fuerte. El límite superior también es teóricamente ilimitado, pero en nuestro planeta no crecen baobabs de un tamaño adecuado. En general, por razones técnicas, la recursividad debe ser finita.

En programación (como en matemáticas), la recursividad es el proceso en el que una función se llama a sí misma (recursión directa), o llama a la función B desde dentro de la función A, que a su vez contiene una llamada a la función A (recursión indirecta o mutua). Por supuesto, las llamadas recursivas deben tener una condición de salida satisfactoria; de lo contrario, el programa se bloqueará, como en un bucle infinito, pero, a diferencia de un bucle infinito, una recursión infinita colapsará en un desbordamiento de pila.

Ejemplo de recursividad

El ejemplo más molesto de recursividad en la programación matemática es el cálculo factorial. No cambiemos nuestras gloriosas tradiciones. Para los que aún no lo han tomado: N! (factorial N) es el producto de todos los números naturales del uno al N (el factorial de cero es 1).
Puedes multiplicar estúpidamente números del 1 al N en un bucle. O puedes crear una función factorial(n), que contendrá una condición y una llamada a sí misma. Si n es igual a uno, entonces la función devuelve el valor 1; de lo contrario, devuelve el valor de n multiplicado por factorial (n-1).
Dibujar en PHP

Función factorial($n) ( if ($n == 1) ( devuelve 1; ) else ( devuelve intval($n * factorial($n - 1)); ) )

Aplicaciones prácticas de la recursividad

"Bueno, ¿por qué se necesita esto aquí?" - nos preguntará un joven lector impaciente - “Disparates científicos, tedios, factoriales de todo tipo... Pero en la práctica, ¿por qué aplicar esta recursividad?”
“Al ojo morado de la programación web”, responderemos sin dudarlo. Y lo justificaremos de inmediato.

De hecho, existen muchos más usos de la recursividad en la programación web de los que parece. Porque la recursividad es, quizás, la única forma de atravesar cualquier estructura de árbol cuando ni su tamaño ni la profundidad de anidación se conocen de antemano. Por cierto, tampoco es posible construir y recorrer gráficos sin él. Esto es un clásico, caballeros: prueben otra forma de buscar los archivos necesarios en el árbol de directorios de Unix e inmediatamente les quedará claro que sin recursividad no llegarán a ninguna parte.

Intente prescindir de él creando un mapa del sitio con una estructura jerárquica de secciones en forma de listas anidadas. Preferiría ahorcarse antes que construirlo si no sabe de antemano exactamente a cuántos niveles se limita la profundidad de anidación. E incluso si lo sabe, pero intenta hacerlo sin recursividad, entonces, en lugar de una función simple, transparente y a prueba de fallas, construirá un software engorroso "con muletas". Y cuando termine y se seque la frente sudorosa, se dará cuenta de la triste verdad de la vida: si cambia la profundidad del anidamiento, su estructura en expansión dejará de funcionar correctamente instantáneamente. Por lo tanto, es poco probable que pueda utilizarlo en ningún otro lugar.

Recursividad en motores de búsqueda.

Sí, eso es correcto. Los motores de búsqueda tampoco tienen dónde escapar de la recursividad. Desde que se estableció la costumbre de medir la autoridad de un sitio (documento) por el número de enlaces, los motores de búsqueda han caído en una trampa recursiva y los dejan vagar en ella para siempre (este es el sincero deseo del autor). El “peso” del enlace de un sitio se compone de pequeños trozos de “peso” de todos aquellos que enlazan con él. Para calcular este peso de A, al que hacen referencia B, C y D, es necesario calcular su peso, que a su vez es transmitido por todo tipo de otros, cuyo peso también es necesario calcular... y así sucesivamente. en toda la Red tenidos en cuenta en el buscador. Un problema completamente recursivo. Y dices que es una teoría completa. La práctica más real.

PageRank recursivo de Google

Los creadores de Google publicaron hace mucho tiempo su algoritmo básico para calcular el PageRank. Y no importa cómo haya cambiado desde entonces, no importa cuántas mejoras se le hayan agregado, la base sigue siendo la misma. No hay forma de saber cuánto PageRank la página B está transmitiendo como enlace a la página A hasta que contamos cuánto PageRank recibió la página B de todas las demás páginas que enlazan con ella, y eso no se puede saber hasta que cuentemos el PageRank de esas páginas... ¿continuamos? Probablemente ya no sea necesario. Es Su Majestad otra vez recursividad .

Algoritmo recursivo

recursividad- un método para definir una clase de objetos o métodos especificando primero uno o más (generalmente simples) básico casos o métodos, y luego definir a partir de ellos una regla para construir una clase definida que se refiera directa o indirectamente a estos casos base.

En otras palabras, la recursividad es una forma de definir generalmente un objeto o acción a través de sí mismo, utilizando definiciones privadas previamente definidas. La recursividad se utiliza cuando se puede identificar la autosimilitud de un problema.

Ejemplos

Algoritmo para mover la torre, el algoritmo moverá la cantidad requerida de discos de la pirámide "fuente" a la pirámide "tarea" utilizando la pirámide "repuesto".

Si el número de discos es uno, entonces:

Mover el disco del origen al trabajo

De lo contrario:

Mueva recursivamente todos los discos excepto uno desde el origen al repuesto, utilizando el trabajo como repuesto
Mueva el disco restante del origen al trabajo
Mueva todos los discos del stock al trabajo utilizando el origen como stock

Recursión en programación

Funciones

Clase elemento_de_lista ( elemento_de_lista *siguiente; /* referencia al siguiente elemento del mismo tipo */ datos enteros; /* algunos datos */ );

La estructura recursiva de los datos a menudo dicta el uso de la recursividad para procesar los datos.

Recursión en física

Un ejemplo clásico de recursividad infinita son dos espejos colocados uno frente al otro: forman dos pasillos de reflejos que se desvanecen de los espejos.

Otro ejemplo de recursividad infinita es el efecto de la autoexcitación (retroalimentación positiva) en los circuitos de amplificación electrónica, cuando la señal de la salida va a la entrada, se amplifica, regresa a la entrada del circuito y se amplifica nuevamente. Los amplificadores para los que este modo de funcionamiento es estándar se denominan autoosciladores.

Recursión en lingüística

La capacidad de una lengua para generar oraciones y construcciones anidadas. oferta básica el gato se comió el ratón se puede expandir por recursividad como Vanya supuso que el gato se comió al ratón., entonces como Katya sabe que Vanya adivinó que el gato se comió al ratón. etcétera. La recursividad se considera uno de los universales lingüísticos, es decir, es característica de cualquier lengua natural (aunque recientemente la posible ausencia de recursividad en una de las lenguas del Amazonas, la pirahã, señalada por el lingüista D. Everett, ha discutido activamente). La recursividad en lingüística, sus variedades y las manifestaciones más características en el idioma ruso se describen en el artículo de E.A Lodatko “Estructuras lingüísticas recursivas” (ver: Estructuras lingüísticas recursivas)

Citas

Humor

La mayoría de los chistes sobre la recursividad tratan sobre la recursión infinita, que no tiene condición de salida. Dichos famosos: “Para entender la recursividad, primero debes entender la recursividad”, “Para hacer algo, necesitas hacer algo”, “Para preparar una ensalada necesitas: pepinos, tomates, lechuga”. Un chiste muy popular sobre la recursividad, que recuerda a una entrada de diccionario:

Varios relatos de Stanislaw Lem están dedicados a (posibles) incidentes con recursividad infinita:

La historia sobre Ion el Tranquilo "El decimocuarto viaje" de "Star Diaries of Iyon el Tranquilo", en la que el héroe pasa sucesivamente de un artículo sobre sepulki a un artículo sobre sepultación, de allí a un artículo sobre sepulcaria, que nuevamente contiene una referencia al artículo “sepulki”.
Una historia sobre una máquina inteligente que tuvo suficiente inteligencia y pereza para construir otra similar para resolver un problema determinado, y confiarle la solución (el resultado fue una recursión interminable, cuando cada nueva máquina construía una similar y delegaba la tarea a él).

La canción-cuento popular ruso “El sacerdote tenía un perro...” es un ejemplo de recursividad:

El cura tenía un perro, le encantaba,
Ella comió un trozo de carne, él la mató.
Enterrado en el suelo
Título escribió:
“El sacerdote tenía un perro, él la amaba, ella comía un pedazo de carne, él la mató, la enterró en la tierra, la inscripción estaba escrita: “El sacerdote tenía un perro, él la amaba, ella comió un pedazo de carne, la mató, la enterró en la tierra, la inscripción escribió: ...

Ver también

Secuencia recurrente (secuencia de retorno)

Campo de golf

Thomas H. Corman, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein Algoritmos: construcción y análisis = INTRODUCCIÓN A LOS ALGORITMOS. - 2ª ed. - M.: "Williams", 2006. - P. 1296. - ISBN 0-07-013151-1

Fundación Wikimedia.

2010.

Vea qué es un “algoritmo recursivo” en otros diccionarios: algoritmo recursivo

- rekursyvusis algoritmas statusas T sritis automatika atitikmenys: engl. algoritmo recursivo vok. Algoritmo rekursiver, m rus. algoritmo recursivo, m pranc. algoritmo recursivo, m … Automatikos terminų žodynas algoritmo de control recursivo

Este es un algoritmo para ordenar elementos en una lista. Cuando un elemento de la lista tiene varios campos, el campo que sirve como criterio de ordenación se denomina clave de clasificación. En la práctica, un número se utiliza a menudo como clave, y en otros campos... ... Wikipedia

Acrónimo recursivo Un acrónimo (a veces un backronym) que se refiere a sí mismo. Se ha vuelto tradicional entre los piratas informáticos elegir siglas y abreviaturas que se refieran a ellos mismos de forma directa o indirecta. Uno de los primeros ejemplos... ... Wikipedia

- (inglés: analizador de descenso recursivo) un algoritmo de análisis implementado llamando mutuamente a procedimientos de análisis que cumplen con las reglas de una gramática libre de contexto o BNF. Aplicación de las reglas de forma secuencial, de izquierda a derecha... Wikipedia

Un método recursivo para crear una malla de corte para dividir múltiples polígonos 2D que contienen islas en áreas libres de islas. Se puede utilizar en sistemas de información geográfica para convertir polígonos insulares en polígonos no insulares. ¿Enlace? ...Wikipedia

Este término tiene otros significados, consulte Algoritmo (significados). ¿Es deseable mejorar este artículo?: Reelaborar el diseño de acuerdo con las reglas ... Wikipedia

Algoritmos de búsqueda de gráficos A* B* Algoritmo de Bellman Ford Búsqueda bidireccional Algoritmo de Dijkstra Algoritmo de Johnson Búsqueda primero en amplitud Búsqueda primero en profundidad Búsqueda limitada en profundidad Búsqueda primera mejor coincidencia Algoritmo de Floyd Warshall Buscar... ... Wikipedia

Este término tiene otros significados, ver ppm. PPM (Predicción por coincidencia parcial) es un algoritmo estadístico adaptativo de compresión de datos sin pérdidas basado en contexto... ... Wikipedia

La recursividad es la propiedad de un objeto de imitarse a sí mismo. Un objeto es recursivo si sus partes tienen el mismo aspecto que el objeto completo. La recursividad se utiliza mucho en matemáticas y programación:

estructuras de datos:
- un gráfico (en particular árboles y listas) puede considerarse como una colección de un único nodo y un subgrafo (gráfico más pequeño);
- la cadena consta del primer carácter y una subcadena (cadena más pequeña);
patrones de diseño, p.e. Un objeto decorador puede incluir otros objetos que también sean decoradores. McColm Smith estudió los patrones recursivos en detalle y destacó un patrón de diseño general en su libro: Recursion;
funciones recursivas (algoritmos) se llaman a sí mismas.

El artículo está dedicado al análisis de la complejidad de los algoritmos recursivos, se proporciona la información matemática necesaria y se consideran ejemplos. Además, se describe la posibilidad de sustituir la recursividad por un bucle, recursividad de cola.

Ejemplos de algoritmos recursivos

Un algoritmo recursivo siempre divide un problema en partes que tienen la misma estructura que el problema original, pero más simples. Para resolver subproblemas, se llama recursivamente a una función y sus resultados se combinan de alguna manera. La división de una tarea ocurre sólo cuando no se puede resolver inmediatamente (es demasiado compleja).

Por ejemplo, la tarea de procesar una matriz a menudo puede reducirse a procesar sus partes. La división en partes se realiza hasta que se vuelven elementales, es decir. lo suficientemente simple como para obtener el resultado sin mayor simplificación.

Encontrar un elemento de matriz

comenzar; buscar(matriz, comienzo, fin, elemento); busca un elemento con el elemento de valor en la matriz entre los índices inicial y final si inicio > resultado final: = falso; elemento no encontrado de lo contrario si matriz = resultado del elemento: = verdadero; elemento encontrado de lo contrario resultado:= búsqueda(matriz, comienzo+1, fin, elemento) fin; resultado de retorno

El algoritmo divide la matriz original en dos partes: el primer elemento y una matriz de elementos restantes. Hay dos casos sencillos en los que no es necesaria la separación: se han procesado todos los elementos o el primer elemento es el que se busca.

En el algoritmo de búsqueda, la matriz podría dividirse de diferentes maneras (por ejemplo, por la mitad), pero esto no afectaría la eficiencia. Si la matriz está ordenada, entonces es aconsejable dividirla por la mitad, porque En cada paso, la cantidad de datos procesados se puede reducir a la mitad.

Búsqueda binaria en una matriz

La búsqueda binaria se realiza en una matriz ordenada. En cada paso, el elemento buscado se compara con el valor ubicado en el medio de la matriz. Dependiendo de los resultados de la comparación, se puede "descartar" el lado izquierdo o el derecho.

Comenzar; binario_search(matriz, comienzo, fin, elemento); busca un elemento con el valor elemento; en una matriz ordenada en orden ascendente matriz; entre los índices comienzan y terminan si comienzan > terminan; devuelve falso - elemento no encontrado mid:= (fin + comienzo) div 2; calcular el índice del elemento en el medio de la parte considerada de la matriz si matriz = extremo del elemento; devuelve verdadero (elemento encontrado) si es una matriz< element результат:= binary_search(array, mid+1, end, element) иначе результат:= binary_search(array, begin, mid, element) конец; вернуть результат

Calcular los números de Fibonacci

Los números de Fibonacci están determinados por una expresión recurrente, es decir tal que el cálculo de un elemento se expresa a partir de elementos anteriores: $F_0 = 0, F_1 = 1, F_n = F_(n-1) + F_(n-2), n > 2$.

Comenzar; fibonacci(número) si número = 0 fin; devuelve 0 si número = 1 final; devolver 1 fib_1:= fibonacci(número-1) fib_2:= fibonacci(número-2) resultado:= fib_1 + fib_2 fin; resultado de retorno

clasificación rápida

En cada paso, el algoritmo de clasificación rápida selecciona uno de los elementos (la referencia) y, en relación con él, divide la matriz en dos partes, que se procesan de forma recursiva. Los elementos más pequeños que el de soporte se colocan en una parte y el resto en la otra.

Diagrama de flujo del algoritmo de clasificación rápida

Combinar ordenar

La base del algoritmo de clasificación por fusión es la capacidad de combinar rápidamente matrices (o listas) ordenadas para que el resultado esté ordenado. El algoritmo divide la matriz original en dos partes al azar (normalmente por la mitad), las clasifica de forma recursiva y combina el resultado. La división ocurre siempre que el tamaño de la matriz sea mayor que uno, porque una matriz vacía y una matriz de un elemento siempre están ordenadas.

Diagrama de bloques de ordenación por fusión

En cada paso de fusión, se selecciona el primer elemento sin formato de ambas listas. Los elementos se comparan y el más pequeño se agrega al resultado y se marca como procesado. La fusión se produce hasta que una de las listas está vacía.

Comenzar; fusionar(Matriz1, Tamaño1, Matriz2, Tamaño2); las matrices originales están ordenadas; el resultado es una matriz ordenada de longitud Tamaño1+Tamaño2 i:= 0, j:= 0 eterna_loop si i >= Tamaño1 agregue elementos de j a Tamaño2 de la matriz Array2 hasta el final del resultado salga del bucle si j >= Tamaño2 agregue elementos desde i hasta Tamaño1 de la matriz Array1 hasta el final del resultado, salga del bucle si Array1[i]< Array2[j] результат := Array1[i] i:= i + 1 иначе (если Array1[i] >= Array2[j]) resultado := Array2[j] j:= j + 1 fin; resultado de retorno

Análisis de algoritmos recursivos.

Cuando se calcula la complejidad de las iteraciones y su número en el peor, mejor y promedio de los casos. Sin embargo, no será posible aplicar este enfoque a una función recursiva, porque el resultado será una relación de recurrencia. Por ejemplo, para que la función busque un elemento en una matriz:

$
\begin(ecuación*)
T^(búsqueda)_n = \begin(casos)
\mathcal(O)(1) \quad &\text($n = 0$) \\
\mathcal(O)(1) + \mathcal(O)(T^(búsqueda)_(n-1)) \quad &\text($n > 0$)
\end(casos)
\end(ecuación*)
$

Las relaciones recurrentes no nos permiten evaluar la complejidad; no podemos simplemente compararlas y, por lo tanto, comparar la efectividad de los algoritmos correspondientes. Es necesario obtener una fórmula que describa la relación recurrente; una forma universal de hacerlo es seleccionar la fórmula usando el método de sustitución y luego probar la correspondencia de la fórmula con la relación usando el método de inducción matemática.

Método de sustitución (iteración)

Consiste en reemplazar secuencialmente la parte recurrente en una expresión para obtener nuevas expresiones. La sustitución se realiza hasta que sea posible captar el principio general y expresarlo en forma de fórmula no recurrente. Por ejemplo, para buscar un elemento en una matriz:

$
T^(búsqueda)_n = \mathcal(O)(1) + \mathcal(O)(T^(búsqueda)_(n-1)) =
2\times\mathcal(O)(1) + \mathcal(O)(T^(búsqueda)_(n-2)) =
3\times\mathcal(O)(1) + \mathcal(O)(T^(búsqueda)_(n-3))
$

Podemos suponer que $T^(search)_n = T^(search)_(n-k) + k\times\mathcal(O)(1)$, pero entonces $T^(search)_n = T^ (búsqueda)_(0) + n\times\mathcal(O)(1) = \mathcal(O)(n)$.

Hemos derivado la fórmula, pero el primer paso contiene una suposición, es decir no hay prueba de la correspondencia de la fórmula con la expresión recurrente; el método de inducción matemática nos permite obtener la prueba.

Método de inducción matemática.

Permite probar la verdad de un determinado enunciado ($P_n$), consta de dos pasos:

prueba de la declaración para uno o más casos especiales $P_0, P_1, …$;
de la verdad de $P_n$ (hipótesis inductiva) y de casos especiales, se deduce la prueba de $P_(n+1)$.

Demostremos la exactitud de la suposición hecha al estimar la complejidad de la función de búsqueda ($T^(search)_n = (n+1)\times\mathcal(O)(1)$):

$T^(search)_(1) = 2\times\mathcal(O)(1)$ es verdadero a partir de la condición (se puede sustituir en la fórmula recurrente original);
supongamos la verdad $T^(search)_n = (n+1)\times\mathcal(O)(1)$;
necesitamos demostrar que $T^(search)_(n+1) = ((n+1)+1)\times\mathcal(O)(1) = (n+2)\times\mathcal(O ) (1)$;
1. sustituyamos $n+1$ en la relación de recurrencia: $T^(search)_(n+1) = \mathcal(O)(1) + T^(search)_n$;
2. en el lado derecho de la expresión es posible hacer un reemplazo basado en la hipótesis inductiva: $T^(search)_(n+1) = \mathcal(O)(1) + (n+1)\times \mathcal(O)(1) = (n+2)\times\mathcal(O)(1)$;
3. la afirmación ha sido probada.

A menudo, dicha prueba es un proceso bastante laborioso, pero es aún más difícil identificar un patrón utilizando el método de sustitución. En este sentido, se utiliza el llamado método general.

Método general (básico) para resolver relaciones de recurrencia.

El método general no es universal; por ejemplo, no se puede utilizar para estimar la complejidad del algoritmo anterior para calcular los números de Fibonacci. Sin embargo, se aplica a todos los casos en los que se utiliza el enfoque de divide y vencerás:

$T_n = a\cdot T(\frac(n)(b))+f_n; a, b = const, a \geq 1, b > 1, f_n > 0, \forall n$.

Las ecuaciones de este tipo se obtienen si el problema original se divide en subtareas, cada una de las cuales procesa $\frac(n)(b)$ elementos. $f_n$ es la complejidad de las operaciones de dividir el problema en partes y combinar soluciones. Además del tipo de relación, el método general impone restricciones a la función $f_n$, distinguiendo tres casos:

$\exists \varepsilon > 0: f_n = \mathcal(O)(n^(\log_b a - \varepsilon)) \Rightarrow T_n = \Theta(n^(\log_b a))$;
$f_n = \Theta(n^(\log_b a)) \Rightarrow T_n = \Theta(n^(\log_b a) \cdot \log n)$;
$\existe \varepsilon > 0, c< 1: f_n = \Omega(n^{\log_b a + \varepsilon}), f_{\frac{n}{b}} \leq c \cdot f_n \Rightarrow T_n = \Theta(f_n)$.

La veracidad de las declaraciones para cada caso se prueba formalmente. La tarea de analizar un algoritmo recursivo se reduce ahora a determinar el caso del teorema principal al que corresponde la relación de recurrencia.

Análisis del algoritmo de búsqueda binaria.

El algoritmo divide los datos de origen en 2 partes (b = 2), pero procesa solo una de ellas (a = 1), $f_n = 1$. $n^(\log_b a) = n^(\log_2 1) = n^0 = 1$. La función de dividir la tarea y ordenar el resultado crece al mismo ritmo que $n^(\log_b a)$, lo que significa que es necesario utilizar el segundo caso del teorema:

$T^(binarySearch)_n = \Theta(n^(\log_b a) \cdot \log n) = \Theta(1 \cdot \log n) = \Theta(\log n)$.

Análisis de algoritmos de búsqueda.

La función recursiva divide el problema original en una subtarea (a = 1), los datos se dividen en una parte (b = 1). No podemos utilizar el teorema principal para analizar este algoritmo, porque la condición $b > 1$ no se cumple.

Para realizar el análisis se puede utilizar el método de sustitución o el siguiente razonamiento: cada llamada recursiva reduce en uno la dimensión de los datos de entrada, lo que significa que habrá n piezas en total, cada una de las cuales tiene complejidad $\mathcal( O)(1)$. Entonces $T^(search)_n = n \cdot \mathcal(O)(1) = \mathcal(O)(n)$.

Análisis del algoritmo de ordenación por fusión

Los datos de origen se dividen en dos partes, las cuales se procesan: $a = 2, b = 2, n^(\log_b a) = n$.

Al procesar una lista, la división puede requerir operaciones $\Theta(n)$, mientras que para una matriz requiere un tiempo constante ($\Theta(1)$). Sin embargo, en cualquier caso, $\Theta(n)$ se gastará en conectar los resultados, por lo que $f_n = n$.

Se utiliza el segundo caso del teorema: $T^(mergeSort)_n = \Theta(n^(\log_b a) \cdot \log n) = \Theta(n \cdot \log n)$.

Análisis de la intensidad laboral de clasificación rápida.

En el mejor de los casos, la matriz original se divide en dos partes, cada una de las cuales contiene la mitad de los datos originales. La división requerirá n operaciones. La complejidad de componer el resultado depende de las estructuras de datos utilizadas: para una matriz $\mathcal(O)(n)$, para una lista enlazada $\mathcal(O)(1)$. $a = 2, b = 2, f_n = b$, lo que significa que la complejidad del algoritmo será la misma que la del ordenamiento por combinación: \(T^(quickSort)_n = \mathcal(O)(n \ cdot \log n)\ ).

Sin embargo, en el peor de los casos, el elemento mínimo o máximo de la matriz se seleccionará constantemente como referencia. Entonces $b = 1$, lo que significa que nuevamente no podemos usar el teorema principal. Sin embargo, sabemos que en este caso se realizarán n llamadas recursivas, cada una de las cuales divide la matriz en partes ($\mathcal(O)(n)$) - lo que significa la complejidad del algoritmo $T^( QuickSort)_n = \mathcal(O)(n^2)$.

Al analizar la clasificación rápida utilizando el método de sustitución, también habría que considerar los mejores y peores casos por separado.

Recursión de cola y bucle

Analizar la complejidad de funciones recursivas es mucho más complejo que evaluar bucles, pero la razón principal por la que los bucles son preferibles es el alto costo de llamar a una función.

despues de la llamada el control se transfiere otra función. Para transferir el control, basta con cambiar el valor del registro del contador del programa, en el que el procesador almacena el número de la instrucción que se está ejecutando actualmente; de la misma manera, el control se transfiere a las ramas del algoritmo, por ejemplo, cuando se usa un operador condicional. Sin embargo, una llamada no es sólo una transferencia de control, porque después de que la función llamada complete sus cálculos, debe control de retorno hasta el punto donde se realizó la llamada, y también restaurar los valores de las variables locales que existían allí antes de la llamada.

Para implementar este comportamiento, se utiliza una pila (pila de llamadas): en ella se coloca el número de comando a devolver y la información sobre las variables locales. La pila no es infinita, por lo que los algoritmos recursivos pueden provocar un desbordamiento de la pila y, en cualquier caso, trabajar con ella puede llevar una cantidad de tiempo significativa.

En algunos casos, es bastante fácil reemplazar una función recursiva con un bucle, por ejemplo, los discutidos anteriormente. En algunos casos, se requiere un enfoque más creativo, pero la mayoría de las veces ese reemplazo es posible. Además, existe un tipo especial de recursividad en el que la llamada recursiva es la última operación realizada por la función. Obviamente, en este caso, la función que llama no cambiará el resultado de ninguna manera, lo que significa que no tiene sentido devolver el control. Semejante La recursividad se llama recursividad de cola.— los compiladores lo reemplazan automáticamente con un bucle.

A menudo ayuda hacer una recursividad de cola. método de parámetros acumulativos, que consiste en sumar la función de un argumento acumulador adicional en el que se acumula el resultado. La función realiza cálculos en el acumulador antes de la llamada recursiva. Un buen ejemplo del uso de esta técnica es la función factorial:
$fact_n = n \cdot fact(n-1) \\
hecho_3 = 3 \cdot hecho_2 = 3 \cdot (2 \cdot hecho_1) = 3\cdot (2 \cdot (1 \cdot hecho_0)) = 6 \\
hecho_n = hechoCola_(n, 1) \\
\\
factTail_(n, acumulador) = factTail(n-1, acumulador \cdot n)\\
coladefacto_(3, 1) = cola de hecho_(2, 3) = cola de hecho_(1, 6) = cola de hecho_(0, 6) = 6
$

Como ejemplo más complejo, considere la función para calcular los números de Fibonacci. La función principal llama a una función auxiliar que utiliza el método de parámetro de acumulación, pasando el valor inicial del iterador y dos acumuladores (los dos números de Fibonacci anteriores) como argumentos.

Comenzar; fibonacci(número) return fibonacci(número, 1, 1, 0) fin inicio; fibonacci(número, iterador, fib1, fib2) si iterador == número devuelve fib1 devuelve fibonacci(número, iterador + 1, fib1 + fib2, fib1) fin

Una función con un parámetro de acumulación devuelve el resultado acumulado si se calcula un número específico de números; de lo contrario, incrementa el contador, calcula un nuevo número de Fibonacci y realiza una llamada recursiva. Los compiladores de optimización pueden detectar que el resultado de una llamada a una función se pasa sin cambios a la salida de la función y reemplazarlo con un bucle. Esta técnica es especialmente relevante en lenguajes de programación funcionales y lógicos, porque en ellos el programador no puede utilizar explícitamente construcciones cíclicas.

Literatura

Servidor Qt multiproceso. Grupo de hilos. Patrón decorador[Recurso electrónico] – modo de acceso: https://site/archives/1390. Fecha de acceso: 21/02/2015.
Jason McColm Smith: Traducción. del ingles - M.: LLC “I.D. Williams”, 2013. - 304 p.
Skiena S. Algoritmos. Guía de desarrollo.-2ª ed.: trans. De inglés-SPb.: BHV-Petersburg, 2011.-720 pp.: ill.
Vasiliev V. S. Análisis de la complejidad de los algoritmos. Ejemplos [recurso electrónico] – modo de acceso: https://sitio/archives/1660. Fecha de acceso: 21/02/2015.
A. Aho, J. Hopcroft, J. Ullman, Estructuras de datos y algoritmos, M., Williams, 2007.
Miller, R. Algoritmos secuenciales y paralelos: un enfoque general / R. Miller, L. Boxer; carril del ingles - M.: BINOM. Laboratorio de Conocimiento, 2006. - 406 p.
Sergievsky G.M. Programación funcional y lógica: libro de texto. manual para estudiantes superiores libro de texto establecimientos / G.M. Sergievsky, N.G. Vólchenkov. - M.: Centro editorial "Academia", 2010.- 320 p.

¿Qué es la recursividad?

Esta palabra se refiere a un proceso que se refiere a la repetición de los mismos elementos de manera “autosimilar”. Un ejemplo digno de tal proceso es la muñeca rusa para anidar, y si no fuera por el límite de posibilidades, entonces tal juguete se repetiría hasta el infinito.

Por razones técnicas, la recursividad sigue siendo una cantidad finita.

En programación, este término se refiere al proceso de una función que se llama a sí misma o que llama a una desde dentro. Naturalmente, las llamadas recursivas deben tener condiciones de terminación completamente factibles; de lo contrario, el programa con otras condiciones se congelará y colapsará con una pila desbordada.

Un ejemplo de recursividad matemática es el ya bastante aburrido ejemplo del cálculo del factorial. De hecho, la recursividad en la programación web se utiliza con bastante frecuencia, y todo porque la recursividad es la única opción para eludir cualquier estructura estándar cuando no se conoce exactamente su tamaño real y su profundidad de anidamiento. La construcción de gráficos tampoco se puede realizar sin él. Esta es una opción clásica.

Para asegurarse de que este proceso sea necesario, vale la pena intentar crear un mapa del sitio con secciones de acuerdo con la estructura jerárquica de listas anidadas. Esto no será realista si no se limita de antemano a su tamaño y profundidad de inversión. Pero si, después de todo, construyes algo similar, comprenderás que en algún momento toda tu estructura se congelará y dejará de funcionar.

Recursividad en motores de búsqueda.

Los motores de búsqueda también dependen de la recursividad. Fue desde el momento en que se introdujo el criterio de autoridad del sitio, medida por el número de enlaces, que los motores de búsqueda también cayeron en estas redes. El enlace “masa” de un sitio se compone de pequeños trozos de la “masa” de todos aquellos recursos que enlazan con él. Para calcular este indicador para un sitio, es necesario calcular la "masa" de todas las opciones de enlaces, que a su vez constan de otros componentes similares, y así sucesivamente, en toda la profundidad de la red de búsqueda. Hasta aquí la recursividad en la práctica.

PageRank recursivo de Google

Así se llama el algoritmo de cálculo creado y publicado por Google. Este algoritmo se conoce desde hace mucho tiempo, pero no importa cuántas veces se transforme y se complemente con todo tipo de mejoras, sigue basándose en el mismo método recursivo. La esencia siempre sigue siendo la misma: cálculos, recálculos y recálculos nuevamente. El resultado es la misma función nuevamente.

TCI recursivo de Yandex

El TIC creado por Yandex tiene exactamente la misma estructura que el algoritmo anterior. La única diferencia es que se calcula para todo el sitio y no para cada página individual. Es por eso que el motor de búsqueda Yandex vive mucho más libremente que otros, ya que hay muchas veces menos sitios que páginas y es mucho más fácil contarlos.

Sin embargo, este indicador no afecta los resultados de búsqueda en Yandex. Para estos fines, tiene un VIC profundamente oculto, que es análogo al PageRank. Por tanto, el volumen de cálculos de Yandex también es considerable.

Un algoritmo de cálculo recursivo basado en el peso del enlace mostró que dos sitios que tienen enlaces entre sí tienen un peso irrealmente alto. Por lo tanto, inmediatamente después de la publicación del algoritmo PageRank, los optimizadores comenzaron a promover los enlaces recursivos. Los experimentos realizados confirmaron que el método utilizado tiene un resultado eficaz.

Comenta este artículo:

Por favor regístrese para comentar.

A la Universidad Nacional de Ucrania Oriental que lleva el nombre de Vladimir Dahl

recursividad

Informática y tecnología informática.

La recursión es una poderosa técnica de programación que le permite dividir un problema en partes cada vez más pequeñas hasta que se vuelven tan pequeñas que la solución a estos subproblemas se reduce a un conjunto de operaciones simples.

Una vez que adquieras experiencia con la recursividad, la verás en todas partes. Muchos programadores que recientemente han dominado la recursividad se dejan llevar y comienzan a utilizarla en situaciones en las que es innecesaria y, a veces, dañina.

¿Qué es la recursividad?

La recursividad ocurre cuando una función o subrutina se llama a sí misma. Derecho recursividad(recursión directa) se parece a esto:

Función Factorial(num Mientras) Mientras tanto

Factorial = núm * Factorial(núm - 1)

En caso recursividad indirecta(recursión indirecta) un procedimiento recursivo llama a otro procedimiento, que a su vez llama al primero:

Subping privado (número como entero)

Sub Pong privado (número como número entero)

La recursividad es útil para resolver problemas que naturalmente se dividen en varios subproblemas, cada uno de los cuales es un caso más simple del problema original. Puedes imaginar un árbol como un “tronco” con dos árboles más pequeños encima. Luego puedes escribir un procedimiento recursivo para dibujar árboles:

Sub DrawTree privado()

Dibuja el "baúl"

Dibuja un árbol más pequeño girado -45 grados

Dibuja un árbol más pequeño girado 45 grados.

Aunque la recursividad puede hacer que algunos problemas sean más fáciles de entender, la gente generalmente no piensa de forma recursiva. Por lo general, se esfuerzan por dividir tareas complejas en tareas más pequeñas que puedan completarse una tras otra hasta completarse. Por ejemplo, para pintar un seto, puedes empezar por el borde izquierdo y continuar hacia la derecha hasta terminar. Probablemente no pienses en la posibilidad de colorear recursivamente primero la mitad izquierda de la cerca y luego colorear recursivamente la mitad derecha al realizar una tarea como esta.

Para pensar de forma recursiva, es necesario dividir un problema en subproblemas, que luego se pueden dividir en subproblemas más pequeños. En algún momento, las subtareas se vuelven tan simples que se pueden realizar directamente. Cuando se completen las subtareas, también se completarán las subtareas más grandes que se componen de ellas. La tarea original se completará cuando se completen todas sus subtareas.

Los peligros de la recursividad
1. recursividad infinita

El peligro más obvio de la recursividad es la recursión infinita. Si el algoritmo se construye incorrectamente, la función puede omitir la condición para detener la recursividad y ejecutarse sin cesar. La forma más sencilla de cometer este error es simplemente olvidarse de comprobar la condición de parada, como se hace en la siguiente versión errónea de la función factorial. Dado que la función no verifica si se ha alcanzado la condición de parada de recursividad, se llamará a sí misma sin cesar.

Función privada BadFactorial (núm. como número entero) como número entero

BadFactorial = núm * MalFactorial (núm - 1)

Una función también puede llamarse a sí misma indefinidamente si la condición de detención no finaliza todas las rutas de recursividad posibles. En la siguiente versión con errores de la función factorial, la función se llamará a sí misma sin cesar si el valor de entrada no es un número entero o si es menor que 0. Estos valores no son valores de entrada válidos para la función factorial, por lo que Es posible que se requiera una verificación en un programa que utiliza los valores de entrada de esta función. Sin embargo, será mejor si la función realiza esta comprobación por sí misma.

Función privada BadFactorial2(num como doble) como doble

MalFactorial2 = 1

BadFactorial2 = núm * BadFactorial2(núm-1)

La siguiente versión de la función de Fibonacci es un ejemplo más complejo. Su condición de detención de recursividad solo detiene algunas rutas de recursividad y tiene los mismos problemas que BadFactorial2 si los valores de entrada son negativos o no enteros.

Función privada BadFib(num como doble) como doble

BadFib = BadPib(núm - 1) + BadFib (núm - 2)

El último problema con la recursividad infinita es que "infinito" en realidad significa "hasta que se agote el espacio de la pila". Incluso los procedimientos recursivos bien escritos a veces provocarán un desbordamiento de la pila y un bloqueo. La siguiente función, que calcula la suma de N + (N - 1) +... + 2 +1, hace que el espacio de la pila se agote para valores grandes de N. El valor más alto posible de N en el que el programa seguirá funcionando depende de la configuración de su computadora.

Función privada BigAdd (N como doble) como doble

Si norte<= 1 Then

SumaGrande=N + SumaGrande(N - 1)

El programa BigAdd en el disco de ejemplo demuestra este algoritmo. Pruebe qué tan grande es el valor de entrada que puede ingresar en este programa antes de causar un desbordamiento de pila en su computadora.

Popular en la categoría: