De decimal a octal con una función recursiva

Éste programa es una consecuencia natural de la entrada anterior. Es tan simple como cambiar 2 por 8. En realidad, como puede verse, éste procedimiento sirve para convertir de decimal a cualquier base posicional entre 2 y 9. También es posible usarlo para una conversión a sistema hexadecimal.

#include <stdio.h>

/*////////////////////////////////////
 * Funcion Octal                     *
 *///////////////////////////////////*/

void Octal( int x)

{  /* Abre Octal*/
if ( x != 0 )
{ /* Abre if*/
Octal(x/8);

printf("%d\t", x%8);
} /*Cierra if */

else;
 /*printf("0\n");*/

}  /*Cierra Octal*/

/****************************************
 * main                                 *
 ***************************************/
int main()

{  /*Abre main */
 int num; 

 printf("\nIntroduzca un numero entero: ");
 scanf("%d", &num);

 Octal(num);
 printf("\n");

 return 0;
}  /*Cierra main */

Y aquí una ejecución, con el número 100 como entrada

[hernandez@localhost Programas]$ ./a.out 

Introduzca un numero entero: 100                                                     
1       4       4                   

De decimal a binario con una función recursiva

Tengo una versión de éste programa que es bastante más complicada, pero por mucho tiempo recordé que lo había visto resuelto usando recursión. Ahora he pensado algunas formas de hacerlo, por ejemplo ésta:
Supongamos que tenemos el número 41, y que queremos convertirlo de su notación decimal a binario.

41 En binario  = 1 0 0 0 0 0 + (41 - 32) En binario

                                   9 En binario = 1 0 0 0 +  (9 - 8) En binario

                                                                1 En binario = 1.

El problema se va reduciendo cada vez por medio de llamadas a sí mismo con argumentos más simples. Al final sólo es necesario sumar las representaciones binarias de 32 + 8 + 1. Sin embargo no es ésto lo que yo quiero aquí. Además, sumar será en éste caso más complicado que la propia conversión. Por lo tanto descarté ésta posibilidad.
Otra forma es sugerida por el siguiente proceso, que puede encontrarse por ejemplo en el libro de Diseño Digital, de Morris Mano:

Número          División       Residuo          Binario
  41/2     =       40/2    +     1/2              1
  
  20/2     =       20/2    +      0               0

  10/2     =       10/2    +      0               0
 
   5/2     =        4/2    +     1/2              1
 
   2/2     =        2/2    +      0               0

   1/2     =          0    +     1/2              1

Éste algoritmo es fácilmente programable usando el operador %. Sin embargo, tiene el gran inconveniente de que los dígitos se imprimen en el orden inverso, como puede verse al ejecutar el siguiente código

#include <stdio.h>

/*////////////////////////////////////
 * Funcion Binario                   *
 *///////////////////////////////////*/

void Binario( int x)

{  /* Abre binario*/
if ( x != 0 )
{ /* Abre if*/
printf("%d\t", x%2);

Binario(x/2);

} /*Cierra if */

else;
 /*printf("0\n");*/

}  /*Cierra binario*/

/****************************************
 * main                                 *
 ***************************************/
int main()

{  /*Abre main */
 int num; 

 printf("\nIntroduzca un numero entero: ");
 scanf("%d", &num);

 Binario(num);

 return 0;
}  /*Cierra main */

La ejecución es la siguiente

[hernandez@localhost Programas]$ ./a.out 

Introduzca un numero entero: 41
1       0       0       1       0       1  

De nuevo el problema es que se está imprimiendo el número al revés. Ésto es grave, porque el código es muy bueno, y cualquier intento por corregir el defecto, requiere algoritmos más complicados que la propia conversión.
Sin embargo, después de pensarle, la solución es muy simple. En la función Binario, basta con cambiar el orden de los dos únicos enunciados. Primero hay que hacer una llamada a Binario, y ésto llevará la ejecución hasta el final, hasta el caso más simple, y el control se regresará desde el último caso, imprimiendo los dígitos binarios en el orden inverso. El programa correcto es el siguiente:

#include <stdio.h>

/*////////////////////////////////////
 * Funcion Binario                   *
 *///////////////////////////////////*/

void Binario( int x)

{  /* Abre binario*/
if ( x != 0 )
{ /* Abre if*/
Binario(x/2);

printf("%d\t", x%2);
} /*Cierra if */

else;
 /*printf("0\n");*/

}  /*Cierra binario*/

/****************************************
 * main                                 *
 ***************************************/
int main()

{  /*Abre main */
 int num; 

 printf("\nIntroduzca un numero entero: ");
 scanf("%d", &num);

 Binario(num);

 return 0;
}  /*Cierra main */

La ejecución,

[hernandez@localhost Programas]$ ./a.out 

Introduzca un numero entero: 41
1       0       1       0       0       1

Comopuede verse, son muy pocas las líneas que se requieren para hacer la conversión de binario a decimal usando la recursión, y es un cambio mínimo el que hace esta diferencia.

Deitel_C++_3.45 (Maximo Comun Divisor en forma recursiva)

_____________________________________________________________________________________
3.45 (Recursividad para el Máximo Común Divisor) El máximo común divisor de los enteros x y y es el entero más grande que divide tanto a x como a y. Escriba una función reursiva mcd que devuelva el máximo común divisor de x y y, la cual está definida recursivamente de la siguiente manera: se y es igual a 0, entonces, mcd(x, y) es x; de otro modo, mcd(y, x%y), donde % es el operador módulo.
_____________________________________________________________________________________
El programa es bastante simple, y la función gcd está definida exactamente como se especifica en el enunciado del problema. El programa en sí mismo es bastante fácil de leer y seguir. Cópielo, ejecútelo y modifíquelo para mejorarlo si quiere.

////////////////////////////////////////////////////////////
//                                                        //
// Este programa recibe un par de enteros positivos y     //
// calcula el maximo comun divisor mediante la recursion  //
////////////////////////////////////////////////////////////
   
#include <iostream>
using namespace std;
int gcd (int, int);

int main()

{       /*Abre main*/
unsigned int a, b, max;

cout <<"\n\nSe calcula el maximo comun divisor de dos numeros."<<endl;
cout <<"Introduzca dos numeros enteros no negativos: "<<endl;
cin >> a >> b;

if ( a >= b )
max = gcd (a,b);
else
max = gcd (b,a);
cout <<"\nEl maximo comun divisor de los numeros es: "
<<max << endl;
 
return 0;
}     /*Cierra main*/

//////////////////////////////////////////////////////////////////////
// FUNCION GCD
//////////////////////////////////////////////////////////////////////

int gcd (int x, int y)

{            /*Abre gcd*/
if (0 == y)
return x;
else
return gcd (y, x%y);
}           /*Cierra gcd*/

Una ejecución de éste programa es la siguiente

[hernandez@localhost Programas]$ ./a.out 
Se calcula el maximo comun divisor de dos numeros.
Introduzca dos numeros enteros no negativos: 

568
456

El maximo comun divisor de los numeros es: 8

Deitel_C++_3.44 (Visualización de la Recursión en C++ con Factorial de 10)

_____________________________________________________________________________________
3.44 (Visualización de la recursividad) Es interesante observar a la recursividad en "acción". Modifique la función factorial de la figura 3.14 para que despliegue su variable local y el parámetro de llamada recursiva. Por cada llamada recursiva, despliegue los resultados en una línea diferente y agregue un nivel de sangrado. Haga su mayor esfuerzo para que sus resultados sean claros, interesantes y útiles. Su objetivo aquí es diseñar e implementar un formato para los resultados que ayude a una persona a comprender mejor la recursividad. Tal vez desee agregar dichas capacidades de despliegue a los muchos otros ejemplos y ejercicios sobre recursividad que contiene el libro.
_____________________________________________________________________________________
Solución:

// Calculo de factoriales.
    #include <iostream>
     #include <iomanip>
     using namespace std;
     using std::setw;
    unsigned long factorial (unsigned long);
 
   int main()

    {
    cout <<endl<<endl<<"Se presentan los factoriales de los primeros";
    cout <<" 10 enteros."<<endl;
    for ( int i = 0; i <= 10; i++)
       cout << setw(2) << i << "! = " <<factorial(i) << endl;

    return 0;

  }

  ////////////////////////////////////////////////////
  // FACTORIAL
  ////////////////////////////////////////////////////
    unsigned long factorial (unsigned long number)

   {
    if ( number <= 1 )
    return 1;
    else

    {
    cout <<number <<" Llamada recursiva a factorial de: "
         << number - 1<< endl;
    return number * factorial(number-1);

    }
   }

la ejecución del programa produce la siguiente salida:

Se presentan los factoriales de los primeros 10 enteros.
 0! = 1
 1! = 1
2 Llamada recursiva a factorial de: 1
 2! = 2
3 Llamada recursiva a factorial de: 2
2 Llamada recursiva a factorial de: 1
 3! = 6
4 Llamada recursiva a factorial de: 3
3 Llamada recursiva a factorial de: 2
2 Llamada recursiva a factorial de: 1
 4! = 24
5 Llamada recursiva a factorial de: 4
4 Llamada recursiva a factorial de: 3
3 Llamada recursiva a factorial de: 2
2 Llamada recursiva a factorial de: 1
 5! = 120
6 Llamada recursiva a factorial de: 5
5 Llamada recursiva a factorial de: 4
4 Llamada recursiva a factorial de: 3
3 Llamada recursiva a factorial de: 2
2 Llamada recursiva a factorial de: 1
 6! = 720
7 Llamada recursiva a factorial de: 6
6 Llamada recursiva a factorial de: 5
5 Llamada recursiva a factorial de: 4
4 Llamada recursiva a factorial de: 3
3 Llamada recursiva a factorial de: 2
2 Llamada recursiva a factorial de: 1
 7! = 5040
8 Llamada recursiva a factorial de: 7
7 Llamada recursiva a factorial de: 6
6 Llamada recursiva a factorial de: 5
5 Llamada recursiva a factorial de: 4
4 Llamada recursiva a factorial de: 3
3 Llamada recursiva a factorial de: 2
2 Llamada recursiva a factorial de: 1
 8! = 40320
9 Llamada recursiva a factorial de: 8
8 Llamada recursiva a factorial de: 7
7 Llamada recursiva a factorial de: 6
6 Llamada recursiva a factorial de: 5
5 Llamada recursiva a factorial de: 4
4 Llamada recursiva a factorial de: 3
3 Llamada recursiva a factorial de: 2
2 Llamada recursiva a factorial de: 1
 9! = 362880
10 Llamada recursiva a factorial de: 9
9 Llamada recursiva a factorial de: 8
8 Llamada recursiva a factorial de: 7
7 Llamada recursiva a factorial de: 6
6 Llamada recursiva a factorial de: 5
5 Llamada recursiva a factorial de: 4
4 Llamada recursiva a factorial de: 3
3 Llamada recursiva a factorial de: 2
2 Llamada recursiva a factorial de: 1
10! = 3628800

Deitel_C++_3.42 (Torres de Hanoi en C++, Version Recursiva)

_____________________________________________________________________________________
3.42 (Las Torres de Hanoi) Cada científico de la computación en ciernes debe batallar con ciertos problemas clásicos. Las Torres de Hanoi representan uno de los más famosos. La leyenda cuenta que en un templo del lejano oriente, unos sacerdotes intentan mover una pila de discos de una pila a otra. La pila inicial tiene 64 discos y están acomodados de abajo hacia arriba en orden de tamaño decreciente. Los sacerdotes intentan mover la pila de esta pila hacia una segunda, con las restricciones de mover sólo un disco a la vez, y que ningún disco más grande debe colocarse en encima de uno más pequeño. Una tercera pila está disponible para alojar temporalmente los discos. Se supone que el mundo terminará cuando los sacerdotes completen su tarea, por lo cual no hay ningún incentivo para facilitarles la tarea.
_____________________________________________________________________________________

Antes de intentar resolver este problema es bueno conseguirse un juego de torres de hanoi por ahi, los he visto en puestos callejeros de ajedrez, cartas, etc.; o improvisar uno, como hacen en las ferias de ciencias; tal vez la primera impresion sea que es complicado, sin embargo no tardaran en darse cuenta de que una vez que logran agarrar la idea, la solucion es bastante aburrida, solo hay que repetir una y otra vez el mismo procedimiento. Es por eso que este problema es tan susceptible de ser resuelto mediante la recursion. Se daran cuenta de que hay que solucionarlo de abajo para arriba. Tienen que mover el disco que esta en el fondo hacia la espiga de destino, para hacer esto tienen que mover una torre un poco menor (de solo N-1 discos) hacia la espiga destino. Este ultimo paso es crucial. Es muydiscos) hacia la espiga intermedia y entonces si mover el disco mas grande a su destino. Ahora lo que falta es mover la torre de N - 1 discos que esta en la importante darse cuenta de que la torre con N - 1 discos se mueve DOS VECES, la primera hacia la espiga intermedia y la segunda hacia la espiga de destino despues de haber movido el disco de abajo. Si logran comprender esto entonces ya resolvieron el problema, solo hagan lo mismo con todas las torres hasta que lleguen a tener una torre con un solo disco. En ese caso limite ya no necesitan usar una espiga intermedia, pueden pasar directamente el disco del origen al destino.

# include <iostream>

using namespace::std;

////////////////////////////////////////////////////////////////////

// FUNCION MOVER_TORRES

////////////////////////////////////////////////////////////////////

void Mover_Torres(int N, int Origen, int Intermedio, int Destino)

{ // Abre funcion Mover_Torres

if ( N > 1 )

{ // Abre if
Mover_Torres( N - 1, Origen, Destino, Intermedio);

/* Se mueve una torre de N - 1 discos desde la espiga origen
pero hacia la espiga intermedia ( para dejar la destino libre)
usando la espiga destino como intermedia cout << "\nMueve disco "
<< N << " de " << Origen << " a " << Destino <<endl;
con esta instruccion mueven el disco de la base hacia su destino
Como comento arriba, ahora hay que mover nuevamente la torre de
N - 1 discos hacia el destino original ( en donde se ha puesto el
disco mayor ) Esto implica una segunda llamada recursiva. Ahora
el origen es la espiga intermedia a la que se movio la torre y
el destino es el destino primitivo,lo que originalmente era el
origen se usa ahora como espiga intermedia */

cout <<"\nMueve el disco " <<  N  << " de " << Origen << " a " <<  Destino << endl;
Mover_Torres( N - 1, Intermedio, Origen, Destino);
} // Cierra if

// El caso limite mas sencillo se resuelve directamente

if ( 1 == N )
cout << "\nMueve el disco 1 de " << Origen << " a " << Destino << endl;

} // Cierra funcion Mover_Torres

int main()

{ // Abre funcion main
int Discos;
cout << "\nEste programa resuelve el problema clasico de las Torres de Hanoi";
cout <<" mediante la recursion." << endl;
cout << "\nPor favor introduzca el numero de discos que quiere mover ";
cout << " de la pila 1 a la pila 3" << endl;
cin >> Discos;

Mover_Torres( Discos, 1, 2, 3);

cout << endl << endl;

return 0;

} // Cierra funcion main

Como nota final se daran cuenta de que para pasar N discos de una torre a otra se requieren (2^N) - 1 movimientos. Asi que si los monjes de marras inician con una torre de 64 discos necesitaran hacer (2 ^ 64) - 1 ( = 18446744073709551616) movimientos para terminar. Suponiendo que hacen un movimiento por segundo entonces necesitarian 584942417355 años para terminar el trabajo. Pero como esto supera, y con mucho, la edad del universo, entonces no hay por que preocuparse de los avances de los monjes ni del fin del mundo.