rekursionsanzahl ermitteln

[batou]

Hallo zusammen,

kann mir jemand einen Tipp geben wie ich bei der Rekursion des größten gemeinsamen Teilers zweier zahlen die rekursionsanzahl ermitteln kann und diese dann auch ausgeben kann über return?

 

[manuche]

verstehe ich dich grad richtig, das du den größten gemeinsamen Teiler einer Zahl durch ein Rekursionsverfahren ermitteln willst und dabei gleichzeitig die Rekursionstiefe ausgegeben werden soll?
Wie ist denn die Rekursion des größten gemeinsamen Teilers oder willst du genau das wissen?

 

[SlaterB]

unabhängig von der Rekursion solltest du dir über den Rückgabewert Gedanken machen,
das kann ja nur ein Wert sein, wenn es der ggt ist, dann nicht die Tiefe,

willst du doch beides zurückgeben, dann entweder ein int[], ein Objekt einer eigenen Klasse oder ein int, der codiert ist:
int x = tiefe*1000+ggt

jedenfalls gibst du zu Beginn der Rekursion den Parameter tiefe = 0 mit und erhöhst ihn bei jeden rekursiven Aufruf um 1

 

[Joker]

wie wäre es mit so was? Das Ergebnis wird zwar nicht returniert aber ans Ergebnis kommt du ja trotzdem. Anstatt der Fakultät nimmst du halt deine ggt Funktion.

public class Rekursion {
	private static int counter = 0;
	
	private static long fakultaet(int n){
		counter++;
	      if (n==0||n==1) 
	    	  return 1;
	      else 
	    	  return n*fakultaet(n-1);
	   }
	
	public static void main(String[] args) {
		System.out.println("Fakultät: "+fakultaet(5)+"  Tiefe: "+counter);
                            counter=0;
	}
}

 

[batou]

joa danke, erstmal ok nein die rekursion für den ggT habe ich bereits.

  public int ggT(int a, int b){

    if (b==0) 
      return a;
    else 
      return ggT(b, a % b);
}

das problem ist wie gesagt die zählung der einzelnen rekursionsschritte, der ggT muss nicht ausgegeben werden nur die Anzahl der einzelnen Rekursionsschritte, der funktionskopf muss so wie er definiert ist bleiben, habe schon überlegt vielleicht eine zweite funktion aufzurufen die dann zählt ... aber irgendwie bin ich lichtjahre von einer lösung entfernt

 

[SlaterB]

das heißt, dass du gar nicht am Ende a zurückgeben musst?
dann ist es doch leicht:

if (b==0)
return 1;
else
return 1+ggT(b, a % b);

 

[Leroy42]

das heißt, dass du gar nicht am Ende a zurückgeben musst?
dann ist es doch leicht:

Genau!

public int ggTCounter(int a, int b) {return 1 + (b==0 ? 0 : ggTCounter(b, a%b));}