Recursividad

Se dice que una función es recursiva cuando se invoca a si misma.

No todas la funciones pueden llamarse a si mismas, sino que deben estar

diseñadas especialmente para que sean recursivas, de otro modo podrían
conducir a bucles infinitos, o a que el programa termine inadecuadamente.

Tampoco todos los lenguajes de programación permiten usar recursividad.

C++ permite la recursividad. Cada vez que se llama a una función, se crea un
juego de variables locales, de este modo, si la función hace una llamada a si
misma, se guardan sus variables y parámetros en la memoria en forma de pila
(mas adelante se tocara este tema de pila) , y la nueva instancia (invocación o
llamada) de la función trabajará con su propia copia de las variables locales.
Cuando esta segunda instancia de la función retorna, recupera las variables y los
parámetros de la pila y continua la ejecución en el punto en que había sido
llamada.

Las funciones en C y C++ pueden ser recursivas, en otras palabras, pueden

llamarse a sí mis-mas directa o indirectamente. La recursividad directa es el
proceso mediante el que una función se llama a sí misma desde el propio cuerpo
de la función, mientras que la recursividad indirecta implica más de una función.
Un proceso recursivo tiene que tener una condición de finalización, ya que de lo
contrario podría continuar infinitamente.

La forma más simple de hacer que una función recursiva no cree un bucle infinito
es hacer que la llamada a si misma está dentro de una estructura condicional. De
esta forma solo si se cumplen ciertas condiciones la ejecución de la función se
repite.

El siguiente ejemplo pide al usuario que pulse una tecla numérica. Mediante una
función comprobamos la tecla pulsada. Si esta es un numero se sale de la función,
pero si no lo es vuelve a pedir que se pulse una tecla, se llama a si misma para
volver a comprobarlo.

#include<iostream>

using namespace std;

void comprobar(char r);

int main(){

char c;

cout << "Pulsa un numero : ";

cin >> c;

comprobar(c);

cout << "Programa terminado." << endl;

void comprobar(char r){

int n=int(r);

if (n>=48 and n<=57) { // siempre debe haber un chequeo para que tenga fin

//la recursividad

cout << "Correcto, la tecla pulsada es un numero." << endl;

else {

cout << "Incorrecto, la tecla pulsada NO es un numero." << endl;

cout << "Vuelve a pulsar un numero : ";

cin >>r;

comprobar(r);

El programa tiene una función recursiva, la cual crea un bucle del que no se sale
hasta que el usuario pulsa una tecla numérica.
Observa como la llamada a la función dentro de la misma está dentro de una
estructura condicional. Cuando se cumplen las condiciones marcadas por la
condicional se sale del bucle, si no se cumplen, la función vuelve a repetirse.

La recursividad es un tema importante en el mundo de la programación, la utilidad

de este tipo de funciones se aprovecha en el diseño de algoritmos de criptografía,
de búsqueda, entre otros. La implementación de la recursividad en nuestros
programas debe evaluarse con mucho cuidado, debemos tratar de evitar que se
usen funciones de complejidad exponencial, que se llamen a sí mismas una y otra
vez sin que se tenga un control claro.

Un ejemplo clásico para este problema es el factorial de un número, (n!). :

Conociendo los casos base 0! = 1 y 1!=1, se sabe que la función factorial puede
definirse como n!=n*(n-1)!, entonces 7!=6*5! que a su vez 7*6! que a su vez
7*6*5! que a su vez 7*6*5*4*3! que a su vez es 7*6*5*4*3*2! entonces
7*6*5*4*3*2*1! y por último 7*6*5*4*3*2*1*0! llegando al caso base.
Esto nos lleva a la idea de función recursiva. Una función de este tipo es una
función que dentro de su código se llama a si misma. Se pasa como parámetro
una versión más sencilla del problema, hasta llegar a un caso que no puede
simplificarse más. Veamos un ejemplo en pseudocódigo:

Toda función recursiva tiene por lo menos dos condicionales. El primero (en verde)
se llama el caso base. Este caso dice a la función cuándo debe parar de llamarse
a si misma.

El segundo caso (azul) es el caso recursivo. Si no se cumple el caso base, la

función se llamará a si misma pasando como parámetro una versión más
simplificada del problema.
Vamos a ver que pasaría al calcular, por ejemplo, 5!…
 Cada llamada recursiva genera una entrada a una pila(el tema de pila se abordara
mas adelante) creada en memoria ram, en donde se guardan (como elementos)
los estados generales del sistema al momento de hacer la llamada la función
recursiva, entonces, cuando se termina las llamadas se recupera una por una las
entradas de la pila. En la figura siguiente ilustra cómo funciona la recursividad
cuando se intenta obtener el factorial(5). Lo que esta letras negras
representa las llamadas a la función recursiva y lo que esta en rojo
representa la salida de los datos de la pila para ir calculando el factorial
por cada llamada, hasta obtener el valor final que es 120

Por ejemplo en lenguaje C y sustituyendo a n por numero

:
Se deben satisfacer dos condiciones para que se pueda resolver un problema
recursivamente:

Primera: El problema se debe escribir en forma recursiva.

Segunda: La sentencia del problema debe incluir una condición de fin.

La solución a este problema en lenguaje C++ podría realizarse sin tener que
utilizar la recursividad como se muestra en el siguiente programa:

#include <stdio.h>

using namespace std;

int factorial(int numero);

int main(){

int valor = 4;

int resultado;

resultado = factorial(valor);

cout<<"El factorial de: "<< valor<< resultado;

return 0;

}
int factorial(int numero){

int i;int devuelve = 1;

for(i = 1; i <= numero; i++)

{devuelve = devuelve * i;

return devuelve;

Sin embargo, resulta más intuitivo dada la definición de número factorial utilizar
una función recursiva como la siguiente:
int factorial(int numero)
{if(numero == 1)return 1;
Else return (numero * factorial(numero-1));
}

En la función anterior, en el caso de que el argumento utilizado en la llamada sea

1, ésta devuelve 1, y en caso contrario se calcula un producto que involucra a la
variable numero y una nueva llamada a la función cuyo argumento es menor en
una unidad (numero -1).El funcionamiento de una función recursiva se realiza
almacenando las llamadas pen-dientes, con sus argumentos, en la pila en tiempo
de ejecución. Veamos un ejemplo: imagina que utilizamos el valor 4como
argumento de la función que calcula el facto-rial, es decir, factorial(4),el proceso
de llamadas será el siguiente:
La implementación completa en C++

#include<iostream>
using namespace std;

//Funcion recursiva
unsigned long int factorial(int n)
{
//Caso base:
if(n == 1)
return 1;

//Caso recursivo
else
return n*factorial(n-1);
}

int main(void)
{
int val; //El entero del que queremos calcular el factorial
unsigned long int result; //El resultado del factorial
 //Leemos un entero y lo guardamos en val
cout << "\nIntroduce valor" << endl;
cin >> val;

result = factorial(val); //Aqui calculamos el factorial y lo guardamos en result

cout << "El resultado de " << val << "! es " << result << endl << endl;

return 0;

En muchas ocasiones, la resolución de un problema mediante una función

recursiva resulta conceptualmente más clara que la resolución mediante una
función iterativa. Tales el caso de algunas estructuras de datos como los árboles
binarios (el tema de árbol se aborda luego) , cuyo manejo es sencillo mediante
una función recursiva. Sin embargo, la función iterativa resulta algo más compleja.
Es evidente que hay tareas que se pueden resolver mediante funciones recursivas
o funciones iterativas, aunque es el programador el que tiene que optar por una
solución u otra.

Otro ejemplo: visualizar las permutaciones de n elementos.

Las permutaciones de un conjunto son las diferentes maneras de colocar sus

elementos, usando todos ellos y sin repetir ninguno. Por ejemplo para A, B, C,
tenemos: ABC, ACB, BAC, BCA, CAB, CBA.

#include <iostream>

using namespace std;

/* Prototipo de función */

void Permutaciones(char *, int l=0);

int main() {

char palabra[] = "ABCDE";

 Permutaciones(palabra);

[Link]();

return 0;

void Permutaciones(char * cad, int l) {

char c; /* variable auxiliar para intercambio */

int i, j; /* variables para bucles */

int n = strlen(cad);

for(i = 0; i < n-l; i++) {

if(n-l > 2) Permutaciones(cad, l+1);

else cout << cad << ", ";

/* Intercambio de posiciones */

c = cad[l];

cad[l] = cad[l+i+1];

cad[l+i+1] = c;

if(l+i == n-1) {

for(j = l; j < n; j++) cad[j] = cad[j+1];

cad[n] = 0;

El algoritmo funciona del siguiente modo:

Al principio todos los elementos de la lista pueden cambiar de posición, es decir,

pueden permutar su posición con otro. No se fija ningún elemento de la lista, l = 0:
Permutaciones(cad, 0)
0 1 2 3 4

A B C D /0

Se llama recursivamente a la función, pero dejando fijo el primer elemento, el 0:

Permutacion(cad,1)

0 1 2 3 4

A B C D /0

Se llama recursivamente a la función, pero fijando el segundo elemento, el 1:

Permutacion(cad,2)

0 1 2 3 4

A B C D /0

Ahora sólo quedan dos elementos permutables, así que imprimimos ésta
permutación, e intercambiamos los elementos: l y l+i+1, es decir el 2 y el 3.

0 1 2 3 4

A B D C /0

Imprimimos (mostrar por pantalla) ésta permutación, e intercambiamos los

elementos l y l+i+1, es decir el 2 y el 4.

0 1 2 3 4

A B /0 C D

En el caso particular de que l+i+1 sea justo el número de elementos hay que
mover hacia la izquierda los elementos desde la posición l+1 a la posición l:

0 1 2 3 4

A B C D /0

En este punto abandonamos el último nivel de recursión, y retomamos en el valor

de l=1 e i = 0.

0 1 2 3 4

A B C D /0

Permutamos los elementos: l y l+i+1, es decir el 1 y el 2.

0 1 2 3 4

A C B D /0

En la siguiente iteración del bucle i = 1, llamamos recursivamente con l = 2:

Permutaciones(cad,2)

0 1 2 3 4

A C B D /0

Imprimimos la permutación e intercambiamos los elementos 2 y 3.

0 1 2 3 4

A C D B /0

Y así sucesivamente.

Otras formas de recursividad

Existen otras formas de implementar algoritmos recursivos, no es necesario que

una función se invoque a si misma.

Por ejemplo, un par de funciones A y B pueden crear un algoritmo recursivo si la

función A invoca a la función B, y esta a su vez invoca a la función A.

Este mismo mecanismo se puede implementar con tres, cuatro o con cualquier
número de funciones.

Veamos un ejemplo. Partamos de la siguiente serie:

1 - 1/2 + 1/3 - 1/4 + 1/5 - ... - 1/2*n + 1/2*n+1 - ...

Podemos diseñar un procedimiento recursivo para calcular la suma de los n

primeros elementos de la serie, de modo que usemos una función diferente para
los elementos pares e impares.

// Suma de la serie 1-1/2+1/3-1/4+1/5...

#include <iostream>

using namespace std;

double par(int);

double impar(int);
double suma(int);

int main() {

cout << suma(3) << endl;

cout << suma(13) << endl;

cout << suma(23) << endl;

cout << suma(87) << endl;

cout << suma(250) << endl;

cout << suma(450) << endl;

return 0;

double suma(int n) {

if(n % 2) return impar(n);

else return par(n);

double par(int n) {

return impar(n-1)-1/double(n);

double impar(int n) {

if(n == 1) return 1;

return par(n-1)+1/double(n);

}
Otro ejemplo

Mas ejemplo:

En este ejemplo vamos a hacer que el usuario escriba una frase y nosotros la
repetimos un determinado número de veces.

Evidentemente será mucho más fácil resolver el problema utilizando un bucle,

pero aquí se trata de ver cómo se puede resolver también mediante una función
recursiva. Veamos el ejemplo :

#include<iostream>

using namespace std;

void escribir(string frase, int n);

int main(){

string f;

int n=5;

cout << "Escribe una frase. Yo la repetire 5 veces." << endl;

getline(cin, f);

cout << endl;

escribir(f,n);

void escribir(string frase, int n){

cout << n << " : " << frase << endl;

n--;

if (n>0) escribir(frase,n);

Observa como tenemos un numero de control, n que en cada llamada va

disminuyendo en una unidad. A su vez el hecho de que se produzca o no la
siguiente llamada a la función depende de que el número sea mayor que cero, por
lo que cuando el numero alcance el cero, la función dejar de autor replicarse.

Otro ejercicio

La serie Fibonacci

Una de las series más famosas es sin duda alguna la serie de Fibonacci:

1, 1, 2, 3, 5, 8, 13, 21, 34, . . .

Un poco de observación es suficiente para encontrar que cualquier número (a

partir del tercero de la serie, ósea el segundo 1) es igual a la suma de los dos
números anteriores.

Daremos en primer lugar la versión iterativa. En este algoritmo deseamos

encontrar el n-esimo número de la serie Fibonacci. Así si n = 4 el resultado del
algoritmo debe ser 3; si n = 6 el resultado debe ser 8. La versión iterativa empieza
desde los primeros 1’s, sumándolos y encontrando el tercero, luego para encontrar
el cuarto número se suman el tercero (recién encontrado) y el segundo, y así en
adelante hasta encontrar el número buscado.

#include <iostream>

using namespace std;

int main () {

int i,n,fib,fib1,fib2,fibx;

cout<<"Un numero entero:";

cin>>n;
fib1=2; fib2=1; i=3;

if ((n==1)||(n==2)) fib=1;

else{ do{

fib = fib1 + fib2; fibx = fib1;

i++;

fib1 = fib;

fib2 = fibx;

}while(i<n);

cout << "\nEl "<<n<<"-esimo numero de la serie Fibonacci es: "<<fib;

return 0;

La definición recursiva para encontrar todos los n primeros números de la serie

Fibonacci es:

fib(n) = 1 Si n = 1 ´o n = 2

fib(n − 1) + fib(n − 2) Si n > 2

En el siguiente código enumerado, la solución que propone la recursividad resulta

en una programación elegante, aunque costosa. El código que hace esto es:

( 1) #include <iostream>

( 2) using namespace std;

( 3) int fib(int val){

( 4) if ((val==1)||(val==2)) ( 5) return 1;

( 6) else
( 7) return (fib(val-1)+fib(val-2)); ( 8) }

( 9) //====================

(10) int main () {

(11) int n;

(12) cout<<"Numero entero:"; std::cin>>n;

(13) cout<<"\nEl "<< n

(14) <<"-esimo numero fibonacci es: "<< fib(n);

(15) return 0;

(16) }

Como regla general, cualquier algoritmo recursivo se puede reescribir en un

algoritmo iterativo. La ventaja de tener un algoritmo iterativo es que no se usa una
pila para guardar llamadas a la misma función de manera recursiva, esto es una
ventaja porque el espacio de memoria destinado al uso de la pila es generalmente
limitado, de manera que cuando se hacen demasiadas funciones push(entrada de
datos a la pila) seguramente llegará el momento en que la pila “se desborde”, que
por cierto es un término usado en computación para decir que ya no hay más
espacio disponible en la pila.

Peligros en la recursividad

El principal peligro al usar recursividad, es no tener una manera de salir del paso
recursivo, esto es peligroso porque se hacen llamadas a la misma función, lo que
significa una entrada en la pila donde se almacenan los estados generales del
programa.

Para decidir hacer un programa recursivo se deben de tener al menos dos cosas
muy claras:

1. El paso base: Esta es la clave para terminar la recursión, es cuando deja de

hacer llamadas a la función recursiva y hace evaluaciones devolviendo los
resultados. En el ejemplo de la serie de Fibonacci, el paso base está en la línea (
5). Además se debe asegurar de que es posible entrar a este paso.
2. El paso recursivo: Es la parte de la definición que hace llamadas a esa
misma función y que es la causante de las inserciones en la pila, almacenando en
cada una de las llamadas, información del programa, del estado de sus variables
locales y globales. En el mismo ejemplo de la serie Fibonacci, el paso recursivo se
muestra en la línea ( 7).

Otras cosas que se deben tener claras son por ejemplo si se pasa una variable
como referencia o por valor, si las variables apuntadores son del tipo adecuado
etc.

Frecuentemente tanto el paso base como el paso recursivo, se encuentran en una

sentencia condicional if, pero por supuesto que es posible usar cualquier otra
sentencia de control, dependiendo de las necesidades particulares del problema.

El siguiente ejemplo ilustra este problema

( 1) #include <iostream>

( 2) using namesapce std;

( 3) int malaFuncion( int n ){

( 4) cout << "malaFuncion es una recursion infinita. n="<<n;

( 5) if( n == 0 )

( 6) return 0;

( 7) else

( 8) return malaFuncion( n / 3 + 1 ) + n - 1;

( 9) }

( 10) int main () {

(11) cout << malaFuncion(10);

(12) return 0;

(13) }

Ejercicios propuestos
1.-Funcion que determine si una cadena de caracteres es o no palíndroma.

2.-Veamos ahora un problema clásico: las torres de Hanói.

Torres de Hanói

Torres de Hanói

El juego consiste en tres varillas verticales. En una de ellas están apiladas un

número de discos, generalmente ocho, de diámetros diferentes, ordenados de
mayor a menor (el de mayor diámetro abajo). Las otras dos varillas están vacías.
El juego consiste en pasar todos los discos de la varilla ocupada a una de las
varillas libres.

Para llegar a ese objetivo hay que respetar tres reglas:

Sólo se puede mover un disco cada vez.

Un disco de mayor tamaño no se puede colocar encima de uno más pequeño.

Sólo se puede mover el disco que se encuentre en la parte superior de cada

varilla.

Resolver el juego usando algoritmos recursivos.