Petando la pila. Problemas y retos usando recursividad.

[eferion]

Como no quiero que me pase como con el de los números vampiros, aquí está mi primera propuesta para el ejercicio de ordenar:

Código C:

#define NUEVO_NODO(nodo,valor,padre)\
  nodo = &padre->memoria->datos[ padre->memoria->nextIndex++ ]; \
  nodo->ant = 0; nodo->sig = 0; \
  nodo->repeticiones = 1; nodo->valor = valor; \
  nodo->memoria = padre->memoria
 
struct Memoria;
 
struct Nodo
{
  int valor;
  int repeticiones;
 
  struct Nodo* ant;
  struct Nodo* sig;
 
  struct Memoria* memoria;
};
 
struct Memoria
{
  struct Nodo* datos;
  int nextIndex;
};
 
void BuscarValor( struct Nodo* nodo, int valor )
{
  if ( nodo->valor < valor )
  {
    if ( nodo->sig == 0 )
    {
      NUEVO_NODO( nodo->sig, valor, nodo );
    }
    else
    {
      BuscarValor( nodo->sig, valor );
    }
  }
  else if ( nodo->valor > valor )
  {
    if ( nodo->ant == 0 )
    {
      NUEVO_NODO( nodo->ant, valor, nodo );
    }
    else
    {
      BuscarValor( nodo->ant, valor );
    }
  }
  else
    ++nodo->repeticiones;
}
 
void CrearArbol( struct Nodo* nodo, int* array, int longitud )
{
  BuscarValor( nodo, *array );
 
  if ( --longitud )
    CrearArbol( nodo, ++array, longitud );
}
 
void RegenerarArray( int* array, struct Nodo* nodo, int *pos )
{
  if ( nodo->ant )
  {
    RegenerarArray( array, nodo->ant, pos );
    nodo->ant = 0;
  }
 
  if ( nodo->repeticiones )
  {
    array[ (*pos)++ ] = nodo->valor;
    if ( --nodo->repeticiones )
      RegenerarArray( array, nodo, pos );
  }
 
  if ( nodo->sig )
  {
    RegenerarArray( array, nodo->sig, pos );
    nodo->sig = 0;
  }
}
 
void ordena(int array[], int n )
{
  Memoria memoria;
  memoria.datos = (struct Nodo*)malloc( n * sizeof( struct Nodo ) );
  memoria.nextIndex = 1;
 
  struct Nodo* root = memoria.datos;
  root->valor = array[ 0 ];
  root->repeticiones = 1;
  root->sig = 0;
  root->ant = 0;
  root->memoria = &memoria;
 
  CrearArbol( root, &array[ 1 ], n-1 );
 
  int pos = 0;
  RegenerarArray( array, root, &pos );
 
  free( memoria.datos );
}
 

-------

EDITO: Bueno, ya puestos pongo también una primera aproximación al segundo ejercicio:

Código C:

#define IMPRIMIR( base, exponente, primerPrimo ) \
  if ( primerPrimo == 0 ) printf( " *" ); \
  if ( exponente == 1 ) printf( " %d", base ); \
  else if ( exponente > 0 ) printf( " %d^%d", base, exponente )
 
int ComprobarPrimo( int* numero, int candidato )
{
  if ( *numero % candidato == 0 )
  {
    *numero /= candidato;
    return 1 + ComprobarPrimo( numero, candidato );
  }
  return 0;
}
 
void bucleChequeo( int numero, int candidato, int primerPrimo, int ver )
{
  int exp = ComprobarPrimo( &numero, candidato );
  if ( exp > 0 && ver)
  {
    IMPRIMIR( candidato, exp, primerPrimo );
    primerPrimo = 0;
  }
 
  candidato += 2;
  if ( numero > 1 )
    bucleChequeo( numero, candidato, primerPrimo, ver );
}
 
void descompon(int a, int b, int ver)
{
  int actual = a;
  int exp = ComprobarPrimo( &actual, 2 );
  if ( ver )
  {
    printf( "%d =", a );
    IMPRIMIR( 2, exp, 1 );
  }
 
  bucleChequeo( actual, 3, exp == 0, ver );
 
  if ( ver )
    printf ( "\n" );
 
  if ( a < b )
    descompon( ++a, b, ver );
}
 

Un saludo.