recursion c
Explore todo sobre la recursividad en C ++ con ejemplos clásicos.
En nuestro tutorial anterior, aprendimos más sobre funciones en C ++.
Además de utilizar las funciones para dividir el código en subunidades y hacer que el código sea más simple y legible, las funciones son útiles en varias otras aplicaciones, incluida la resolución de problemas en tiempo real, el cálculo matemático y estadístico.
A medida que desarrollamos aplicaciones más complejas en C ++, nos encontramos con muchos requisitos, por lo que necesitamos poner en práctica varios conceptos especiales de C ++. La recursividad es uno de esos conceptos.
=> Visite aquí para ver la lista completa de tutoriales de C ++.
En este tutorial, aprenderemos más sobre la recursividad, dónde y por qué se usa junto con algunos ejemplos clásicos de C ++ que implementan la recursividad.
Lo que vas a aprender:
- ¿Qué es la recursividad?
- Condición base de recursividad
- Asignación de memoria para la llamada recursiva
- Desbordamiento de pila en recursividad
- Recursión directa vs indirecta
- Recursión con cola y sin cola
- Ventajas y desventajas de la recursividad sobre la programación iterativa
- Ejemplos de recursividad
- Conclusión
- Lectura recomendada
¿Qué es la recursividad?
La recursividad es un proceso en el que una función se llama a sí misma. La función que implementa la recursividad o se llama a sí misma se denomina función recursiva. En la recursividad, la función recursiva se llama a sí misma una y otra vez y continúa hasta que se cumple una condición final.
La siguiente imagen muestra cómo funciona la recursividad:
Como vemos en el diagrama anterior, la función principal llama a una función, funct (). La función funct () a su vez se llama a sí misma dentro de su definición. Así es como funciona la recursividad. Este proceso de la función que se llama a sí misma continuará hasta que proporcionemos una condición de terminación que hará que finalice.
Por lo general, proporcionamos una rama de código mientras implementamos la recursividad, de modo que proporcionamos una condición que activará la recursividad y otra para llevar a cabo la ejecución normal.
Condición base de recursividad
Cuando se lleva a cabo la recursividad, se proporciona la solución al caso base o al caso de terminación y las soluciones a problemas mayores se construyen en base a las soluciones a problemas menores.
Consideremos un ejemplo clásico de recursividad, la notación factorial.
Sabemos que matemáticamente el factorial de un número n es:
¡norte! = nxn-1x… .x0!
dado que 0! = 1;
¡Entonces el factorial para n = 3 será 3! = 3 × 2!
3! = 3x2x1!
3! = 3x2x2x0!
3! = 3x2x1x1 = 6
Entonces programáticamente podemos expresar este cálculo de la siguiente manera:
|_+_|Por lo tanto, como se muestra arriba, hemos expresado el cálculo anterior de un factorial en una llamada de función recursiva. Vemos que si el número n es menor o igual a 1, devolvemos 1 en lugar de una llamada recursiva. Esto se denomina condición / caso base para el factorial que permite detener la recursividad.
Por lo tanto, la condición base básicamente decide cuántas veces una función recursiva debe llamarse a sí misma. Esto significa que podemos calcular muy bien el factorial de un número mayor expresándolo en términos de números más pequeños hasta alcanzar la clase base.
A continuación se muestra un ejemplo perfecto para calcular el factorial de un número:
|_+_|Producción:
Introduzca el número cuyo factorial se va a calcular: 10
10! = 3628800
En el ejemplo anterior, implementamos la recursividad. Tomamos el número cuyo factorial se va a encontrar de la entrada estándar y luego lo pasamos a la función factorial.
En la función factorial, hemos dado la condición base como (n<=1). So, when the base case is reached, the function returns. Using this base case, we can calculate factorial of any number greater than 1.
Asignación de memoria para la llamada recursiva
Sabemos que cuando se realiza una llamada de función, el estado de la función que llama se almacena en la pila y cuando se completa una llamada de función, ese estado se restaura para que el programa pueda continuar la ejecución.
Cuando se realiza una llamada de función recursiva, el estado o la memoria de la función llamada se asigna además del estado de la función que llama y se realiza una copia diferente de las variables locales para cada llamada de función recursiva.
Cuando se alcanza la condición base, la función vuelve a la función que llama y se desasigna la memoria y el proceso continúa.
Desbordamiento de pila en recursividad
Cuando la recursividad continúa por una cantidad de tiempo ilimitada, puede resultar en un desbordamiento de pila.
¿Cuándo puede continuar la recursión así? Una situación es cuando no especificamos la condición base. Otra situación es cuando no se alcanza la condición base mientras se ejecuta un programa.
Por ejemplo,modificamos el programa factorial anterior y cambiamos su condición base.
|_+_|En el código anterior, hemos cambiado la condición base a (n == 1000). Ahora, si damos el número n = 10, podemos concluir que la condición base nunca alcanzará. De esta manera, en algún momento, la memoria de la pila se agotará, lo que provocará un desbordamiento de la pila.
Por lo tanto, al diseñar programas recursivos, debemos tener cuidado con la condición base que proporcionamos.
Recursión directa vs indirecta
Hasta ahora, en recursividad, hemos visto que la función se llama a sí misma. Esta es la recursividad directa.
Hay otro tipo de recursividad, es decir, recursividad indirecta. En esto, una función llama a otra función y luego esta función llama a la función que llama. Si f1 y f2 son dos funciones. Entonces f1 llama a f2 y f2, a su vez, llama a f1. Esta es una recursividad indirecta.
¿Cuál es la máscara de subred adecuada para una red entre dos hosts?
L Revisemos nuestro programa factorial para demostrar la recursividad directa.
|_+_|Producción:
Ingrese el número cuyo factorial se va a calcular: 5
5! = 120
En el ejemplo anterior, hemos mostrado la recursividad indirecta. La función principal llama a factorial_a. Factorial_a llama factorial_b. A su vez, factorial_b llama factorial_a. Vemos que la salida del programa no se ve afectada.
Recursión con cola y sin cola
Una función recursiva con cola es una función recursiva donde la última llamada se ejecuta en la función.
Por ejemplo, considere la siguiente función.
|_+_|En el ejemplo anterior, la pantalla es una función recursiva con cola, de modo que es la última llamada a la función.
Las funciones con cola se consideran mejores que las funciones recursivas sin cola, ya que pueden ser optimizadas por el compilador. La razón es que como la llamada recursiva con cola es la última declaración de la función, no hay código para ejecutar después de esta llamada.
Como resultado, no es necesario guardar el marco de pila actual para la función.
Ventajas y desventajas de la recursividad sobre la programación iterativa
Los programas recursivos proporcionan un código limpio y compacto. Un programa recursivo es una forma sencilla de escribir programas. Hay algunos problemas inherentes como factorial, secuencia de Fibonacci, torres de Hanoi, recorridos de árboles, etc. que requieren recursividad para su resolución.
En otras palabras, se resuelven de manera eficiente con recursividad. También se pueden resolver con programación iterativa utilizando pilas u otras estructuras de datos, pero hay posibilidades de que su implementación sea más compleja.
Los poderes de resolución de problemas de la programación recursiva e iterativa son los mismos. Sin embargo, los programas recursivos ocupan más espacio en la memoria, ya que todas las llamadas a funciones deben almacenarse en la pila hasta que coincida con el caso base.
Las funciones recursivas también tienen una sobrecarga de tiempo debido a demasiadas llamadas a funciones y valores de retorno.
Ejemplos de recursividad
A continuación, implementaremos algunos de los ejemplos de programación recursiva.
Serie de Fibonacci
La serie de Fibonacci es la secuencia que se da como
0 1 1 2 3 5 8 13……
Como se muestra arriba, los dos primeros números de la serie de Fibonacci son 0 y 1. El siguiente número en la secuencia es la suma de los dos números anteriores.
Implementemos esta serie usando Recursion.
|_+_|Producción:
Ingrese el número de elementos para la serie Fibonacci: 10
Serie Fibonacci para 10 números: 0 1 1 2 3 5 8 13 21 34
En este ejemplo, hemos utilizado una llamada recursiva para generar la secuencia de Fibonacci. Vemos que los dos primeros números que son constantes se imprimen directamente y para los siguientes números de la secuencia usamos una función recursiva.
Palíndromo
Un número palíndromo es un número que, cuando se lee en dirección inversa, es el mismo que se lee de izquierda a derecha.
Por ejemplo, el número 121 mientras se lee de izquierda a derecha y de derecha a izquierda dice lo mismo, es decir, 121. Por lo tanto, 121 es un palíndromo.
El número 291, cuando se lee de derecha a izquierda, es decir, en orden inverso, se lee como 192. Por lo tanto, 291 no es un palíndromo.
|_+_|Producción:
Ingrese el número para verificar palíndromo: 6556
El número 6556 es un palíndromo
La captura de pantalla de la misma se muestra a continuación.
En el programa anterior, leemos el número de entrada de la entrada estándar. Luego pasamos este número a una función recursiva para invertir los dígitos de un número. Si los dígitos invertidos y el número de entrada son iguales, entonces el número es un palíndromo.
Conclusión
Con esto, hemos terminado con la recursividad. En este tutorial, hemos estudiado la programación recursiva, la función recursiva, sus ventajas / desventajas, junto con varios ejemplos en detalle.
Aparte de estos ejemplos, la recursividad también se utiliza para resolver algunos problemas estándar como recorridos (inorder / preorder / postorder), torres de Hanoi, recorrido BFS, etc.
=> Visite aquí para aprender C ++ desde cero.
Lectura recomendada
- Funciones de amigo en C ++
- Polimorfismo en C ++
- Una descripción completa de C ++
- Tutorial de la función principal de Python con ejemplos prácticos
- Tutorial de Unix Pipes: Pipes en la programación Unix
- Funciones de biblioteca en C ++
- 70+ MEJORES Tutoriales de C ++ para aprender programación C ++ GRATIS
- Tutorial de QTP n. ° 21: cómo hacer que las pruebas de QTP sean modulares y reutilizables usando acciones y bibliotecas de funciones