¿Qué es la recursividad?
El proceso en el que una función se llama a sí misma directa o indirectamente se llama recursividad y la función correspondiente se llama función recursiva. Utilizando un algoritmo recursivo, ciertos problemas se pueden resolver con bastante facilidad. Ejemplos de tales problemas son Torres de Hanoi (TOH) , Recorridos de árboles en orden/preorden/postorden , DFS de Graph, etc. Una función recursiva resuelve un problema particular llamando a una copia de sí misma y resolviendo subproblemas más pequeños de los problemas originales. Se pueden generar muchas más llamadas recursivas cuando sea necesario. Es fundamental saber que debemos proporcionar un caso determinado para poder finalizar este proceso de recursividad. Entonces podemos decir que cada vez la función se llama a sí misma con una versión más simple del problema original.

Necesidad de recursividad

La recursividad es una técnica asombrosa con la ayuda de la cual podemos reducir la longitud de nuestro código y hacerlo más fácil de leer y escribir. Tiene ciertas ventajas sobre la técnica de iteración que se discutirán más adelante. Una tarea que se puede definir con su subtarea similar, la recursividad es una de las mejores soluciones para ello. Por ejemplo; El factorial de un número.

Propiedades de la recursividad:

• Realizar las mismas operaciones varias veces con diferentes entradas.
• En cada paso, intentamos realizar aportaciones más pequeñas para reducir el problema.
• Se necesita una condición base para detener la recursividad, de lo contrario se producirá un bucle infinito.

Algoritmo: pasos

The algorithmic steps for implementing recursion in a function are as follows: Step1 - Define a base case: Identify the simplest case for which the solution is known or trivial. This is the stopping condition for the recursion, as it prevents the function from infinitely calling itself. Step2 - Define a recursive case: Define the problem in terms of smaller subproblems. Break the problem down into smaller versions of itself, and call the function recursively to solve each subproblem. Step3 - Ensure the recursion terminates: Make sure that the recursive function eventually reaches the base case, and does not enter an infinite loop. step4 - Combine the solutions: Combine the solutions of the subproblems to solve the original problem.>

Una interpretación matemática

Consideremos un problema que tiene un programador para determinar la suma de los primeros n números naturales, hay varias formas de hacerlo, pero el enfoque más simple es simplemente sumar los números comenzando desde 1 hasta n. Entonces la función simplemente se ve así,

enfoque(1) – Simplemente agregando uno por uno

f(norte) = 1 + 2 + 3 +……..+ norte

pero hay otro enfoque matemático para representar esto,

enfoque(2) – Suma recursiva

f(norte) = 1 norte=1

f(n) = n + f(n-1) n>1

Hay una diferencia simple entre el enfoque (1) y el enfoque (2) y eso está en enfoque(2) la función f( ) se llama dentro de la función, por lo que este fenómeno se llama recursividad, y la función que contiene recursividad se llama función recursiva. Al final, esta es una gran herramienta en manos de los programadores para codificar algunos problemas de una manera mucho más fácil y eficiente. forma.

¿Cómo se almacenan las funciones recursivas en la memoria?

La recursión utiliza más memoria, porque la función recursiva se suma a la pila con cada llamada recursiva y mantiene los valores allí hasta que finaliza la llamada. La función recursiva utiliza la estructura LIFO (ÚLTIMO EN ENTRAR, PRIMERO EN SALIR) al igual que la estructura de datos de la pila. estructura-de-datos-de-pila/

¿Cuál es la condición base en recursividad?
En el programa recursivo, se proporciona la solución al caso base y la solución al problema mayor se expresa en términos de problemas más pequeños.

int fact(int n) { if (n <= 1) // base case return 1; else return n*fact(n-1); }>

En el ejemplo anterior, se define el caso base para n <= 1 y el valor mayor de un número se puede resolver convirtiéndolo a uno más pequeño hasta alcanzar el caso base.

¿Cómo se resuelve un problema particular mediante la recursividad?
La idea es representar un problema en términos de uno o más problemas más pequeños y agregar una o más condiciones base que detengan la recursividad. Por ejemplo, calculamos el factorial n si conocemos el factorial de (n-1). El caso base para factorial sería n = 0. Devolvemos 1 cuando n = 0.

¿Por qué se produce un error de desbordamiento de pila en recursividad?
Si no se alcanza el caso base o no se define, entonces puede surgir el problema de desbordamiento de pila. Pongamos un ejemplo para entender esto.

int fact(int n) { // wrong base case (it may cause // stack overflow). if (n == 100) return 1; else return n*fact(n-1); }>

Si se llama al hecho (10), llamará al hecho (9), al hecho (8), al hecho (7), etc., pero el número nunca llegará a 100. Por lo tanto, no se alcanza el caso base. Si estas funciones agotan la memoria en la pila, se producirá un error de desbordamiento de la pila.

¿Cuál es la diferencia entre recursividad directa e indirecta?
Una función divertida se llama recursiva directa si llama a la misma función divertida. Una función fun se llama recursiva indirecta si llama a otra función, digamos fun_new y fun_new llama a fun directa o indirectamente. La diferencia entre recursividad directa e indirecta se ilustra en la Tabla 1.

 // An example of direct recursion void directRecFun() { // Some code.... directRecFun(); // Some code... } // An example of indirect recursion void indirectRecFun1() { // Some code... indirectRecFun2(); // Some code... } void indirectRecFun2() { // Some code... indirectRecFun1(); // Some code... }>

¿Cuál es la diferencia entre recursividad con cola y sin cola?
Una función recursiva es recursiva de cola cuando una llamada recursiva es lo último que ejecuta la función. Consulte artículo de recursividad de cola para detalles.

¿Cómo se asigna la memoria a diferentes llamadas a funciones en recursividad?
Cuando se llama a cualquier función desde main(), se le asigna memoria en la pila. Una función recursiva se llama a sí misma, la memoria para una función llamada se asigna además de la memoria asignada a la función que llama y se crea una copia diferente de las variables locales para cada llamada a la función. Cuando se alcanza el caso base, la función devuelve su valor a la función que la llama, se desasigna la memoria y el proceso continúa.
Tomemos el ejemplo de cómo funciona la recursividad tomando una función simple.

CPP

>

>

Java

patrón de diseño del método de fábrica

>

>

Python3

>

>

C#

>

>

PHP

>

>

JavaScript

>

>

3 2 1 1 2 3>

Complejidad del tiempo: O(1)
Espacio Auxiliar: O(1)

Cuando imprimirDiversión(3) se llama desde main(), la memoria se asigna a imprimirDiversión(3) y una prueba de variable local se inicializa en 3 y las declaraciones 1 a 4 se insertan en la pila como se muestra en el siguiente diagrama. Primero imprime '3'. En la declaración 2, imprimirDiversión(2) se llama y se asigna memoria a imprimirDiversión(2) y una prueba de variable local se inicializa en 2 y las declaraciones 1 a 4 se insertan en la pila. Similarmente, imprimirDiversión(2) llamadas imprimirDiversión(1) y imprimirDiversión(1) llamadas imprimirDiversión(0) . imprimirDiversión(0) va a la declaración if y regresa a imprimirDiversión(1) . Las declaraciones restantes de imprimirDiversión(1) se ejecutan y vuelve a imprimirDiversión(2) etcétera. En la salida, se imprimen los valores del 3 al 1 y luego del 1 al 3. La pila de memoria se muestra en el siguiente diagrama.

Recursión VS Iteración

Ahora, analicemos algunos problemas prácticos que se pueden resolver mediante el uso de la recursividad y comprendamos su funcionamiento básico. Para una comprensión básica, lea los siguientes artículos.
Comprensión básica de la recursividad.
Problema 1: Escriba un programa y una relación de recurrencia para encontrar la serie de Fibonacci de n donde n>2.
Ecuación matemática:

n if n == 0, n == 1; fib(n) = fib(n-1) + fib(n-2) otherwise;>

Relación de recurrencia:

T(n) = T(n-1) + T(n-2) + O(1)>

Programa recursivo:

 Input: n = 5 Output: Fibonacci series of 5 numbers is : 0 1 1 2 3>

Implementación:

C++

núcleo java

>

>

C

>

>

Java

>

>

Python3

>

>

C#

>

>

JavaScript

mapeo en mecanografiado

>

>

Fibonacci series of 5 numbers is: 0 1 1 2 3>

Complejidad del tiempo: o(2^norte)
Espacio Auxiliar: En)

Aquí está el árbol recursivo para la entrada 5 que muestra una imagen clara de cómo un problema grande se puede resolver en otros más pequeños.
fib(n) es una función de Fibonacci. La complejidad temporal del programa dado puede depender de la llamada a la función.

fib(n) -> nivel CBT (UB) -> 2^n-1 nodos -> 2^n llamada de función -> 2^n*O(1) -> T(n) = O(2^n)

Para el mejor de los casos.

T(n) = ?(2^n2)>

Laboral:

Problema 2: Escriba un programa y una relación de recurrencia para encontrar el Factorial de n donde n>2.
Ecuación matemática:

1 if n == 0 or n == 1; f(n) = n*f(n-1) if n>1;>

Relación de recurrencia:

T(n) = 1 for n = 0 T(n) = 1 + T(n-1) for n>0>

Programa recursivo:
Aporte: norte = 5
Producción:
factorial de 5 es: 120
Implementación:

C++

>

>

C

>

>

Java

>

>

Python3

>

>

C#

>

>

JavaScript

>

>

factorial of 5 is: 120>

Complejidad del tiempo: En)
Espacio Auxiliar: En)

Laboral:

Diagrama de la función de recursividad factorial para la entrada del usuario 5.

Ejemplo: Aplicaciones reales de la recursividad en problemas reales

La recursividad es una técnica poderosa que tiene muchas aplicaciones en informática y programación. Estas son algunas de las aplicaciones comunes de la recursividad:

Recorrido de árboles y gráficos: la recursión se utiliza con frecuencia para atravesar y buscar estructuras de datos como árboles y gráficos. Se pueden utilizar algoritmos recursivos para explorar todos los nodos o vértices de un árbol o gráfico de forma sistemática. Algoritmos de clasificación: los algoritmos recursivos también se utilizan en algoritmos de clasificación, como la clasificación rápida y la clasificación por combinación. Estos algoritmos utilizan la recursividad para dividir los datos en subarreglos o sublistas más pequeños, ordenarlos y luego volver a fusionarlos. Algoritmos de divide y vencerás: muchos algoritmos que utilizan un enfoque de divide y vencerás, como el algoritmo de búsqueda binaria, utilizan la recursividad para dividir el problema en subproblemas más pequeños. Generación fractal: se pueden generar formas y patrones fractales utilizando algoritmos recursivos. Por ejemplo, el conjunto de Mandelbrot se genera aplicando repetidamente una fórmula recursiva a números complejos. Algoritmos de retroceso: Los algoritmos de retroceso se utilizan para resolver problemas que implican tomar una secuencia de decisiones, donde cada decisión depende de las anteriores. Estos algoritmos se pueden implementar mediante recursividad para explorar todos los caminos posibles y retroceder cuando no se encuentra una solución. Memoización: la memorización es una técnica que implica almacenar los resultados de costosas llamadas a funciones y devolver el resultado almacenado en caché cuando se repiten las mismas entradas. La memorización se puede implementar utilizando funciones recursivas para calcular y almacenar en caché los resultados de los subproblemas.

Estos son sólo algunos ejemplos de las numerosas aplicaciones de la recursividad en informática y programación. La recursión es una herramienta versátil y poderosa que se puede utilizar para resolver muchos tipos diferentes de problemas.

Explicación: un ejemplo real de recursividad:

La recursividad es una técnica de programación que implica que una función se llame a sí misma. Puede ser una herramienta poderosa para resolver problemas complejos, pero también requiere una implementación cuidadosa para evitar bucles infinitos y desbordamientos de pila.

Aquí hay un ejemplo de implementación de recursividad en Python:

C++

>

>

Java

funcionamiento interno de hashmap

>

>

Python3

>

>

C#

>

>

JavaScript

>

>

120>

En este ejemplo, definimos una función llamada factorial que toma un número entero n como entrada. La función utiliza la recursividad para calcular el factorial de n (es decir, el producto de todos los números enteros positivos hasta n).

La función factorial primero verifica si n es 0 o 1, que son los casos base. Si n es 0 o 1, la función devuelve 1, ya que 0! ¡y 1! ambos son 1.

Si n es mayor que 1, la función entra en el caso recursivo. Se llama a sí mismo con n-1 como argumento y multiplica el resultado por n. Esto calcula n! calculando recursivamente (n-1)!.

Es importante tener en cuenta que la recursividad puede ser ineficiente y provocar desbordamientos de pila si no se usa con cuidado. Cada llamada a función agrega un nuevo marco a la pila de llamadas, lo que puede hacer que la pila crezca demasiado si la recursividad es demasiado profunda. Además, la recursividad puede hacer que el código sea más difícil de entender y depurar, ya que requiere pensar en múltiples niveles de llamadas a funciones.

Sin embargo, la recursividad también puede ser una herramienta poderosa para resolver problemas complejos, particularmente aquellos que implican dividir un problema en subproblemas más pequeños. Cuando se usa correctamente, la recursividad puede hacer que el código sea más elegante y más fácil de leer.

¿Cuáles son las desventajas de la programación recursiva sobre la programación iterativa?
Tenga en cuenta que tanto los programas recursivos como los iterativos tienen el mismo poder de resolución de problemas, es decir, cada programa recursivo se puede escribir de forma iterativa y viceversa. El programa recursivo tiene mayores requisitos de espacio que el programa iterativo ya que todas las funciones permanecerán en la pila hasta que se alcance el caso base. También requiere mayores requisitos de tiempo debido a las llamadas a funciones y los gastos generales de retorno.

Además, debido a la menor longitud del código, los códigos son difíciles de entender y, por lo tanto, se debe tener especial cuidado al escribir el código. La computadora puede quedarse sin memoria si las llamadas recursivas no se verifican adecuadamente.

¿Cuáles son las ventajas de la programación recursiva sobre la programación iterativa?
La recursión proporciona una forma limpia y sencilla de escribir código. Algunos problemas son inherentemente recursivos como los recorridos de árboles, Torre de Hanoi , etc. Para tales problemas, se prefiere escribir código recursivo. Podemos escribir dichos códigos también de forma iterativa con la ayuda de una estructura de datos de pila. Por ejemplo, consulte Inorder Tree Traversal without Recursion, Iterative Tower of Hanoi.

Resumen de recursividad:

• Hay dos tipos de casos en recursividad, es decir, un caso recursivo y un caso base.
• El caso base se utiliza para terminar la función recursiva cuando el caso resulta ser verdadero.
• Cada llamada recursiva hace una nueva copia de ese método en la memoria de la pila.
• La recursividad infinita puede provocar que se agote la memoria de la pila.
• Ejemplos de algoritmos recursivos: Merge Sort, Quick Sort, Torre de Hanoi, Serie de Fibonacci, Problema factorial, etc.

Problemas de práctica basados ​​en resultados para principiantes:
Preguntas de práctica para la recursividad | Serie 1
Preguntas de práctica para la recursividad | Conjunto 2
Preguntas de práctica para la recursividad | Conjunto 3
Preguntas de práctica para la recursividad | Conjunto 4
Preguntas de práctica para la recursividad | Conjunto 5
Preguntas de práctica para la recursividad | Conjunto 6
Preguntas de práctica para la recursividad | Conjunto 7
Prueba sobre recursividad
Práctica de codificación en recursividad:
Todos los artículos sobre recursividad
Problemas de práctica recursiva con soluciones