Prim rekursiv?

Hallo,

eine rekursive Methode schreiben, um zu gucken ob eine Zahl Prim ist oder nicht, bisher habe ich eine iterative Lösung. Idee?

static int prim(int n){
for(int i=2; i<n-1; i++){
	int r=n%i;
	if(r==0) return 0;
	}
	return 1;
}

Hi

wo ist das problem die schleife in eine recursion umzubauen?

statt einen neuen durchlauf zu starten rufst sich die funktion selber mit veränderten parametern auf.(i++)

und sobald die abbruchkriterium erreicht ist bricht die rekursion ab, kein neuer aufruf.

bool is(int zahl)
{
   return test(zahl,1);
}

bool test(int zahl, int n)
{
   bool ret = false;

   int p = getP(n); // die n'te p-zahl 1,2,3,5,...

   if ( subTest( zahl, p ) ) 
   {
      ret = true;
   }
   else
   {
      if ( p ^ 2 < zahl ) 
      {
         test(zahl,n++); // recursionsschritt
      }
   }
   return ret;
}

int getP(int n)
{
   ...
}

bool subTest (int zahl, int p)
{
   bool ret = false;

   ...

   return ret;
}

nur wieso man sowas recursiv lösen sollte? Hausaufgabe?

gruss

Hallo,
nein keine Hausaufgabe, nur interessehalber, aber ich habe auch eine Lösung gefunden:

static int rec(int n, int i){
	if(i==1) return 1;
	if(n%i==0) return 0;
	return rec(n, i-1);		
}

Hi

int prim(int n,int i)
{
  int ret = 1;
  for(int x=i; x > 1 ; i--)
  { 
    int r=n%i; 
    if(n%x==0)
    {
      ret = 0;
      break; 
    } 
  }
  return ret; 
}

so würd deine lösung ohne rekursion aussehen sieht ja so ähnlich aus wie bei dir nur das er von oben anfängt zu teilen. Nach möglichkeit sollte man rekursionen vermeiden. da sie meist lansamer sind und ggf gar nicht zum ziehl führen, da sie einen stackoverflow produziehren.

versuch mal testweise die n'te fibunachi zahl zu berechnen.

fib(0) = 0; // abbruchkriterium 1
fib(1) = 1; // abbruchkriterium 2
fib(n) = fib(n-1) + fib(n-2); // Rekursionsvorschrift

int steps  = 0;

unsigned int fib( unsigned int x )
{
  steps ++;
  if ( x < 2 )
  {
    return x;
  }
  return fib(x-2) + fib(x-1);
}

versuch das einam recursiv zu implementieren ( zähl dabei die recursionsschritte mit )
und versuch es mal mit einer nicht recursiven lösung. ( die geht einen anderen ansatz. sie berechnet die zahlen von unten her beginnen und merkt sich immer die letzten beiden um die dritte zu berechnen.)

fib1 = 0;
fib2 = 1;
fib3 = 1;
for (int i = 1 ; i < n; i++)
{
  fib3 = fib1 + fib2;
  fib1 = fib2;
  fib2 = fib3;
}

return fib3;

für richtigkeit übernehm ich keine verantwortung. vergleich aber mal die laufzeiten und den speicherverbrauch. könnte recht lustig werden.

kurtz noch mal die ersten par fibu zahlen
0, 1, 1, 2, 3, 5, 8, 13, 21, ...

gruss