Aufgabe mit einer endrekursiven Funktion

Schnelle objektorientierte, kompilierende Programmiersprache.
Antworten
forumnewbie
Beiträge: 80
Registriert: Di Jan 15, 2013 9:02 pm

Aufgabe mit einer endrekursiven Funktion

Beitrag von forumnewbie » Sa Feb 02, 2013 8:06 pm

Hi, ich brauche eure Hilfe bei der Beantwortung dieser Aufgabe.

Folgende Funktion ist gegeben (Überläufe bleiben unberücksichtigt):

Code: Alles auswählen

int f1(int par1, int par2)
{
    if(par1 == 0) return par2;
    else return f1(par1-1, par2+1);
}
Fragen zu der Aufgabe:
1. Man muss die Menge der Werte eingeben, für die f1 terminiert.
2. f1(par1, par2) als möglichst einfache Formel aufschreiben.
3. Eine endrekursive Version schreiben oder begründen, warum diese Funktion f1 bereits endrekursiv ist.
1. Sind hier einfach die Zahlen 0 für par1 und beliebige int-Zahl für par2 gemeint, mit der die Funktion beendet wird? Ansonsten verstehe ich nicht, was mit "für die f1 terminiert" gemeint ist.
2. Mein Vorschlag:

Code: Alles auswählen

int f1(int par1, int par2){return par1+par2;}
Ist das mit der Formel gemeint?
3. Ich würde sagen, dass diese Funktion bereits endrekursiv ist. Begründung: in der letzten Anweisung der Funktion ruft sich die Funktion selbst auf. Stimmt diese Antwort?
4. Wann und wo entstehen hier Überläufe? Der einzige Überlauf, der meiner Meinung nach hier entstehen könnte, ist wenn der Rückgabewert größer ist, als Integer speichern kann.

Danke!

Benutzeravatar
cloidnerux
Moderator
Beiträge: 3123
Registriert: Fr Sep 26, 2008 4:37 pm
Wohnort: Ram (Gibts wirklich)

Re: Aufgabe mit einer endrekursiven Funktion

Beitrag von cloidnerux » Sa Feb 02, 2013 8:19 pm

1. Sind hier einfach die Zahlen 0 für par1 und beliebige int-Zahl für par2 gemeint, mit der die Funktion beendet wird? Ansonsten verstehe ich nicht, was mit "für die f1 terminiert" gemeint ist.
Ich denke, dass alle Zahlen kleiner 0 für par1 die Funktion nicht Terminieren, da ungeachtet des möglichen Zahlraums für int par1 nicht mehr 0 werden wird, wenn sie mit kleiner 0 begonnen wird.
Für par2 sollte es stimmen.
Ist das mit der Formel gemeint?
In der Regel meint man Mathematische Formel:

Code: Alles auswählen

f(par1, par2)=par+par2
bzw ohne die Variablennamen aus deinem Code:

Code: Alles auswählen

f(a, b)=a+b
4. Wann und wo entstehen hier Überläufe? Der einzige Überlauf, der meiner Meinung nach hier entstehen könnte, ist wenn der Rückgabewert größer ist, als Integer speichern kann.
Der Stack wird auf jeden Fall überlaufen, wenn du für par1 einen Wert >~60000 wählst(meine ich zumindest, wenn nicht größeres par1 wählen).
Redundanz macht wiederholen unnötig.
quod erat expectandum

forumnewbie
Beiträge: 80
Registriert: Di Jan 15, 2013 9:02 pm

Re: Aufgabe mit einer endrekursiven Funktion

Beitrag von forumnewbie » Sa Feb 02, 2013 8:33 pm

Danke für die schnelle Antwort!

Also bedeutet "nicht terminieren" = eine Endlosschleife verursachen, richtig? Da Überläufe laut Aufgabenstellung unwichtig sind, kann ich dann für par1 als Antwort die Menge von 0 bis n angeben. Wobei n Element der Menge der natürlichen Zahlen ist.

Dann bleibt nur noch die Frage 3 offen.

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Aufgabe mit einer endrekursiven Funktion

Beitrag von Xin » So Feb 03, 2013 11:27 am

forumnewbie hat geschrieben:Hi, ich brauche eure Hilfe bei der Beantwortung dieser Aufgabe.

Folgende Funktion ist gegeben (Überläufe bleiben unberücksichtigt):

Code: Alles auswählen

int f1(int par1, int par2)
{
    if(par1 == 0) return par2;
    else return f1(par1-1, par2+1);
}
Fragen zu der Aufgabe:

1. Man muss die Menge der Werte eingeben, für die f1 terminiert.
Die Funktion terminiert immer, da par1 einfach bis 0 runterzählt.
Da Integers bei zu großen Negativen ins Positive überlaufen, kommst Du auch bei Negativen Werten für par1 wieder bei 0 an.

Die Funktion addiert par1 auf par2.
forumnewbie hat geschrieben:3. Eine endrekursive Version schreiben oder begründen, warum diese Funktion f1 bereits endrekursiv ist.
Musste ich erst nachschlagen, was das bedeutet.

Ist endrekursiv und kann daher leicht optimiert werden.
forumnewbie hat geschrieben:4. Wann und wo entstehen hier Überläufe? Der einzige Überlauf, der meiner Meinung nach hier entstehen könnte, ist wenn der Rückgabewert größer ist, als Integer speichern kann.
par1 ist negativ, läuft über, um die 0 zu erreichen.
par1+par2 >= INT_MAX => Überlauf
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

forumnewbie
Beiträge: 80
Registriert: Di Jan 15, 2013 9:02 pm

Re: Aufgabe mit einer endrekursiven Funktion

Beitrag von forumnewbie » So Feb 03, 2013 4:01 pm

Die Funktion terminiert immer, da par1 einfach bis 0 runterzählt.
Da Integers bei zu großen Negativen ins Positive überlaufen, kommst Du auch bei Negativen Werten für par1 wieder bei 0 an.
Daran habe ich nicht gedacht. Das Programm müsste ja wieder von oben anfangen, wenn es ganz unten an die Grenze angekommen ist und weiter laufen will -> also läuft es in einem Kreis. Ich wollte das ausprobieren, aber das Programm stürzt bei mir sofort ab, wenn ich -1 für par1 angebe. Hängt das vom Compiler ab, ob ein Programm bei einem Überlauf abstürzt oder nicht?

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Aufgabe mit einer endrekursiven Funktion

Beitrag von Xin » So Feb 03, 2013 5:53 pm

forumnewbie hat geschrieben:
Die Funktion terminiert immer, da par1 einfach bis 0 runterzählt.
Da Integers bei zu großen Negativen ins Positive überlaufen, kommst Du auch bei Negativen Werten für par1 wieder bei 0 an.
Daran habe ich nicht gedacht. Das Programm müsste ja wieder von oben anfangen, wenn es ganz unten an die Grenze angekommen ist und weiter laufen will -> also läuft es in einem Kreis. Ich wollte das ausprobieren, aber das Programm stürzt bei mir sofort ab, wenn ich -1 für par1 angebe. Hängt das vom Compiler ab, ob ein Programm bei einem Überlauf abstürzt oder nicht?
Nein, ich denke, das hängt vom Entwickler ab. ;-)

Hättest Du den Code gepostet, könnte ich konkreter werden. ^^
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

forumnewbie
Beiträge: 80
Registriert: Di Jan 15, 2013 9:02 pm

Re: Aufgabe mit einer endrekursiven Funktion

Beitrag von forumnewbie » So Feb 03, 2013 6:43 pm

:D

Code: Alles auswählen

#include <stdio.h>

int f1(int par1, int par2)
{
    if(par1 == 0) return par2;
    else return f1(par1-1, par2+1);
}

int main()
{
    int a;
    a = f1(-1,1); //mit <0 funktioniert nicht
    printf("%d", a);
    return 0;
}
Also sobald ich für par1 als Argument eine Zahl < 0 eingebe, stürzt mein Programm ab.
Ich bekomme dann eine Fehlermeldung: "rekf.exe funktioniert nicht mehr. Es wird nach einer Lösung für das Problem gesucht..."

Benutzeravatar
Dirty Oerti
Beiträge: 2229
Registriert: Di Jul 08, 2008 5:05 pm
Wohnort: Thurndorf / Würzburg

Re: Aufgabe mit einer endrekursiven Funktion

Beitrag von Dirty Oerti » Mo Feb 04, 2013 12:55 am

Hm, das liegt daran, dass VC (mit dem du vermutlich kompilierst) per Default eine Stack Size von 1 MB vergibt, und die ist sehr schnell aufgebraucht. Ich teste gerade, ob es eine Stack Größe gibt, mehr der das Programm noch läuft :D

Sprich dein Stack wird voll, weil du zu oft rekursieren musst, um zu par1 == 0 zu gelangen. Ändere den Datentyp von int nach char und du wirst sehen, dass es nun funktioniert :)


*edit*
Nein, mit int bekomme ich es hier nicht zum laufen, ist ja auch irgendwie logisch, so viele Stack Frames passen nicht in den Speicher :D

Code: Alles auswählen

#include <stdio.h>
#include <limits.h>
#include <sys/resource.h>

#define LINUX 1

int f1(int par1, int par2)
{
	if(par1 == 0) return par2;
	else return f1(par1-1, par2+1);
}

int main()
{
#ifdef LINUX
	const rlim_t stackSize = INT_MAX;
	struct rlimit rl;
	int result;
	result = getrlimit(RLIMIT_STACK, &rl);
	if (result == 0)
	{
		if (rl.rlim_cur < stackSize)
		{
			rl.rlim_cur = stackSize;
			result = setrlimit(RLIMIT_STACK, &rl);
			if (result != 0)
			{
				fprintf(stderr, "Error setting stack size = %d\n", result);
			}
		}
	}
#endif
	int a;
	a = f1(-1,1);
	printf("%d", a);
	return 0;
}

Es geht also theoretisch, praktisch aber eher nicht :)


Der Spaß hat nur dazu geführt, dass jetzt 400 MB auf meiner Swap Partition liegen :D
Bei Fragen einfach an daniel[ät]proggen[Punkt]org
Ich helfe gerne! :)
----------
Wenn du ein Licht am Ende des Tunnels siehst, freu dich nicht zu früh! Es könnte ein Zug sein, der auf dich zukommt!
----
It said: "Install Win95 or better ..." So I installed Linux.

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Aufgabe mit einer endrekursiven Funktion

Beitrag von Xin » Mo Feb 04, 2013 10:32 am

Dirty Oerti hat geschrieben:Nein, mit int bekomme ich es hier nicht zum laufen, ist ja auch irgendwie logisch, so viele Stack Frames passen nicht in den Speicher :D
-1 zählt etwas über 4 Milliarden Mal (2^32 mal)

Du brauchst für das Stackframe 8 Byte Rückspungadresse, 2*4 Byte Parameter, je nach Implementierung 4 Byte Rückgabe. => 16-20 Byte.
Gehen wir von 16 aus, dass sind 2^4.
2^4*2^32 = 2^36.

Um das Programm auszuführen benötigst Du also 64GB RAM für den Stack und noch ein, zwei GB für das OS. Auf einem Rechner mit 68GB würde es also laufen.
Und sollte das als Swap-Space zur Verfügung stehen, natürlich auch auf den kleinen Gurken, die wir so haben. Wir müssten nur etwas mehr Geduld haben. ;-)

Ein gutes Beispiel dafür, wo man Software optimieren kann und sollte... ;-)
Es zeigt sehr schön, wo Software richtige Ergebnisse liefern kann, aber trotzdem falsch ist. ^^
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Benutzeravatar
Dirty Oerti
Beiträge: 2229
Registriert: Di Jul 08, 2008 5:05 pm
Wohnort: Thurndorf / Würzburg

Re: Aufgabe mit einer endrekursiven Funktion

Beitrag von Dirty Oerti » Mo Feb 04, 2013 10:54 am

Mit short ging es wie gesagt, also hatte ich 2^16 * 2^4 = 2^20 Bytes = 2^10 KiB = 2 MiB an Stack :D

Ich hatte das auch mit gdb laufen, da war ein "bt" sehr lustig :)
Bei Fragen einfach an daniel[ät]proggen[Punkt]org
Ich helfe gerne! :)
----------
Wenn du ein Licht am Ende des Tunnels siehst, freu dich nicht zu früh! Es könnte ein Zug sein, der auf dich zukommt!
----
It said: "Install Win95 or better ..." So I installed Linux.

Antworten