Rekursion

[freaki_333]

Hi,

ich soll eine applikative Funktion erstellen.

Meine Methode sieht so aus:
die klappt auch aber wenn ich für "i" so ca 10000 eingebe bekomme ich ein :Exception in thread "main" java.lang.StackOverflowErrorn

ist das jetzt Java spezifisch oder habe ich nur blöde programmiert?

 public double f_applikative(int i) {
		double ergebnis = 0;
		
		if (i > 1) {
			ergebnis = f_applikative(i - 1);
		}
		ergebnis += 1.0 / ((double) i * i);
		
		return ergebnis;
	}

 

[0din]

naja, is ziemlich simpel
StackOverflow = Speicher voll

passiert schnell un leicht bei rekursion... einfach n abbruch bei 10000 machen un beim dozenten/lehrer/what ever sagen dasset danach einfach zuviel wird um mit rekursion zu arbeiten

 

[SlaterB]

standardmäßig verkraftet Java nur so viele ineinander geschachtelte Methodenaufrufe, wie du sie hast,
das sollte auch ausreichen für die allermeisten Rekursionen, ich brauchte noch nie mehr,

wenn du aber von 1-10000 alles rekursiv machst, was genauso leicht in einer Schleife ginge,
dann überforderst du natürlich Java,

man kann aber die maximale Rekursionstiefe erhöhen,
siehe
http://www.java-forum.org/allgemein...ckoverflowerror-bei-rekursion-verhindern.html
sowie für Windows
http://www.java-forum.org/allgemeine-java-themen/64258-rekursion-und-stackoverflow.html

 

[0x7F800000]

ist das jetzt Java spezifisch oder habe ich nur blöde programmiert?

Beides. Du könntest diese funktion so umschreiben, dass sie endrekursiv wird. Daher ist es gewissermaßen "blöd programmiert". Das würde dir bei java aber nichts nützen, weil es endrekursion nicht erkennt, daher "java spezifisch". Dir bleibt wohl nichts anderes übrig, als alles in iterative form umzuschreiben. Und pass auf, dass du die reihe von hinten nach vorne aufaddierst.

 

[Landei]

Sun's JVM kennt keine Endrekursion, andere Implementierungen (wie von IBM) allerdings schon.

 

[0x7F800000]

Versteh ich nicht. Wenn man anfängt, gegen bestimmte Implementierungen der JVM zu programmieren, wo ist dann überhaupt der Sinn so einer VirtualMachine. :bahnhof:

 

[Landei]

Ich habe nicht gesagt, dass es eine gute Idee ist, gegen eine bestimmte JVM zu programmieren, sondern nur, dass manche JVMs Endrekursion beherrschen (und übrigens auch eine gewisse JVM-Sprache per Compiler-Optimierung).

 

[freaki_333]

Ich nochmal...
diesesmal geht es aber ums suchen mit rekursion bzw applikative Funktion.
Wir sollen ein 100000 Feld großes Array die größte Zahl finden. Das soll laut Prof. Funktionieren, und er hat den Tip gegeben, dass das man das array nur Teilweise durchsuchen sollte aber ich hab keine Ahnung. Hat jemand eine Idee? Es muss keine Lösung sein es reicht vollkommen aus wenn man mir Schlagwörter sagt.


Gruß freaki

 

[Painii]

Wie würdest du denn einen GROSSEN Stapel Papier durchsuchen? (Wenn dann auf jedem Blatt ein Zahl steht suchst du aus dem Stapel das Blatt mit der höchsten Zahl)

 

[freaki_333]

Ich versteh dein Beispiel/Hinweiß leider nicht!

Wenn ich ein großen Stabel Papier habe und die unsortiert sind müsste ich (bei mein klein Hirn ^^) die einzeln nach gucken und immmer die höchste Zahl rausnehmen.

vllt. sollte ich mein Problem weiter erläutern und das zwar geht das Problem um dem OverFlow. Mein Prof meint das man in Java mit einer applikative Funktion auch ein Array welches ein Feldlänge von 100000 hat durchsuchen kann ohne ein StackOverFlow zu bekommen.

 

[faetzminator]

Also 100'000'000 funktioniert bei mir noch und 1'000'000'000 wirft einen java.lang.OutOfMemoryError

 

[freaki_333]

Hi,
ja also ohne schleifen nur mit rekursion? wenn ja wär nett wenn du mir ein ansatz sagen könntes

 

[0x7F800000]

Beide folgende Algos sind zumindest in java schwachsinnig, und nur vom akademischen interesse...

Aber erklär mir mal, wieso max2 wunderbar funzt, während max1 jämmerlich verreckt. Beide sind rekursiv.

import static java.lang.System.*;

public class _ {
	
	public static int max(int x, int y){
		return x>y?x:y;
	}
	

	public static int max1(int[] a){
		return max1(a,a.length);
	}
	
	public static int max1(int[] a, int end){
		if(end==1){
			return a[0];
		}else{
			return max(max1(a,end-1),a[end-1]);
		}
	}
	
	public static int max2(int[] a){
		return max2(a,0,a.length);
	}
	public static int max2(int[] a,int start, int end){
		if(end-start==1){
			return a[start];
		}else{
			int middle=(start+end)/2;
			return max(max2(a,start,middle),max2(a,middle,end));
		}
	}
	public static void main(String..._){
		
		for(int n:new int[]{100,1000,10000,100000,10000000}){
			int[] a=new int[n];
			for(int i=0; i<a.length; i++){
				a[i]=(i*i)%213265343;
			}
			out.print("1:\t"); try{out.println(max1(a));}catch(Error e){out.println(e);}
			out.print("2:\t"); try{out.println(max2(a));}catch(Error e){out.println(e);}
		}
		
	}
}

 

[faetzminator]

Ich hab von der Logik her das gleiche wie 0x7F800000 gemacht, als einziger Unterschied arbeite ich intern mit start und len statt start und end Btw, unnötige else cases

 

[freaki_333]

Hi danke erst mal für deine Antwort,
also bei max2 teils du das Array im 2 hälften und suchst die in 2 hälften parrallel ab?! aber ganz verstehe ich nicht wieso das geht bzw. der stack nicht wächst?

 

[faetzminator]

Wieso? Du brauchst für max1() [c]n[/c] Aufrufe. Für max2() irgendwas wie [c]n^0.5[/c] oder [c]n*log(n)[/c] oder so...

 

[freaki_333]

sorry wenn ich nerve aber es bringt mir nichts wenn ich das jetzt kopiere und davon nix raffe,
deshalb möchte ich gern das wiese näher erläutert bekommen bzw. man nur n^0,5 aufrufe hat da bin ich noch nichts ganz durchgestiegen. vllt gibt es für diesen algo ein namen dann kann ich das selber nachlesen

 

[faetzminator]

Aufrufe hast du gleich viele, doch der Stack ist kleiner. Als Beispiel bei n = 16 bei max1():

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

max2():

   1          9
 2   5     10   13
3 4 6 7  11 12 14 15
      8           16

Tiefe 16 vs. 5 (zuerst Aufruf mit allem)

Edit: nun sollte die Teilung stimmen

 

[0x7F800000]

Wieso? Du brauchst für max1() [c]n[/c] Aufrufe. Für max2() irgendwas wie [c]n^0.5[/c] oder [c]n*log(n)[/c] oder so...

complexity analysis fail?
[nicht bös gemeint, schon klar, dass kein mensch ohne guten grund den code genau anschaut :smoke:]

sorry wenn ich nerve aber es bringt mir nichts wenn ich das jetzt kopiere und davon nix raffe

vorbildliche einstellung, darauf habe ich doch sehr gehofft...

deshalb möchte ich gern das wiese näher erläutert bekommen bzw. man nur n^0,5 aufrufe hat da bin ich noch nichts ganz durchgestiegen. vllt gibt es für diesen algo ein namen dann kann ich das selber nachlesen

n^0,5 kommt da nirgends vor, die Zahl scheint frei erfunden.
Weniger aufrufe kriegst du auch nicht.
Schneller laufen tut es auch nicht, als die normale iterative variante, eher langsamer.
Jeder Eintrag wird genau einmal angeschaut.

Aber wie hoch der Stack jeweils wird, das solltest du mal nachrechnen...

edit: @faetzminator: gute skizze! :toll:

 

[faetzminator]

0x7F800000 ich spreche nur von dem Stack. Wie ich auf [c]n^0.5[/c] (was sqrt(n) wär) kann ich irgendwie nicht mehr erklären *g*. Dass man gleich viele Aufrufe hat, hab ich doch geschrieben .

 

[freaki_333]

Morgen,

thx an alle die mir geholfen haben.

 

[0x7F800000]

thx an alle die mir geholfen haben.

bluptsch^^ vom herumthxen ist noch keiner schlauer geworden, erzähl mal lieber, wie hoch der stack bei der zweiten variante wird. Mal dir ggf. skizze für 1,2,4,8,16... elemente.