Stack statt Rekursion.

ProgrammierGeselle

Hallo liebe Community.

nachdem ich schon ein paar mal davon gehört habe, dass Rekursion das "gleiche" sein soll wie ein Stack, habe ich mich an den Schreibtisch gesetzt und versucht ein einfaches Beispiel mit einem Stack statt Rekursion zu lösen. Dies ist mir auch soweit gelungen.
Komischer Weise braucht die iterative Variante mehr Zeit, sollte die nicht schneller sein?

Mein Code:

#include <cstdio>
#include <ctime>
#include <cctype>
#include <cstring>
#include <stack>

using namespace std;

char str [250];
char tmp [250];
stack <int> stapel;

void func (int index) {
	if (index>=strlen(str)) {
		//printf("%s\n", tmp);
		return ;
	}

	for (int i=0;i<strlen(str);++i) {
		if (tmp[i]==' ') {
			tmp[i] = str[index];
			func(index+1);
			tmp[i] = ' ';
		}
	}
}

void iter () {
	int index=0, i=0;
	while (index>=0) {
		if (index>=strlen(str)) {
			//printf("%s\n", tmp);
			--index;
			stapel.pop();
		}
		else {
			if (stapel.top()!=-1)
				tmp[stapel.top()] = ' ';
			for (i=stapel.top()+1;i<strlen(str) && tmp[i]!=' ';++i)
				;
			if (i<strlen(str) && tmp[i]==' ') {
				stapel.pop();
				stapel.push(i);
				tmp[i] = str[index];
				stapel.push(-1);
				++index;
			}
			if (i>=strlen(str)) {
				--index;
				stapel.pop();
			}
		}
	}
}

int main () {
	int index=0, i;
	double start;
	printf("str: "); scanf("%s", str);
	printf("Moegliche Reihenfolgen rekursiv\n");
	for (i=0;i<strlen(str);++i)
		tmp[i]=' ';
	start=clock();
	func(0);
	printf("Clocks: %.3f\n", (clock()-start)/CLOCKS_PER_SEC);
	printf("Moegliche Reihenfolgen iterativ\n");
	for (i=0;i<strlen(str);++i)
		tmp[i]=' ';
	stapel.push(-1);
	start=clock();
	iter();
	printf("Clocks: %.3f\n", (clock()-start)/CLOCKS_PER_SEC);
	return 0;
}

Gibt es noch eine effizientere Methode um das Problem iterativ zu lösen?
Leider habe ich nichts passendes im Netz gefunden,
wenn ihr also noch ein paar hilfreiche Links zu diesem Thema habt,
könnt ihr sie mir gerne posten!

mfg Programmiergeselle

EXDW

ich hab den code selber jetzt nicht an geschaut
was ich mir aber denken kann ist das das Push und Pop die performance frist
wenn man nur direkt durch iteriert kostet das weniger als wenn die ganzen objekte staendig verschoben werden muessen

nachdem ich schon ein paar mal davon gehört habe, dass Rekursion das "gleiche" sein soll wie ein Stack

"gleich" bedeutet ja nur vom ergebnis her - nicht von der leistung

pumuckl

Man kann unter bestimmten Umständen die Tail Recursion (Funktionen wo der rekursive Aufruf der letzte ist) so in eine Iteration umwandeln, dass es effektiver ist als eine normale Rekursion. Das ist bei dir aber nicht der Fall, weil du erstens noch die Zuweisung nach dem rekursiven Aufruf hast und zweitens der rekursive Aufruf mehrfach vorkommt.

ProgrammierGeselle

Danke für die Beiträge,
der Begriff "Tail Recursion" hat mir weitergeholfen

^^probier mal das: http://www.geocities.com/permute_it/01example.html

volkard

ProgrammierGeselle schrieb:

Komischer Weise braucht die iterative Variante mehr Zeit, sollte die nicht schneller sein?

NÖ!
Wenn Du eine echte iterative Version gegen eine rekursive stelltst, ist meistens die iterarive schneller. Aber Du hast ja keine echte Iteration genehmt, sondern mit dem eigenen stack die Rekursion implementiert.
Und da kann man meistens manchmal oft davon ausgehen, daß die Jungs von Intel und AMD total viel Aufwand reinstecken, daß der Prozessorstack mit den Maschinenbefehlen CALL und PUSH und POP und LEAVE und so sauschnell ist, weil der wird ja für alle Funktionsaufrufe immer genehmt. Deswegen ist es meistens manchmal oft keine super Idee, die Rekursion vermittels eigenem Stack nachzubilden.

volkard schrieb:

Aber Du hast ja keine echte Iteration genehmt,

Was ist für dich eine "echte Iteration" sein?

Tyrdal

Eine die sich nicht auf Rekursion stützt.