Ayuda - Recursividad

[davitcito]

Buenas, me gustaría ver si me podrian ayudar o dar algun consejo de como podría escribir un algoritmo recursivo para cambiar a un numero decimal a una número binario (se q se pasa dividiendo sucesivamente entre 2, pero no tengo muy en claro como hacerlo recursivamente).

Gracias.

[roman]

¿Qué tal algo así?

Código Delphi [-]
function DecToBin(D: Integer): String;
begin
  if D > 0
    then Result := DecToBin(D div 2) + IntToStr(D mod 2)
    else Result := '';
end;

// Saludos

[davitcito]

hola, gracias por el dato, pero lo q no me queda muy en claro es cual vendria a ser el caso base??

[roman]

Empezado por davitcito

viene a ser el caso base?

Así es.

// Saludos

[davitcito]

Gracias Roman, hice la corrida de escritorio y todo bien, sale perfecto. Saludos. . Otra, cosilla, será posible con una funcion similar pasar de decimal a hexadecimal?? Voy a intentar

[roman]

Si te contesto para hexadecimal me vas a preguntar para octal así que mejor te propongo esta:

Código Delphi [-]
function DecToBaseN(D, N: Integer): String;
const
  Digits = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ';

begin
  if D > 0
    then Result := DecToBaseN(D div N, N) + Digits[(D mod N) + 1]
    else Result := '';
end;

que convierte de decimal a cualquier base (al menos hasta base 36)

// Saludos

[Mick]

Solo comentar que no tiene sentido implementar ese tipo
de algoritmo en forma recursiva, esos algoritmos
se implementan siempre de forma iteractiva ya que consume
menos recursos/memoria y se ejecutan mas rapido.

Saludos

[jachguate]

Empezado por Mick

Solo comentar que no tiene sentido implementar ese tipo
de algoritmo en forma recursiva

Cierto, a menos que estes aprendiendo como funciona la recursividad... en ese caso son un muy buen ejemplo...

Además, con la potencia de las máquinas de hoy y suponiendo que se ganaría apenas un par de milisegundos, para mi es preferible la legibilidad y simplicidad de la solución recursiva.

Hasta luego.

[davitcito]

si pues es verdad, el mismo profesor nos dice q consume mas recursos pero lo hacemos porke recien estamos empezando a ver recursividad.

[roman]

Empezado por Mick

Solo comentar que no tiene sentido implementar ese tipo
de algoritmo en forma recursiva

¡Qué exigentes!

Código Delphi [-]
function DecToBin2(D: Integer): String;
begin
  Result := '';

  while D > 0 do
  begin
    Result := IntToStr(D mod 2) + Result;
    D := D div 2;
  end;
end;

// Saludos

[Mick]

Era facil suponer que era para un ejercicio, pero mi opinion es que es preferible poner ejercicios que si es necesario que se realicen con recursividad, para que los alumnos vayan teniendo claro y puedan distinguir cuando se debe y no se debe utilizar.

En cuanto al tema de que las maquinas de hoy son potentes es cierto, pero eso no significa que haya que tirar ciclos del reloj a la papelera haciendo cosas redundantes, por muy potentes que sean los equipos de hoy la verdad es que en muchos casos se arrastran, considero una desgracia que hoy en dia, en general, no se tenga en cuenta un poco el rendimiento del software.
Sobre todo porque en muchos casos con unas minimas modificaciones se pueden conseguir mejorar sustanciales.

Pongamos un caso practico, por ejemplo, seleccionemos ultima implementacion del algoritmo en cuestion:

function Dec2Bin(D: Integer): String;
begin
  Result := '';
  while D > 0 do
  begin
    Result := IntToStr(D mod 2) + Result;
    D := D div 2;
  end;
end;

Comparemosla con esta otra implementacion:

function Dec2BinEx(D: Cardinal): String;
var
 P:PChar;
begin
  Result:= '00000000000000000000000000000000';
  P:= @Result[32];
  while D > 0 do begin
    P^:= PChar('01')[D AND 1];
    D := D SHR 1;
    Dec(P);
  end;
end;

Si hacemos un test de velocidad, en un: PIV 2.4 Ghz.

La Primera implementacion:
2 millones de ejecuciones tardan aproximadamente 1 minuto.

La segunda implementacion:
2 millones de ejecuciones tardan aproximadamente 1 segundo.

Como podemos ver la diferencia es abismal de un minuto a un segundo, 60 veces mas rapido !!!.

Es decir la diferencia de velocidad es tal, que mi 486 a 50Mhz de hace 15 años usando el segundo algoritmo, es casi mas rapido que mi Pentium IV a 2.4 Gigahercios usando el algoritmo lento.

Se podria objetar que en software normal no se dan las condiciones del ejemplo, pero solo hay que pensar que precisamente para lo que se utilizan las computadoras es para realizan operaciones repetitivas sobre gran cantidad de informacion.
Si algun servidor de base de datos, por ejemplo digamos firebird o interbase, tuviese cuellos de botella en su codigo como el del ejemplo, las consultas sobre las bases de datos podrian ir 60 veces mas lentas de lo que deberian, y no es lo mismo que una consulta compleja sobre miles o millones de registros tarde 1 minuto que una hora.
Los propios componentes Indy de delphi tienes cuellos de botella de ese tipo, de modo que modificando pequeñas partes del codigo se pueden conseguir mejoras de velocidad abismales, en determinadas operaciones y situaciones.

Igualmente en los programas de mas alto nivel, digamos programas de gestion, aunque no hagan calculos complejos directamente, lo cierto es que se suele implementar pequeños algoritmos o rutinas decenas o centenares de veces a lo largo del codigo, si sumamos un pequeño retraso en cada una de las rutinas, al final tendremos retrasos y consumos de memoria apreciables.

Saludos

PD: Como ejercicio dejo la siguiente pregunta, ¿ porque la segunda implementatcion es 60 veces mas rapida que la primera ?

[roman]

Je, je, muy bueno tu algoritmo. ¿Y has visto la diferencia también sustancial que se obtiene al regresar un ShortString en lugar de un String?

Empezado por Mick

mi opinion es que es preferible poner ejercicios que si es necesario que se realicen con recursividad

¿Por ejemplo?

// Saludos

[davitcito]

bueno, gracias por sus respuestas amigos