Rekursive Methode

[dan1996]

Hallo ich arbeite an einer Aufgabe und es ist eine rekursive Methode gegeben.. Problem ist dass ich nicht den Sinn/ die Funktion dieser Methode erkenne.. Kann mir jemand dabei weiter helfen ?

static int f(int n) {
        if (n <= 1) return n;
        if (n%2 == 1) return n+f(n-2);
        return  n;
}

 

[kneitzel]

Soll es da denn einen Sinn geben? Oder ist es einfach nur die Berechnung einer Zahlenreihe?

Für ungerade Zahlen kommen die Quadratzahlen raus. 1 -> 1, 3->4, 5->9, 7->16, ... Gerade Zahlen bleiben grade Zahlen...

 

[dan1996]

Die Aufgabe ist Was berechnet diese rekursive Methode? Schreiben Sie diese Methode nicht rekursiv mit Verwendung der Datenstruktur Stack...

 

[dan1996]

ich verstehe auch nicht den Bezug vom Parameter n zur Quadratzahl..

 

[kneitzel]

Ungerade Zahlen (1, 3, 5, 7, 9, ...) sind immer 2x-1 (1 = 2*1-1; 3 = 2*2-1; 5=3*2-1)
Und x^2 = (x-1 + 1)^2 = (x-1)^2+2(x-1)+1 = (x-1)^2+(2x-1)
Somit ist x^2 ausdrückbar durch die vorhergehende Quadratzahl + eben dem 2x-1 was genau der xten ungeraden Zahl entspricht.

Das ist der mathematische Zusammenhang, weshalb bei der Zahlenfolge bei den ungeraden Zahlen immer Quadratzahlen ausgegeben werden (Zusammen mit dem Endpunkt: f(1) = 1 natürlich. Wäre f(1) nicht 1, dann würde das auch nicht hin kommen).

Ansonsten sieht man das auch direkt, wenn man sich die f(n) für die ersten 10 Zahlen aufschreibt ...

 

[dan1996]

Danke, was ich mir immer noch nicht zusammenreimen kann, ist wie man diese Methode mithilfe eines Stacks umschreiben kann

 

[M.L.]

Stacks

Geraten: die Zahlen sind nicht nur zusätzlich iterativ zu berechnen, sondern auch zwischenzuspeichern und abzuleiten. Z.B. in einem Stack (s. Kommentar zu "search")

 

[Xyz1]

import java.util.ArrayDeque;
import java.util.Deque;

public class M {
	public int a(int n) {
		if (n <= 1)
			return n;
		if (n % 2 == 1)
			return n + a(n - 2);
		return n;
	}

	public int b(int n) {
		Deque<Integer> d = new ArrayDeque<Integer>();
		d.push(n);
		int sum = 0;
		while (!d.isEmpty()) {
			int f = d.removeFirst();
			sum += f;
			if (f > 1 && f % 2 == 1) {
				d.addLast(f - 2);
			}
		}
		return sum;
	}

	public int c(int n) {
		if (n % 2 == 1) {
			return (n + 1) * (n + 1) / 4;
		}
		return n;
	}

	public static void main(String[] args) {
		M m = new M();
		// ...
	}
}

 

[Xyz1]

Es gibt auch noch eine vierte Möglichkeit mit einer simplen for Schleife, fällt mir gerade auf
Euch auch?