# Login Programm / Passwort Rekursiv testen



## gta008 (25. Dez 2021)

Guten Abend,
ich studiere im ersten Semester Informatik und wir haben nun mit dem Thema Rekursion begonnen. Ich habe mich sehr viele Stunden damit und mit der Aufgabe beschäftigt, aber bekomme es leider nicht hin sie zu lösen. Wir sollen in Java ein Programm schreiben, welches (1) Iterativ ein Passwort der Länge 6 herausfinden kann, wobei das Passwort nur aus kleinen Buchstaben besteht. Diesen Teil habe ich hinbekommen und bereits die Rückmeldung bekommen, dass er korrekt ist. Jetzt sollen wir das ganze (2) rekursiv umschreiben, sodass es für Passwörter beliebiger Länge funktioniert. Dazu haben wir folgenden Aufgabentext bekommen:
_Dieses Problem lässt sich mit Rekursion lösen. Wir nutzen also verschachtelte Methoden-
aufrufe anstatt verschachtelter Schleifen. Das in der Beispiellösung verwendete Array c
sollen Sie als Parameter an die rekursiven Methodenaufrufe weiterreichen. Die Methode
calculatePassword soll einen weiteren Parameter int length haben, welcher angibt, wel-
che Stelle des Passworts von diesem Methodenaufruf varriiert wird. Bspw. verändert ein Me-
thodenaufruf von calculatePassword das Arrayelement c[length-1] und ruft für jedes
an dieser Stelle eingesetzte Zeichen erneut calculatePassword mit einer um 1 geringeren
length auf. Dies wird solange fortgeführt bis length=0. In diesem Fall soll das Passwort mit-
tels isValidPassword-Methode überprüft werden. Wurde das Passwort gefunden, so soll die
Methode das Passwort zurückgeben. Ansonsten soll eine leere Zeichenkette ("") zurückgege-
ben werden. Sie können die Rekursion also abbrechen, wenn ein rekursiver Methodenaufruf
eine nicht-leere Zeichenkette zurückgibt.
Sie dürfen weitere Hilfsmethoden schreiben._
Ich habe sehr viele Stunden, über die letzte Woche probiert und komme einfach nicht auf eine Lösung. Kann mir hier jemand helfen? Anbei das Iterative Programm, von welchem wir ausgehen sollen. Ich denke der fehlende Code ist sehr einfach und kurz für jemanden, der das Rekursive Denken schon kann.
[CODE lang="java" title="Programm Iterativ"]class Login {

  static boolean isValidPassword(String password) {
    return "abcdef".equals(password);
  }

  static String calculatePassword() {
    char[] c = new char[6];
    for (char c0 = 'a'; c0 < 'z'; ++c0) {
      c[0] = c0;
      for (char c1 = 'a'; c1 < 'z'; ++c1) {
        c[1] = c1;
        for (char c2 = 'a'; c2 < 'z'; ++c2) {
          c[2] = c2;
          for (char c3 = 'a'; c3 < 'z'; ++c3) {
            c[3] = c3;
            for (char c4 = 'a'; c4 < 'z'; ++c4) {
              c[4] = c4;
              for (char c5 = 'a'; c5 < 'z'; ++c5) {
                c[5] = c5;
                String password = new String(c);
                if (isValidPassword(password)) {
                  return password;
                }
              }
            }
          }
        }
      }
    }
    return null;
  }

  public static void main(String[] args) {
    Out.println("Berechnetes Passwort: " + calculatePassword());
    int tries = 0;
    do {
      Out.print("Geben Sie das Passwort ein: ");
      String password = In.readLine();
      if (isValidPassword(password)) {
        Out.println("Login erfolgreich");
        return;
      } else {
        Out.println("Passwort falsch");
        ++tries;
      }
    } while (tries < 3);
    Out.println("Passwort zu oft falsch eingegeben");
  }

}
[/CODE]


----------



## mihe7 (25. Dez 2021)

gta008 hat gesagt.:


> Ich denke der fehlende Code ist sehr einfach und kurz für jemanden, der das Rekursive Denken schon kann.


Nur bringt Dir das nichts, wenn Dir hier jemand die Lösung hinschreibt  Wir können das zusammen erarbeiten.

Hinter der Rekursion steckt genau die gleiche Überlegung, die Du in der iterativen Variante bereits angewendet hast.

Du hast eine Schleife geschrieben, um das erste Zeichen zu variieren. Dabei hast Du Dir überlegt: ok, es gibt noch ein zweites Zeichen, das variiert werden kann, also pflanze ich eine weitere for-Schleife ein. Das gleiche hast Du für das dritte, vierte, fünfte und sechste Zeichen gemacht. Dann wusstest Du: ok, es gibt kein weiteres Zeichen, das variiert werden könnte, also erledige ich jetzt die Prüfung des Passworts.

Natürlich hättest Du das auch in umgekehrter Reihenfolge machen können: vom sechsten Zeichen bis zum ersten und dort die Prüfung des Passworts einbauen können. 

Nichts anderes machst Du beim rekursiven Ansatz. Der Hauptunterschied besteht darin, dass Du die Methode erneut aufrufst, statt eine weitere for-Schleife einzubauen und der length-Parameter angibt, welches Zeichen die Methode variieren soll.

Probiers mal und poste Deinen Ansatz.


----------



## gta008 (26. Dez 2021)

mihe7 hat gesagt.:


> Nur bringt Dir das nichts, wenn Dir hier jemand die Lösung hinschreibt  Wir können das zusammen erarbeiten.
> 
> Hinter der Rekursion steckt genau die gleiche Überlegung, die Du in der iterativen Variante bereits angewendet hast.
> 
> ...


Hallo,

Vielen Dank für die schnelle Rückmeldung. Ich habe dies sowie die Aufgabenstellung versucht umzusetzen, leider funktioniert es nicht. Anbei der neue Code:
[CODE lang="java" title="Programm Rekursiv Versuch 1"]class Logincopy {

  static boolean isValidPassword(String password) {
    return "abcdef".equals(password);
  }

  static String calculatePassword(int length) {
    char[] c = new char[length];
    char letter = 'a';
    if (length == 0) {
      String password = new String(c);
      if (isValidPassword(password)) {
        return password;
      } else {
        return ""; //++lenght?
      }
    } else {
        c[length - 1] = letter;
        if ("".equals(calculatePassword(length - 1))) {
          ++letter;
          calculatePassword(length - 1);
        } else {
        }
    }
    return null;
  }

  public static void main(String[] args) {
    Out.println("Berechnetes Passwort: " + calculatePassword(1));
    int tries = 0;
    do {
      Out.print("Geben Sie das Passwort ein: ");
      String password = In.readLine();
      if (isValidPassword(password)) {
        Out.println("Login erfolgreich");
        return;
      } else {
        Out.println("Passwort falsch");
        ++tries;
      }
    } while (tries < 3);
    Out.println("Passwort zu oft falsch eingegeben");
  }

}
[/CODE]


----------



## mihe7 (26. Dez 2021)

Das ist schon mal nicht schlecht. Die rekursive Methode braucht als Parameter zusätzlich das Array. Das kommt also von außen:

```
static String calculatePassword(char[] c, int length) {
```
Ich würde das Array allerdings mit letters statt c bezeichnen.

Die Zeilen 8 und 9 brauchst Du damit nicht. Die Zeilen 10 bis 17 sind ok. Auf das else kannst Du verzichten, weil im then-Zweig returned wird.

In Zeile 18 fehlt die for-Schleife, so wie Du sie ursprünglich für ein Zeichen hattest:

```
for (char ch = 'a'; ch <= 'z'; ++ch) {
    c[length-1] = ch;
    // statt der verschachtelten for-Schleife, einfach
    Sting password = calculatePasssword(c, length-1);
    // und noch prüfen, was Sache ist
    if (!password.isEmpty()) {
        return password;
    }
}
```


----------



## gta008 (26. Dez 2021)

Ich habe das Programm nun angepasst, aber es funktioniert noch nicht. Anbei der angepasste Code:
[CODE lang="java" title="Rekursiv"]class Logincopy {

  static boolean isValidPassword(String password) {
    return "abcdef".equals(password);
  }

  static String calculatePassword(char[] letter, int length) {
    if (length == 0) {
      String password = new String(letter);
      if (isValidPassword(password)) {
        return password;
      } else {
        return "";
      }
    }
    for (char ch = 'a'; ch <= 'z'; ++ch)
      letter[length - 1] = ch;
      String password = calculatePassword(letter, length - 1);
      if (!password.isEmpty()) {
        return password;
      }
  }

  public static void main(String[] args) {
    Out.println("Berechnetes Passwort: " + calculatePassword('a', 1));
    int tries = 0;
    do {
      Out.print("Geben Sie das Passwort ein: ");
      String password = In.readLine();
      if (isValidPassword(password)) {
        Out.println("Login erfolgreich");
        return;
      } else {
        Out.println("Passwort falsch");
        ++tries;
      }
    } while (tries < 3);
    Out.println("Passwort zu oft falsch eingegeben");
  }

}[/CODE]
Wo habe ich noch einen Fehler und damit ich das verstehe, was genau macht die Zeile 19, also was prüft das !password.isEmpty()?
Vielen Dank im Voraus.


----------



## gta008 (26. Dez 2021)

Bezüglich !password.isEmpty(), wäre es dasselbe, wenn ich if (password.length() != 0) schreibe?


----------



## mihe7 (26. Dez 2021)

gta008 hat gesagt.:


> Bezüglich !password.isEmpty(), wäre es dasselbe, wenn ich if (password.length() != 0) schreibe?


Ja und es fehlen die geschweiften Klammern nach dem for (vgl. mit Code aus Kommentar #4)


----------



## gta008 (26. Dez 2021)

Das habe ich angepasst. Jetzt bekomme ich immer noch folgende Fehlermeldungen.:
This method must return a result of type String [7,17]
The method calculatePassword(char[], int) in the type Logincopy is not applicable for the arguments (char, int) [26,44]
Rufe ich Methode denn richtig in der Main Methode? Mir wird nicht ersichtlich, dass es für ein Passwort beliebiger Länge funktioniert, da ich ja immer nur in der Main Methode die weitergebe. Wo muss ich noch eine weitere Änderung vornehmen, damit das Programm wie gewünscht funktioniert?
[CODE lang="java" title="Aktueller Stand"]class Logincopy {

  static boolean isValidPassword(String password) {
    return "abcdef".equals(password);
  }

  static String calculatePassword(char[] letter, int length) {
    if (length == 0) {
      String password = new String(letter);
      if (isValidPassword(password)) {
        return password;
      } else {
        return "";
      }
    }
    for (char ch = 'a'; ch <= 'z'; ++ch) {
      letter[length - 1] = ch;
      String password = calculatePassword(letter, length - 1);
      if (password.length() != 0) {
        return password;
      }
    }
  }

  public static void main(String[] args) {
    Out.println("Berechnetes Passwort: " + calculatePassword('a', 1));
    int tries = 0;
    do {
      Out.print("Geben Sie das Passwort ein: ");
      String password = In.readLine();
      if (isValidPassword(password)) {
        Out.println("Login erfolgreich");
        return;
      } else {
        Out.println("Passwort falsch");
        ++tries;
      }
    } while (tries < 3);
    Out.println("Passwort zu oft falsch eingegeben");
  }

}[/CODE]


----------



## mihe7 (26. Dez 2021)

gta008 hat gesagt.:


> Jetzt bekomme ich immer noch folgende Fehlermeldungen.:


Ja. Wenn das Ende der Methode erreicht wird, dann wurde offensichtlich kein passendes Passwort gefunden. Dementsprechend müsstest Du am Ende noch ein `return "";` einfügen.



gta008 hat gesagt.:


> Rufe ich Methode denn richtig in der Main Methode?


Nun, die rekursive Methode verlangt ein char-Array und die Länge des Passworts. Also ist der Aufruf nicht korrekt.

Allerdings stellt sich mir gerade ein ganz andere Frage: die Methode probiert ja sämtliche Kombinationen durch. In der main-Methode fragst Du den Benutzer nach einem Passwort. Soll dieses das herauszufindende Passwort sein? 

Dann würde ich Dir eine statische Variable für dieses Passwort vorschlagen, die in isValidPassword (statt "abcdef") verwendet wird.

Für den Aufruf der rekursiven Methode müsstest Du also noch lokal ein entsprechend langes char-Array anlegen und an die Methode zusammen mit der Länge des Passworts übergeben.


----------



## gta008 (26. Dez 2021)

Genau, in der main Methode soll das korrekte Passwort ausgegeben werden und danach soll der Benutzer dieses eingeben. Das korrekte Password steht in der Methode isValidPassword. Das ganze soll nicht für eine bestimmte Länge des Passworts funktionieren, sondern für alle Längen. Für eine bestimmte Länge hat das Programm so funktioniert. Ich dachte mir das so, dass es erst für die Länge 1, dann 2 usw. probiert wird, bis die Methode isValidPassword dementsprechend true liefert. Das ganze habe ich nun mit der neuen Methode calculatePassword() probiert umzusetzen. Es kommt keine Fehlermeldung, aber das Programm funktioniert nicht bzw. läuft unendlich lange.
[CODE lang="java" title="Neue Methode"]class Logincopy {

  static boolean isValidPassword(String password) {
    return "abcde".equals(password);
  }

  static String calculatePassword(char[] letter, int length) {
    if (length == 0) {
      String password = new String(letter);
      if (isValidPassword(password)) {
        return password;
      } else {
        return "";
      }
    }
    for (char ch = 'a'; ch <= 'z'; ++ch) {
      letter[length - 1] = ch;
      String password = calculatePassword(letter, length - 1);
      if (password.length() != 0) {
        return password;
      }
    }
    return "";
  }

  static String calculatePassword() {
    int n = 1;
    boolean passwordStatus = false;
    String password;
    do {
      char[] letter = new char[n];
      password = calculatePassword(letter, n);
      if (password.length() != 0) {
        passwordStatus = true;
      }
    } while (passwordStatus == false);
    return password;
  }

  public static void main(String[] args) {
    //char[] c = new char[5];
    Out.println("Berechnetes Passwort: " + calculatePassword());
    int tries = 0;
    do {
      Out.print("Geben Sie das Passwort ein: ");
      String password = In.readLine();
      if (isValidPassword(password)) {
        Out.println("Login erfolgreich");
        return;
      } else {
        Out.println("Passwort falsch");
        ++tries;
      }
    } while (tries < 3);
    Out.println("Passwort zu oft falsch eingegeben");
  }

}[/CODE]


----------



## gta008 (26. Dez 2021)

Einen Fehler habe ich gefunden. Ich habe jetzt nach Zeile 53 noch n++ ergänzt. Nun funktioniert das Programm zum Beispiel für das Passwort: "abcdef" , aber nicht für das Passwort "password". Das verstehe ich nicht.


----------



## gta008 (26. Dez 2021)

Es funktioniert auch für das Passwort "password". Das Problem ist hier die Laufzeit. Für ein 7 stelliges Passwort benötigt das Programm ca. 50sekunden, für 8 Stellen 6,3min. Ich habe einen Timer sowie eine Ausgabe der aktuellen Stelle eingebaut. Gibt es eine Möglichkeit, das Programm (deutlich) zu beschleunigen für Passwörter Länger als 7?
[CODE lang="java" title="Programm langsam"]class Logincopy {

  static boolean isValidPassword(String password) {
    return "password".equals(password);
  }

  static String calculatePassword(char[] letter, int length) {
    if (length == 0) {
      String password = new String(letter);
      if (isValidPassword(password)) {
        return password;
      } else {
        return "";
      }
    }
    for (char ch = 'a'; ch <= 'z'; ++ch) {
      letter[length - 1] = ch;
      String password = calculatePassword(letter, length - 1);
      if (password.length() != 0) {
        return password;
      }
    }
    return "";
  }

  static String calculatePassword() {
    int n = 1;
    boolean passwordStatus = false;
    String password;
    do {
      Out.println(n);
      char[] letter = new char[n];
      password = calculatePassword(letter, n);
      if (password.length() != 0) {
        passwordStatus = true;
      }
      n++;
    } while (passwordStatus == false);
    return password;
  }

  public static void main(String[] args) {
    //char[] c = new char[5];
    double start = System.currentTimeMillis();
    Out.println("Berechnetes Passwort: " + calculatePassword());
    double end = System.currentTimeMillis();
    Out.println("Dauer: " + (end - start) + " ms");
    int tries = 0;
    do {
      Out.print("Geben Sie das Passwort ein: ");
      String password = In.readLine();
      if (isValidPassword(password)) {
        Out.println("Login erfolgreich");
        return;
      } else {
        Out.println("Passwort falsch");
        ++tries;
      }
    } while (tries < 3);
    Out.println("Passwort zu oft falsch eingegeben");
  }

}[/CODE]


----------



## mihe7 (26. Dez 2021)

gta008 hat gesagt.:


> Gibt es eine Möglichkeit, das Programm (deutlich) zu beschleunigen für Passwörter Länger als 7?


Wenn Du alle Kombinationen durchprobieren musst, erhöht sich mit jeder Stelle die Zahl der Kombinationen um den Faktor 26. Die Laufzeit des Algorithmus ist O(26^n) und damit exponentiell.

Tatsächlich könnte man aber was drehen, indem man deutlich langsamere Hardware simuliert. Wenn isValidatePassword einen zeichenweisen Vergleich durchführt und je Zeichen eine messbare Zeit benötigt, dann könnte man anhand des zeitlichen Unterschieds eine Stelle nach der anderen ermitteln. Das ist aber ein ganz anderer Ansatz als der geforderte


----------



## gta008 (26. Dez 2021)

Genau, die Laufzeit hatte ich eben auch so berechnet und mit einer Variablen ausgetestet. Vielen Dank für die Hilfe und vor allem die schnellen Antworten, ich lasse das Programm jetzt bei der Laufzeit


----------

