Rekursion Allgemeine Fragen

derfreak

Mitglied
Hallo alle Zusammen,

ich bin derzeitig dran das Thema Rekursion zu verstehen, leider habe ich einige Schwierigkeiten.

Was ich bis jetzt weiß, ist das Rekursionen ohne Schleifen auskommen können.
Stattdessen benutzten sie Ihre eigene Methode oder eine Hilfsmethode immer und immer wieder.

(Aufgabenstellung : Given a non-negative int n, return the count of the occurrences of 7 as a digit, so for example 717 yields 2. (no loops))
Wenn ich jetzt das Beispiel von CodingBat nehme : count7.
Verstehe ich was von mir verlangt wird. Leider ist die Umsetzung etwas schwer.

Die Lösung habe ich mir auch schon angeguckt, leider habe ich sie nicht ganz verstanden.
Java:
public int count7(int n) {
  if (n < 1) return 0;
  if (n % 10 == 7) return 1 + count7(n/10);
  else return count7(n/10);
}

Bei der zweiten if-Abfrage wird mit count7(n/10) addiert, ich kann mir leider nicht ganz vorstellen was da gemacht wird.
Kann mir jemand erklären, was in der Aufgabe Stück für Stück passiert und was es mit dem addieren von count7(n/10) auf sich hat?

----------------------------------------------------------------------------------
Ich habe mir das so vorgestellt:
Beispiel n = 717

- Kontrolliert ob n < 1 ist wenn ja, return 0;
- Kontrolliere ob der Rest-Wert von n gleich 7 ist [Also der letzte Wert 717] wenn ja, return 1 + count7(717 / 10);
SO ab hier wird dann count7(717 /10) ausgeführt es entsteht count7(71 / 10) daraus entsteht count7(7), Bedingung wird wieder erfüllt, warum wird nun count7(7) == 1 gesetzt?
- und wenn jetzt beispielsweise nicht 717 zutrifft sondern beispielsweise 71 dann wird
count7(71/10) --> count7(7) --> Bedingung erfüllt bei der zweiten if-Anweisung, return 1 + was?


Wie ihr sieht, verstehe ich nicht ganz was zwischen den Zeilen passiert.
Ich wäre sehr dankbar wenn mir das jemand gut erklären kann.

VIELEN DANK! 🙂
 
Zuletzt bearbeitet:
Denk einfach noch einen Schritt weiter. Du hast es ja fast... Was passiert, wenn
Code:
count7(7)
aufgerufen wird? 7 modulo 10 ist 7, also ist die Bedingung in der zweiten if-Abfrage erfüllt und es wird
Code:
1+count7(7 / 10)
zurückgegeben. 7/10 ist aber 0, sofern wir mit Integer rechnen, also wird count7 mit n=0 aufgerufen... Nun ist count7(0) = 0, also ist count7(7) = 1 + count7(0) = 1 + 0 = 1, also ist count7(71) = ... usw
 
Denk einfach noch einen Schritt weiter. Du hast es ja fast... Was passiert, wenn
Code:
count7(7)
aufgerufen wird? 7 modulo 10 ist 7, also ist die Bedingung in der zweiten if-Abfrage erfüllt und es wird
Code:
1+count7(7 / 10)
zurückgegeben. 7/10 ist aber 0, sofern wir mit Integer rechnen, also wird count7 mit n=0 aufgerufen... Nun ist count7(0) = 0, also ist count7(7) = 1 + count7(0) = 1 + 0 = 1, also ist count7(71) = ... usw

Aso Vielen Dank 🙂

Eine Frage hätte ich da noch:
# Das heißt count7() <-- dieser Aufruf wird immer solange ausgerufen bis "umgangssprachlich" zu einer ganzen Zahl wird?

# Wenn wir jetzt davon ausgehen das n = 77 ist, würde er wieder in die zweite If-Anweisung gehen,
dann 1 + count7(77/10) zurückgeben. // Da wir noch keine ganze Zahl für count7 haben, ruft die Methode sich selber wieder auf. Zweite If-Anweisung wird wieder erfüllt, rechnen wir JETZT 1+1+count7(7/10), nun geht es nicht mehr weiter und count7 wird auf 0 gesetzt da 7 / 10 = 0 ist bei Int. Das heißt 1+1 wird ausgerechnet und man hat 2.

Ist das so richtig? Also wird die grüne eins die man zuvor hatte erneut mit genommen und dann dazu gerechnet?

PS: Ich glaube wenn ich eine Variable genommen hätte, wäre es mit vllt schneller so eingefallen.
Ich bin davon ausgegangen, dass die grüne eins einfach verschwindet, weil sie ja nicht zugewiesen wurde... :/
 

Neue Themen


Zurück
Oben