Sitzung: Jeden Freitag in der Vorlesungszeit ab 16 Uhr c. t. im MAR 0.005. In der vorlesungsfreien Zeit unregelmäßig (Jemensch da?). Macht mit!

Javakurs/Übungsaufgaben/Rekursion vs. Iteration: Unterschied zwischen den Versionen

(Funktionsweise Ermitteln & Verhübschen)
K
 
(16 dazwischenliegende Versionen von 10 Benutzern werden nicht angezeigt)
Zeile 1: Zeile 1:
Schwierigkeitsgrad: mittel bis schwer.
+
__TOC__
 +
Das Ziel dieser Aufgabe ist es, dass Ihr möglichst viele Eurer bisher erworbenen Java-Kenntnisse Schritt für Schritt anwendet. Abschließend sollt Ihr noch einen kleinen [[wikipedia:Benchmark|Benchmark]] einer rekursiv und iterativ implementierten Funktion durchführen.
  
Das Ziel dieser Aufgabe ist es, dass Ihr möglichst viele Eurer bisher erworbenen Java-Kenntnisse Schritt für Schritt anwendet. Abschließend sollt Ihr noch einen kleinen Benchmark einer rekrusiv und iterativ implementierten Funktion durchführen.
+
=== Aufgabenstellung ===
 +
Seht euch die Codebeispiele an und findet heraus, was der Code tut. Schreibt den Code anschließend neu, sodass der Code übersichtlicher und lesbarer ist.
  
== Funktionsweise Ermitteln & Verhübschen==
+
Gegeben ist folgende kleine Funktion:
  
Gegeben ist folgendes kleines Programm:
+
<pre>
 +
public static void main(String args[]) {
 +
int[] testValues = { 5, 10, 15, 20, 30, 40 };
 +
for (int i = 0; i < testValues.length; ++i) {
 +
System.out.println(doSomethingClever(testValues[i]));
 +
}
 +
}
  
''
+
public static int doSomethingClever(int a) {
public class MyProgramm{
+
int b;
 +
if (a <= 1) {
 +
if (a == 1) {
 +
b = calcSomethingNice(a);
 +
} else {
 +
b = getSomeSmartInt(a - 1);
 +
}
 +
} else {
 +
return theSmartestMethodsAlwaysNeedRidiculouslyLongNames(a);
 +
}
 +
return b;
 +
}
  
  public static int doSomethingClever(int a){
+
public static int getSomeSmartInt(int c) {
    int b;
+
return ++c;
    if(a <= 1){
+
}
      if(a == 1){
 
          b = calcSomethingNice(a);
 
      }else{
 
          b = getSomeSmartInt(a - 1);
 
      }
 
    }else{
 
      return theSmartestMethodsAlwaysNeedRidiculouslyLongNames(a);
 
    }
 
    return b;
 
  }
 
  
  public static int getSomeSmartInt(int c){
+
public static int calcSomethingNice(int d) {
    return ++c;
+
int i = 1;
  }
+
for (i = d * 11; i > d; i--) {
 +
i--;
 +
}
 +
return i;
 +
}
  
  public static int calcSomethingNice(int d){
+
public static int theSmartestMethodsAlwaysNeedRidiculouslyLongNames(int e) {
    int i = 1;
+
int container = doSomethingClever(e - 1);
    for(i = d * 11; i > d; i--){
+
return container + doSomethingClever(e - 2);
      i--;
+
}
    }
+
</pre>
    return i;
+
 
  }
+
Offensichtlich ist hier programmiertechnisch einiges schief gegangen. Denn obwohl der Code richtig funktioniert, ist er nur schwer leserlich. Folgende Fehler wurden gemacht:
  
  public static int theSmartestMethodsAlwaysNeedRidiculouslyLongNames(int e){
+
*nichtssagende Benennung der Variablen und Methoden,
    int container = doSomethingClever(e - 1);
+
*keine Kommentare,
    return container + doSomethingClever(e - 2);
+
*übertriebene Auslagerung in Extra-Methoden.
  }
 
}''
 
  
Offensichtlich ist hier programmiertechnisch Einiges schief gegangen. Denn obwohl der Code richtig funktioniert, ist er nur schwer leserlich. Folgende Fehler wurden gemacht:
+
Hinweis: Die obige Funktionalität ist [[wikipedia:Rekursion|rekursiv]] implementiert.
 
 
*nichtssagende Bennung der Variablen und Methoden
 
*keine Kommentare
 
*übertrieben Auslagerung in Extra-Methoden
 
  
 
All das sollt Ihr jetzt schrittweise ändern:
 
All das sollt Ihr jetzt schrittweise ändern:
  
#Versucht, ohne den PC mit einigen Handsimulationen herauszufinden, was das Programm eigentlich berechnet
+
#Versucht, ohne den PC mit einigen Handsimulationen herauszufinden, was <code>doSomethingClever</code> eigentlich berechnet.
#* Hinweis: Beginnt mit kleinen Zahlen wie 0,1,2 oder 3 und macht mehrere Durchgänge.
+
#* Hinweis: Beginnt mit kleinen Zahlen wie 0, 1, 2 oder 3 und macht mehrere Durchgänge.
 
#* Tipp: Es wird stets das n-te Glied einer bekannten Zahlenfolge berechnet.
 
#* Tipp: Es wird stets das n-te Glied einer bekannten Zahlenfolge berechnet.
#Integriert zuerst die beiden Hilfsfunktionen getSomeSmartInt und calcSomethingNice in die Hauptfunktion, da beide ziemlich überflüssig sind.
+
#Integriert zuerst die beiden Hilfsfunktionen <code>getSomeSmartInt</code> und <code>calcSomethingNice</code> in die Hauptfunktion, da beide ziemlich überflüssig sind.
#Löst die verschachtelte Rekursion von doSomethingClever und theSmartest... auf.
+
#Löst die verschachtelte Rekursion von <code>doSomethingClever</code> und <code>theSmartest...</code> auf.
 
#Lasst Euch "sprechende" Namen sowohl für die Variablen, Methode(n) und als auch die Klasse einfallen.
 
#Lasst Euch "sprechende" Namen sowohl für die Variablen, Methode(n) und als auch die Klasse einfallen.
 
#Fügt ausreichend viele und prägnante Kommentare hinzu, bis das Programm für Euch gut lesbar ist.
 
#Fügt ausreichend viele und prägnante Kommentare hinzu, bis das Programm für Euch gut lesbar ist.
#'''WICHTIG:''' Holt Euch nun einen '''Tutor''' ran, zeigt ihm Euer Programm und diskutiert die Lesbarkeit des Codes. Er kann euch sicherlich nützliche Tipps geben, was Ihr in Zukunft beim Programmieren unbedingt beachten solltet.
+
#'''Wichtig:''' Holt Euch nun einen '''Tutor''' ran, zeigt ihm Euer Programm und diskutiert die Lesbarkeit des Codes. Er kann euch sicherlich nützliche Tipps geben, was Ihr in Zukunft beim Programmieren unbedingt beachten solltet.
  
 
== Eine Iterative Alternative ==
 
== Eine Iterative Alternative ==
  
Schreibt nun ein Programm, dass die gleiche Zahlenreihe nicht-rekursiv berechnet. Verwendet dazu ein Array von Integern und folgende Idee:  
+
Schreibt nun ein Programm, das die gleiche Zahlenreihe nicht-rekursiv berechnet. Verwendet dazu ein Array von Integern und folgende Idee:  
 
* Initialisiert ein Array, das alle Folgenglieder (bei 0 anfangend) bis zum Gesuchten aufnehmen kann.
 
* Initialisiert ein Array, das alle Folgenglieder (bei 0 anfangend) bis zum Gesuchten aufnehmen kann.
 
* Berechnet die Folgenglieder in einer Schleife Eurer Wahl aufsteigend bei 0 beginnend und speichert sie in dem Array wie folgt: Folgenglied 0 steht an Position 0 im Array, Folgenglied 1 steht an Position 1 im Array, usw.
 
* Berechnet die Folgenglieder in einer Schleife Eurer Wahl aufsteigend bei 0 beginnend und speichert sie in dem Array wie folgt: Folgenglied 0 steht an Position 0 im Array, Folgenglied 1 steht an Position 1 im Array, usw.
  
Hinweis: Wenn Ihr mit der Programmidee oder der Implementation Probleme habt, zögert nicht, einen Tutor zu fragen.
+
Hinweis: Wenn Ihr mit der Programmidee oder der Implementierung Probleme habt, zögert nicht, einen Tutor zu fragen.
 
 
  
 
== Benchmark und Auswertung ==
 
== Benchmark und Auswertung ==
Zeile 75: Zeile 81:
  
 
Tipp: Sollte Euer iteratives Programm nicht binnen weniger Sekunden sämtliche Zahlen berechnet haben, lasst unbedingt einen Tutor kurz drüberschauen.
 
Tipp: Sollte Euer iteratives Programm nicht binnen weniger Sekunden sämtliche Zahlen berechnet haben, lasst unbedingt einen Tutor kurz drüberschauen.
 +
 +
 +
 +
 +
 +
 +
== Kommentare ==
 +
Wenn du Anmerkungen zur Aufgabe hast oder Lob und Kritik loswerden möchtest, ist hier die richtige Stelle dafür. Klicke einfach ganz rechts auf "bearbeiten" und schreibe deinen Kommentar direkt ins Wiki. Keine Scheu, es geht nichts kaputt ;)
 +
 +
<!--
 +
Als kleine Starthilfe folgt ein Beispiel, wie so ein Kommentar formatiert sein könnte. Mit "Vorschau zeigen" kannst du dir ansehen, was deine Änderung bewirken würde, ohne wirklich etwas zu ändern.
 +
Du musst übrigens außerhalb dieses auskommentieren Bereichs schreiben ;)
 +
 +
==== Robert ====
 +
Na mal schauen, ob irgendjemand diese Funktion wirklich benutzt. Ich fände es jedenfalls toll.
 +
-->
 +
 +
[[Kategorie:Java]]
 +
[[Kategorie:Java_Aufgaben]]

Aktuelle Version vom 5. März 2013, 10:42 Uhr

Das Ziel dieser Aufgabe ist es, dass Ihr möglichst viele Eurer bisher erworbenen Java-Kenntnisse Schritt für Schritt anwendet. Abschließend sollt Ihr noch einen kleinen Benchmark einer rekursiv und iterativ implementierten Funktion durchführen.

Aufgabenstellung

Seht euch die Codebeispiele an und findet heraus, was der Code tut. Schreibt den Code anschließend neu, sodass der Code übersichtlicher und lesbarer ist.

Gegeben ist folgende kleine Funktion:

public static void main(String args[]) {
	int[] testValues = { 5, 10, 15, 20, 30, 40 };
	for (int i = 0; i < testValues.length; ++i) {
		System.out.println(doSomethingClever(testValues[i]));
	}
}

public static int doSomethingClever(int a) {
	int b;
	if (a <= 1) {
		if (a == 1) {
			b = calcSomethingNice(a);
		} else {
			b = getSomeSmartInt(a - 1);
		}
	} else {
		return theSmartestMethodsAlwaysNeedRidiculouslyLongNames(a);
	}
	return b;
}

public static int getSomeSmartInt(int c) {
	return ++c;
}

public static int calcSomethingNice(int d) {
	int i = 1;
	for (i = d * 11; i > d; i--) {
		i--;
	}
	return i;
}

public static int theSmartestMethodsAlwaysNeedRidiculouslyLongNames(int e) {
	int container = doSomethingClever(e - 1);
	return container + doSomethingClever(e - 2);
}

Offensichtlich ist hier programmiertechnisch einiges schief gegangen. Denn obwohl der Code richtig funktioniert, ist er nur schwer leserlich. Folgende Fehler wurden gemacht:

  • nichtssagende Benennung der Variablen und Methoden,
  • keine Kommentare,
  • übertriebene Auslagerung in Extra-Methoden.

Hinweis: Die obige Funktionalität ist rekursiv implementiert.

All das sollt Ihr jetzt schrittweise ändern:

  1. Versucht, ohne den PC mit einigen Handsimulationen herauszufinden, was doSomethingClever eigentlich berechnet.
    • Hinweis: Beginnt mit kleinen Zahlen wie 0, 1, 2 oder 3 und macht mehrere Durchgänge.
    • Tipp: Es wird stets das n-te Glied einer bekannten Zahlenfolge berechnet.
  2. Integriert zuerst die beiden Hilfsfunktionen getSomeSmartInt und calcSomethingNice in die Hauptfunktion, da beide ziemlich überflüssig sind.
  3. Löst die verschachtelte Rekursion von doSomethingClever und theSmartest... auf.
  4. Lasst Euch "sprechende" Namen sowohl für die Variablen, Methode(n) und als auch die Klasse einfallen.
  5. Fügt ausreichend viele und prägnante Kommentare hinzu, bis das Programm für Euch gut lesbar ist.
  6. Wichtig: Holt Euch nun einen Tutor ran, zeigt ihm Euer Programm und diskutiert die Lesbarkeit des Codes. Er kann euch sicherlich nützliche Tipps geben, was Ihr in Zukunft beim Programmieren unbedingt beachten solltet.

Eine Iterative Alternative

Schreibt nun ein Programm, das die gleiche Zahlenreihe nicht-rekursiv berechnet. Verwendet dazu ein Array von Integern und folgende Idee:

  • Initialisiert ein Array, das alle Folgenglieder (bei 0 anfangend) bis zum Gesuchten aufnehmen kann.
  • Berechnet die Folgenglieder in einer Schleife Eurer Wahl aufsteigend bei 0 beginnend und speichert sie in dem Array wie folgt: Folgenglied 0 steht an Position 0 im Array, Folgenglied 1 steht an Position 1 im Array, usw.

Hinweis: Wenn Ihr mit der Programmidee oder der Implementierung Probleme habt, zögert nicht, einen Tutor zu fragen.

Benchmark und Auswertung

Schreibt nun ein letztes kurzes Programm, das zuerst die Folgenglieder 5, 10, 15, 20, 30 und 40 iterativ und dann noch einmal rekursiv berechnet und sofort auf der Console ausdruckt.

Diskutiert die Geschwindigkeitsunterschiede und die möglichen Vorteile der iterativen Implementation mit einem Tutor.

Tipp: Sollte Euer iteratives Programm nicht binnen weniger Sekunden sämtliche Zahlen berechnet haben, lasst unbedingt einen Tutor kurz drüberschauen.




Kommentare

Wenn du Anmerkungen zur Aufgabe hast oder Lob und Kritik loswerden möchtest, ist hier die richtige Stelle dafür. Klicke einfach ganz rechts auf "bearbeiten" und schreibe deinen Kommentar direkt ins Wiki. Keine Scheu, es geht nichts kaputt ;)