Primeramente, no todos los lenguajes de programación aceptan la recursividad. Dicho esto empezamos: Se dice que una función es recursiva cuando, dicha función, requiere de su propia ejecución un número indefinido de veces para poder terminar adecuadamente. No todas las funciones pueden ser recursivas, el hecho de que sean recursivas ha de darse porque hayan sido diseñadas para ello.
Cuando se llama a una función, las variables creadas locales se guardan en una pila, de este modo, cuando la función hace una llamada a si misma, se guardan sus variables y el parámetro hasta que la función retorna su resultado recuperando las variables y los parámetros de la pila y prosiguiendo así su ejecución en el punto de inicio.
Ejemplo de recursividad:
El programa leerá una secuéncia de palabras y las escribirá en el orden inverso.
#include <iostream>
using namespace std;void palabra (){
string n;
if(cin >> n){palabra ();
cout<<n<<endl;}
}
int main (){
palabra ();}
El main en este caso sólo llamará a la función palabra.
Cada vez que se ejecute la función se creará la variable n que se irá guardando en una pila. Cuando la instrucción if(cin>>n) sea falsa empezará la ejecución desde la última instancia, es decir la última palabra introducida, hasta acabar al punto de inicio y ejecutarlo.
El dibujo es un ejemplo para entenderlo mejor: cada escalón es una iteración del programa, cuando se llama a la función, se crea un nuevo escalón y la función actual queda pausada. Cuando llega al final vuelve iteración por iteración ejecutando el código restante hasta acabar la primera.
Otro ejemplo:
Esta vez haremos una función recursiva que resuelva los números factoriales.
#include <iostream>
using namespace std;int factorial (int n){
if (n == 0){
return 1;}
else{return n * factorial(n – 1);}
}
int main(){
int n;
cin>>n
cout<<factorial(n)<<endl;}
La función devolverá «1» si n es «0» sino ara la multiplicación de n * factorial(n-1).
Para que veáis más claro cómo funciona haremos una ejecución del programa: Usando como n=4. (4 es el numero que introduciremos en el main) y ejecutamos la función.
- (En esta iteración n = 4) como n es diferente de 0 ejecutará return n * factorial(n-1) «Esto significa que ejecutará otra instancia donde n = n-1»
- (En esta iteración n = 3) volverá a ejecutarse igual y así durante los siguientes ciclos hasta llegar a 0
- (En esta iteración n = 2) ……
- (En esta iteración n = 1) ……
- (En esta iteración n = 0) como n = 0 devolverá 1 «lo que significa que acabado el bucle de ejecución, volverá iteración tras iteración hasta llegar al inicio»
- (En esta iteración n = 1) el código anteriormente ejecutado ahora tiene un resultado ya que factorial(n-1) = 1, por lo tanto ejecutara return n*(1) y así en todos los ciclos cargando el resultado del anterior.
- (En esta iteración n = 2) ejecutará return n*(1*1).
- (En esta iteración n = 3) ejecutará return n*(1*1*2).
- (En esta iteración n = 4) ejecutará return n*(1*1*2*3).
- Vuelve a la función de main mostrando el resultado final en el que n= (1*1*2*3*4).
Y ahora os toca practicar!