La recursión es uno de esos temas que siempre genera controversia. Sin embargo, independientemente de la posición de cada programador una cosa es cierta: debes conocer el concepto y la técnica. Aunque nunca más la utilices.
A diferencia del resto del tutorial, en este artículo he hecho una extensa consulta de diversas fuentes y las he integrado de forma directa considerando la complejidad del tema, como siempre, se dan los créditos correspondientes.
La recursividad es una técnica de programación que busca resolver un problema sustituyéndolo por otros problemas de la misma categoría, pero más simples implementando un algoritmo recursivo.
En muchos lados encontrarás expresado lo anterior como:
Una función recursiva es una función que se llama a sí misma.
Se dice que un algoritmo es recursivo si dentro del cuerpo del algoritmo y de forma directa o indirecta se realiza una llamada a él mismo.
Las funciones recursivas tienen similitud con los bucles, pero no están basados en una declaración condicional. La función se llama siempre que se requiere el mismo código para ejecutarse de forma reiterada.
Para escribir una función recursiva, se deben satisfacer 3 condiciones:
Es importante recordar que cualquier función recursiva debe tener un “caso base” (paso 1), el caso base es cualquier expresión donde le dice a la función cuándo dejar de llamarse a sí misma. Si no tiene un caso base, la recursión producirá un bucle infinito.
Las llamadas a funciones recursivas pueden usarse para actividades que son recursivas por naturaleza y que tienen las siguientes características.
Otros ejemplos que se adaptan a la programación recursiva son la búsqueda binaria, listas recursivas, particiones, árboles, series de Fibonacci, etc.
Un ejemplo típico de programación recursiva consiste en la terea de eliminar un directorio. La función eliminará todos los archivos en un directorio y cuando encuentre un subdirectorio se llamará a sí mismo para eliminar el subdirectorio y todos sus archivos y subdirectorios.
Normalmente no tendrás necesidad de complicarte con la recursión a menos que te dediques a programar de forma avanzada.
De forma general, si la eficiencia es un factor importante y/o el algoritmo se va a ejecutar de forma frecuente, conviene escribir una solución iterativa.
Notarás que casi todos los libros, blogs, papers, cursos en línea y cualquier recurso que te muestra la recursión inevitablemente utilizan la función factorial como ejemplo.
Sin embargo si buscas información académica, comprenderás que la recursión en más que el cálculo del factorial.
Esto se debe a que el factorial de un número tiene una implementación natural utilizando la recursión y es el ejemplo más claro. (Considera que este concepto a muchos usuarios se les dificulta la primera vez que lo revisan)
Antes de ver la implementación de código conviene revisar el concepto de factorial de un número:
El factorial es el resultado de multiplicar un número dado de enteros consecutivos de 1 al número dado. En la ecuación, está simbolizado por un signo de exclamación (!). Por ejemplo:
0! = 1
5! = 5 × 4 × 3 × 2 × 1 = 120
10! = 10 × 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1
El siguiente código muestra la implementación para obtener el Factorial de un número en C++
int factorial(int n)
{
if(n==1 || n==0) // condición de parada
return 1; return n*factorial(n-1); // Llamada recursiva a la función que lleva a la condición de parada
}
Si probamos este código para el número 5 tenemos
factorial(5)= 5 * factorial(4);
factorial(4)= 4 * factorial(3);
factorial(3)= 3 * factorial(2);
factorial(2)= 2 * factorial(1);
factorial(5)= 1; //para y devuelve la respuesta de la última llamada de la función.
factorial(2)= 21;
factorial(3)= 3 * 2;
factorial(4)= 4 * 6;
factorial(5)= 5 * 24 = 120;
A continuación puedes revisar el programa completo
// cpp_77_factorial.cpp
// 2019, Por http://about.me/carlosgbr
// Versión 1
// Revisa todo el código del tutorial en: https://github.com/carlosgbr/
// Compilado en https://www.onlinegdb.com/online_c++_compiler
include <iostream>
using namespace std;
long long factorial(long long n)
{
if(n==1 || n==0) // condición de parada
return 1;
return n * factorial(n - 1); // Llamada recursiva a la función y condición de parada
}
int main()
{
int n;
cin >> n;
cout<< "Factorial de "<< n <<" es " << factorial(n) << endl;
return 0;
}
Probablemente tenga sentido ampliar el funcionamiento de la función factorial.
Se ingresa 5 la condición n == 5 evalúa a falso, moviéndose a la función else que evalúa
n * factorial (n-1)
lo que eso significa
5 * (5-1)
lo cual es
5 * 4
entonces el factorial se llama a sí mismo
5 * 4 * (4-1)
lo cual es
5 * 4 * 3
entonces el factorial se llama a sí mismo
5 * 4 * 3 (3-1)
lo cual es 4 * 3 * 2
entonces el factorial se llama a sí mismo
5 * 4 * 3 * 2 (2-1)
lo cual es
5 * 4 * 2 * 3 * 1
ahora que ha alcanzado 1 factorial no se llamará más.
Una forma alterna de ver este mismo proceso es:
desde n = 5, llamas f(5) y esto sucede:
f(5) -> return 5 * f(4)
f(4) -> return 4 * f(3)
f(3) -> return 3 * f(2)
f(2) -> return 2 * f(1)
f(1) -> return 1 // n == 1
de modo que, f(5)
= 5 * ( f(4) = 4 * ( f(3) = 3 * ( f(2) = 2 * ( f(1) = 1 ) ) ) )
_ _
= 5 * 4 * 3 * 2 * 1
= 120
La iteración en computación es la técnica que marca un bloque de declaraciones dentro de un programa de computadora para un número definido de repeticiones. Se dice que ese bloque de declaraciones está iterado
La recursión en la computación es un método en el que la solución a un problema depende de soluciones para casos más pequeños del mismo problema.
La diferencia principal entre recursión e iteración es que una recursión es un proceso, siempre aplicado a una función.
La mayoría de los algoritmos que pueden ser descritos de forma iterativa (es decir, haciendo uso de bucles while, for…) pueden ser reescritos de forma recursiva, y viceversa.
Sí. Una prueba formal simple es mostrar que tanto la recursión µ como un cálculo no recursivo, como el GOTO, son Turing completos. Dado que todos los cálculos completos de Turing son estrictamente equivalentes en su poder expresivo, todas las funciones recursivas pueden implementarse mediante el cálculo de Turing no completo recursivo.
Konrad Rudolph
El tema de la recursión despierta siempre interesantes debates acerca de la conveniencia o no de utilizarla. Sin embargo casi siempre notarás que la discusión se centra al hablar de la programación del factorial de un número como acabamos de describir.
“El uso de la recursión te brinda la oportunidad de demostrar lo inteligente que eres, al tiempo que dificulta las cosas a todos los demás que tienen que trabajar en el código.”
Road Runner
“El uso adecuado de la recursión facilita la comprensión del código.”
Clayton Arends
Cualquier función recursiva puede escribirse sin llamadas recursivas, pero requiere que la función mantenga una lista interna de “pila” para impulsar el estado de ejecución. Esto puede hacer que el código sea más difícil de seguir y depurar.”
Blood
La recursión se implementa como pilas o construcciones similares en los intérpretes o compiladores reales. Así que ciertamente puedes convertir una función recursiva en una contraparte iterativa porque así es como siempre se hace (si es automáticamente). Simplemente duplicarás el trabajo del compilador de forma ad hoc y probablemente de una manera muy fea e ineficiente.
C Con clase
Y la discusión puede elevar el nivel (para argumentar o debatir) a medida que consideramos aspectos más avanzados en sistemas
“Realmente depende del contexto. Como regla general, tiene razón en que las llamadas a funciones adicionales, con sus marcos de pila y espacios de memoria, son menos eficientes que los bucles, pero existen varias advertencias importantes.”
Para empezar, muchos problemas solo pueden resolverse “eficientemente” ( (n ^ 2) o menos) con la recursión. Los ejemplos clásicos incluyen la -multiplicación campesina- que se beneficia de la optimización directa del hardware a través de instrucciones máquina de cambio de un solo bit.
En segundo lugar, normalmente los cursos básicos ignoran por completo la memoria y la recursión de la cola, cuya combinación elimina de manera efectiva los problemas de la memoria y los marcos de pila.
Por último, muchos lenguajes y compiladores están altamente optimizados uno sobre el otro, pero cuál es “mejor” depende del lenguaje específico. …algunos lenguajes funcionales como OCaml ni siquiera “técnicamente” admiten bucles (hay soluciones en OCaml, pero son menos eficientes que la recursión altamente optimizada de ese lenguaje).
Geof Colman
Inicia párrafo de autoría de Geof en Sololearn
Nunca, * NUNCA * escriba algo como esto en el código de producción. Siempre que tengas que realizar llamadas a funciones recursivas, a menos que sea absolutamente imposible de hacer (como en, digamos, el problema del logaritmo discreto o la factorización de números primos de los enteros), siempre busca una forma de memorizar y hacer que sea recursivo.
A modo de ejemplo:
int factorial (int n, int r) {
si (n == 0) {
return r;
}
else {
return factorial (n - 1, n * r);
}
}Este código elimina la necesidad de que el sistema operativo mantenga el marco de la pila para cada llamada de función recursiva en la memoria, en lugar de pasar los valores que deben ser “recordados” en cada paso como un argumento a la función. Esto mejora dramáticamente el rendimiento a medida que n crece.
El primer bloque de instrucciones (la declaración condicional y su cuerpo) es el “caso base”. Esto es lo que se devuelve después de que el algoritmo “toque fondo”, por así decirlo, como en su ejemplo.
La cláusula else se ejecuta para cualquier valor de n distinto de 1. Lo que sucede aquí es la magia de recursión real, ya que, al igual que sus ejemplos, la declaración de retorno decrece n antes de llamarse a sí misma recursivamente. La diferencia entre el ejemplo de recursión “tradicional” y este código, sin embargo, es que esta forma recursiva de cola recopila el resultado parcial hasta ahora (n * r) antes de la llamada recursiva. Esto reduce la carga en el entorno de ejecución para “recordar” todos esos cuadros de pila de llamadas recursivas, y se ejecuta exponencialmente más rápido a medida que n crece.
Termina párrafo de autoría de Geof en Sololearn
El programa para funcionar debe asignar r = 1, el código queda:
// cpp_78_factorial2.cpphttps://github.com/carlosgbr/
// Variación de una función recursiva para calcular el factorial de un número
// 2019, Por Geof en Sololearn &
// Versión 1
// Revisa todo el código del tutoral en: https://github.com/carlosgbr/
// Compilado en https://www.onlinegdb.com/online_c++_compiler
include
using namespace std;
long long factorial (long long n, long long r) {
if (n == 0) {
return r;
}
else {
return factorial (n - 1, n * r);
}
}
int main()
{
long long n;
cin >> n;
cout<< "Factorial de "<< n <<" es " << factorial(n,1) << endl;
return 0;
}
Termino esta sección con algunas rutinas desarrolladas con funciones recursivas para ampliar los ejemplos que regularmente se encuentran (que siempre se reducen al factorial).
Considera que la recursión tienen aplicación en la ciencia informática, no se puede descartar tan a la ligera como algunos blog sugieren.
// cpp_79_factorial3.cpp
// Se implementan varias funciones con técnicas recursivas
// Factorial, Fibonacci, Multiplicación y Potencia
// 2019, Adaptado a C++ Por http://about.me/carlosgbr
// Versión 1
// Revisa todo el código del tutoral en: https://github.com/carlosgbr/
// Compilado en https://www.onlinegdb.com/online_c++_compilerinclude <iostream>
using namespace std;
int factorial(int n){
if(n==0)
return 1;
else
return factorial(n-1)*n;
}
void factor(int n, int *res){
int aux;
if(n==0)
*res = 1;
else{
factor(n-1,&aux);
*res = aux * n;
}
}
int multiplicacion(int a, int b){
if(a==0 || b==0)
return 0;
else
return multiplicacion(a,b-1) + a;
}
int potencia(int a, int b){
if(b==0)
return 1;
else
return potencia(a,b-1) * a;
}
int fibonacci(int n){
if(n==1 || n==2)
return n-1;
else
return fibonacci(n-1) + fibonacci(n-2);
}
int main()
{
int n, solucion;
int a, b;
cout << "Ingrese numero : "; cin >> n;
cout << "El factorial de "<< n << " es " << factorial(n) << endl;
factor(n,&solucion);
cout << "El factorial de " << n << " es " << solucion << endl;
cout << "El termino " << n << " de fibonacci es " << fibonacci(n) << endl;
cout << "Ingrese valor de a : " << endl; cin >> a;
cout << "Ingrese valor de b : " << endl; cin >> b;
cout << a << " * " << b << " = " << multiplicacion(a,b) << endl;
cout << a << " elevado a " << b << " = " << potencia(a,b) << endl;
return 0;
}
Si no te queda del todo claro el tema de la recursividad, no lo tomes a mal, es uno de los temas típicos que siempre cuestan trabajo cuando se aborda por primera vez. Esto se ve reflejado con muchas de las frases que se han escrito con humor en relación a la recursión:
Recursividad en C++ by Roberto C. González is licensed under a Creative Commons Reconocimiento-NoComercial-CompartirIgual 4.0 Internacional License.
El comando dnsenum es una herramienta de línea de comandos para realizar enumeración de DNS…
En esta entrada te presento 24 de las listas negras más comunes que los servidores…
ZoomIt es una herramienta de anotación y zoom de pantalla para presentaciones técnicas que incluyen…
WinObj es el visor de espacios de nombres de Object Manager definitivo. Es la primera…
Whois realiza el registro de registro para el nombre de dominio o la dirección IP…
VolumeID – Esta utilidad, le permite cambiar los identificadores de los discos FAT y NTFS…