Wann terminiert ein Programm ?

molleonair

Hallo Profis ..ich hab hier ne Aufgabe gestellt bekommen.
Ich soll sagen ob das folgende mini programm für jede eingabe terminiert.
ich glaub das bezieht sich darauf das mit scanf eine Int variable eingelesen wird.
Was aber wenn ich was anderes eingebe?? Das ist doch bestimmt von der Entwicklungsumgebung abhängig.

#include <stdio.h>
float funk (int zahl);

void main ()
   	{
	int i;
	printf ("\n Eingabe :  ");
	scanf ("%d",&i);
	printf("\n \n Ausgabe (%d)  =  %f",i,funk(i));
	}
float funk (int zahl)
	{
	float erg=0.0;
	if (zahl>0)
		erg=zahl+funk(zahl/3)/funk(zahl-1);
	else
		erg=1.0;
	return (erg);
	}

Simon2

molleonair schrieb:

...Das ist doch bestimmt von der Entwicklungsumgebung abhängig. ...

Glaubst Du nicht, dass es darum geht, wann die Abbruchbedingung der Rekursion erfüllt ist, bzw. ob es "stabile Zirkel" für den Algorithmus gibt ?

Für mich sieht das nicht wie eine typische "Programmiersprachenkönner-Aufgabe" aus, sondern eher etwas, was sich mit dem konkreten Algorithmus beschäftigt.

Gruß,

Simon2.

molleonair

tja ich weiß nicht so recht
die frage heißt: Terniniert das Programm für jede zulässige Eingabe?

da stellt sich die Frage was ist eine zulässige Eingabe .... vieleicht einfach ne integer zahl

und wie bekomm ich raus ob die rekursive funktion auch zum ende findet.

Wie funktioniert so ein Programm der benötigte speicher der funktion ist ja abhängig von der größe der zahl je größer desto mehr instanzen laufen gleichzeitig desto mehr speicher brauchts programm also wenn ich das auf nem system mit begrenzten cache laufen lass ist doch irgendwann ein überlauf erreicht oder ?

Das Argument von funk(int zahl) wird mit jedem Aufruf kleiner.
Es muss eine ganze Zahl sein (Integer-Arithmetik bei zahl/3).
Es kann aber nicht negativ werden.

Daraus ergibt sich, dass die Funktion immer terminiert.
Allerdings könnte die Terminierung bei sehr großen
Anfangswerten in einem Stack-Overflow bestehen

Bei einem Anfangswert N ist spätestens nach N-mal Schluss.

molleonair

das mit dem stack ist das was ich meine

nimmt sich das Programm den speicher erst dynamisch zu laufzeit oder schaut der compiler schon vorher nach maximalen werten und reserviert den speicher beim erstellen des proggs ?

Der Compiler kann nicht wissen, wie die Rekursionstiefe maximal
sein könnte. zahl wird ja auch erst beim Laufen des Progs
eingegeben.
Er reserviert also nix extra. Der zur Verfügung
stehende Stack ist allerdings begrenzt, d.h. ggf. kracht es
zur Laufzeit.

Ich nehme mal an, dass "für jede eingabe" nicht Fehler meint,
wie statt einer Zahl XXX einzugeben.

molleonair

ich dachte das der compiler irgendwie weiß das ja maximal ne integer mit ca 32000 eingegeben werden kann und dann den gesamten platz freimacht im code.

Also lässt sich festhalten das wenn genügend stacktiefe da ist.die funktion immer terminiert,da die aufrufe von funk immer kleiner werden und somit sichergestellt ist das die funktion auch irgendwann verlassen wird,da ja innerhalb der funktion bei übergebenen parametern <= 0 der wert 1 zurückgegeben wird.

Helium

Ich dneke du sollt dich nicht, um den Stack oder um mögliche Falsche Eingaben kümmern. Es geht eher in Richtung Mathematik