Recursividad

En su forma más simple recursividad se define como la habilidad de una función de llamarse a si mismo. Es un concepto bastante fácil de aprender pero difícil de aplicar.

#include
#include
#include
#include
#include

class Matematicas
{
public:
void Tablas(int T,int B)
{

if(B<11) n="="> "<:Fin<:endl; return; } Torres(N-1,Inicio,Fin,Aux); cout<:Inicio<<" --> "<:Fin<:endl; Torres(N-1,Aux,Inicio,Fin); return; } }tec; main() { int t,b,op=0; while(op!=5) { clrscr(); cout<<"\n1) Tablas de Multiplicar\n2) Factorial de un Numero\n"; cout<<"3) Formula Lineal\n4) Torres de Hanoi\n5) Salida"<:endl; gotoxy(1,1); cout<<"Que deseas hacer: "; cin>>op;

clrscr();
switch(op)
{
case 1:

cout<<"Que Tabla de Multiplicar deseas Imprimir?"<>t;
cout<<"Desde que Numero deseas empezar a multiplicar (Menor que 10)"<>b;
tec.Tablas(t,b);
break;

case 2:

cout<<"Que Factorial deseas conocer"<>t;
cout<:t<<"! = "<:tec.Factorial(t)<:endl; break; case 3: cout<<"f(x) = x^3 + 2x + 3"<:endl; cout<<"Escribe la Base (Menor de 10)"<>t;
tec.Formula(t);
break;

case 4:
cout<<"Cuantos discos deseas mover?"<>t;
tec.Torres(t,'A','B','C');
break;

case 5:

cout<<"Salida..."; break; default: cout<<"Opcion Erronea..."; break; } getch(); } }
[+/-] Ejemplo de Recursividad...

Características

• Ser una herramienta muy potente en determinadas aplicaciones,sobre todo de cálculo, pudiendo ser utilizada como alternativa a la repetición o estructura repetitiva.
• Toda función/método recursivo debe tener dos partes:

• i. una parte de terminación en la que se deja de hacer llamadas (es lo que denominaremos caso base) y que constituye la condición de terminación de la función,
• permitiendo así que no se produzca una recursión infinita.
• ii. y una llamada recursiva con sus propios parámetros, en los que éstos sufrirán alguna variación.

• Cuando una función se llama así misma, se denomina función recursiva y denominaremos a la llamada a sí misma llamada recursiva.

Un algoritmo recursivo es un algoritmo que expresa la solución de un problema en términos de una llamada a sí mismo. La llamada a sí mismo se conoce como llamada recursiva.

FUNCIÓN Factorial(n)
INICIO
SI (n<2) factorial =" 1;" factorial =" n" style="font-weight: bold;">Torres de Hanoi
Consiste en tres varillas verticales y un número indeterminado de discos que determinarán la complejidad de la solución. No hay dos discos iguales, están colocados de mayor a menor en la primera varilla ascendentemente, y no se puede colocar ningún disco mayor sobre uno menor a él en ningún momento.
El juego consiste en pasar todos los discos a la tercera varilla colocados de mayor a menor ascendentemente.
Las reglas son:

• Sólo se puede mover un disco cada vez.
• Un disco de mayor tamaño no puede descansar sobre uno más pequeño que él mismo.
• Sólo puedes desplazar el disco que se encuentre arriba en cada varilla.

Si numeramos los discos desde 1 hasta n, y llamamos X a la primera pila de discos (origen), Z a la tercera (destino) e Y a la intermedia (auxiliar) y a la función le llamaríamos hanoi (origen, auxiliar, destino), como parámetros, la función recibiría las pilas de discos. El algoritmo de la función sería el siguiente:

1. Si origen == {0}: mover el disco 1 de pila origen a la pila destino (insertarlo arriba de la pila destino); terminar.
2. Si no: hanoi({0...n-1},destino, auxiliar) //mover todas las fichas menos la más grande (n) a la varilla auxiliar
3. mover disco n a destino //mover la ficha grande hasta la varilla final
4. hanoi (auxiliar, origen, destino) //mover todas las fichas restantes, {0...n-1}, encima de la ficha grande (n)
5. terminar

Veamos el algoritmo en pseudo código

Hanoi( int n, int start, int destination, int open )
Hanoi( n - 1, start, open, destination )
Move( n, start, destination )
Hanoi( n - 1, open, destination, start )