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/Musterlösung

< Javakurs‎ | Übungsaufgaben‎ | Rekursion vs. Iteration
Version vom 4. März 2013, 13:41 Uhr von MarkusH (Diskussion | Beiträge) (fix alignment)
(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)
public class RecursionVsIteration {
	public static void main(String args[]) {
		int[] testValues = { 5, 10, 15, 20, 30, 40 };
		timeTest(testValues);
	}

	/* calculates FibonacciNumbers */
	public static int fibonacciRek(int n) {
		int result;
		if (n <= 1) {
			if (n == 1) {
				result = 1;
			} else if (n == 0) {
				result = 0;
			} else {
				System.out.println("Fibonacci numbers undefined for negative values.");
				result = -1;
			}
		} else {
			result = fibonacciRek(n - 1) + fibonacciRek(n - 2);
		}
		return result;
	}

	public static int fibonacciIte(int n) {
		int result;
		if (n <= 1) {
			if (n == 1) {
				result = 1;
			} else if (n == 0) {
				result = 0;
			} else {
				System.out.println("Fibonacci numbers undefined for negative values.");
				result = -1;
			}
		} else {
			// n+1 because in the n-th entry is the n-th fibonacci number
			int[] predecessors = new int[n + 1];
			predecessors[0] = 0;
			predecessors[1] = 1;
			for (int i = 2; i < predecessors.length; i++) {
				predecessors[i] = predecessors[i - 1] + predecessors[i - 2];
			}
			result = predecessors[n];
		}
		return result;
	}

	public static void timeTest(int[] values) {
		long before;
		long after;
		// recursion time test
		before = System.currentTimeMillis();
		for (int i = 0; i < values.length; i++) {
			// fibonacciRek(values[i]);
			System.out.print("f(" + values[i] + ")= ");
			System.out.println(fibonacciRek(values[i]));
		}
		after = System.currentTimeMillis();
		System.out.println("Rekursion benötigt: " + (after - before) + " ms");
		// iteration time test
		before = System.currentTimeMillis();

		for (int i = 0; i < values.length; i++) {
			// fibonacciIte(values[i]);
			System.out.print("f(" + values[i] + ")= ");
			System.out.println(fibonacciIte(values[i]));
		}
		after = System.currentTimeMillis();
		System.out.println("Iteration benötigt: " + (after - before) + " ms");
	}
}