4. Rekursion

Rekursion

  • ?

    Hier gings auch um Rekursion.
    http://www.fun-soft.de/showtopic.php?threadid=18198

    0
  • C

    von tail call optimization (edit: und stack folding, kennt keiner) habt ihr blub programmierer wohl noch nichts gehoert, wa?

    nie vergessen:

    http://c2.com/cgi/wiki?ExtraLegsOntoAdog schrieb:

    An octopus made by...
    CeeLanguage

    • ...isn't really an octopus at all. Just a dog, although it's a racing greyhound with almost no brain

    CeePlusPlus

    • ...made by nailing extra legs to a dog

    • you now have an 8-legged dog, and the process was rather painful.

    hier doch ein wenig darstellender code (entstand, als ich einem freund verkettete listen nahebringen wollte)

    #include <stdio.h>
#include <stdlib.h>

typedef struct _Node
{
	int value;
	struct _Node *next;
} Node;

Node *newnode(int value, Node *next)
{
	Node *result = malloc(sizeof(Node));

	result->value = value;
	result->next = next;

	return result;
}

void shownode(Node *node)
{
	printf("%p: %i, %p\n", node, node->value, node->next);
}

void delnode(Node *node)
{
	printf("loesche ");
	shownode(node);

	free(node);
}

void showlist(Node *list)
{
	while (list)
	{
		shownode(list);
		list = list->next;
	}
}

void showlist_r(Node *list)
{
	if (list)
	{
		shownode(list);
		showlist_r(list->next);
	}
}

void printlist(Node *s)
{
	if (s)
	{
		printf("%d ", s->value);
		printlist(s->next);
	}
	else
		printf("\n");
}

int listlen(Node *list)
{
	int result = 0;

	while(list)
	{
		result++;
		list = list->next;
	}

	return result;
}

int listlen_r(Node *list)
{
    if (!list)
	    return 0;
    else
	    return 1 + listlen_r(list->next);
}

void clearlist(Node *list)
{
	Node *tmpnode;

	while(list)
	{
		tmpnode = list->next;
		delnode(list);
		list = tmpnode;
	}
}

void clearlist_r(Node *list)
{
	if (list)
	{
		clearlist_r(list->next);
		delnode(list);
	}
}

Node *constructlist_r(int *s, int n)
{
	if (n)
		return newnode(*s, constructlist_r(s+1, n-1));
	else
		return NULL;
}

Node *constructlist_ir(int *s, int n)
{
	Node *result = NULL;

	while (n--)
		result = newnode(s[n], result);

	return result;
}

Node *constructlist(int *s, int n)
{
	Node *result = NULL, *end = NULL, *tmp;
	int i;

	for (i = 0; i < n; i++)
	{
		tmp = newnode(s[i], NULL);

		if (!result)
			result = tmp;

		if (end)
			end->next = tmp;

		end = tmp;
	}

	return result;
}

int main(void)
{
	Node *a = NULL, *b = NULL;
	int i;

	int foo[10] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};

	for (i = 0; i < 10; i++)
		a = newnode(i, a);

	printf("listenlaenge: %d\n", listlen(a));

	b = constructlist(foo, 10);

	printlist(a);
	printlist(b);

	clearlist(a);
	clearlist(b);

	return 0;
}
    0
  • P

    c.rackwitz schrieb:

    http://c2.com/cgi/wiki?ExtraLegsOntoAdog

    😃 👍
    c2.com/cgi/wiki ist sowieso die beste site im ganzen internet
    🙂

    0
  • S

    Die Frage war nicht ob Rekursion der uber-burner ist und ob Gott selbst erst die Rekursion und dann den Menschen erschaffen hat und ob Iteration der Teufel in Person ist, sondern einfach darum wie man eine Rekursion schreibt.

    Die Frage ist durchaus valid, liebe Leute. Rekursion verlangt ein anderes denken als iteration. Ich kann jedem deppen Iteration erklaeren. Rekursion dagegen verlangt etwas anderes denken, denken dass wir im Alltag nicht haben/brauchen.

    c.rackwitz, es wuerde mich freuen wenn du deine Wortwahl etwas verbessern koenntest. Danke.

    @long long double:
    das ist irrelevant. Viel interessanter ist Rekursion in einem rekursiven umfeld. Sprich: wenn wir so oder so einen Stack brauchen.

    Gutes Beispiel ist QuickSort - sollte jedem ein Begriff sein. Standardmaessig loest man es ueber rekursion -> bietet sich einfach an: man quicksortet die ermittelte Teilmenge. Das kann man aber auch iterativ machen. Allerdings hat man dann nicht den Maschinen Stack, sondern muss sich einen eigenen Stack bauen. Klappt genauso.

    Das sind dann vielleicht die relevanteren Faelle wo man Rekursion sinnvoll einsetzen kann: ein simpler Schleifen Ersatz klappt es nur, wenn der Compiler das auch optimieren kann - was in C eher selten ist. In Funktionalen Sprachen dagegen eher der Standard.

    0
  • P

    Shade Of Mine schrieb:

    Viel interessanter ist Rekursion in einem rekursiven umfeld. Sprich: wenn wir so oder so einen Stack brauchen.

    --> http://www.olympus.net/personal/7seas/recurse.html
    😉

    0
  • B

    Schöne Beispiele für Rekursion, die über Trivialkram wie die Fakultät oder Fibonacci-Zahlen hinausgehen:
    * Anzahl der Knoten eines Baumes
    * Türme von Hanoi
    * Alle Permutationen einer Menge

    BTW stimmt es eigentlich nicht so ganz, dass Iteration leichter zu verstehen ist. In schwierigeren Fällen wird die Betrachtung deutlich erleichtert, wenn man sich über Dinge wie Invarianten Gedanken macht.

    0
  • ?

    Hmmm, ich habe den Fragesteller ehrlich gesagt auch eher so verstanden, dass er schon eine Lösung für ein Problem hat, aber jetzt eine rekursive Lösung sucht.
    Und die Frage ist dann imho doch, ob es sinnvoll ist umbedingt nach einer rekursiven Lösung zu suchen.

    Dieses "basteln" hat mich glaube ich ein wenig verwirrt. 😉

    Bei Quicksort oder Ähnlichem sollte es ja eigentlich auch nicht so schwer sein, dies rekursiv zu implementieren, weil es ja eben auch rekursiv definiert ist.

    Irgendwie habe ich aber auch das Gefühl, dass dieser Thread langsam außer Kontrolle gerät und niemand mehr wirklich auf die ürsprüngliche Frage eingeht.
    Deshalb halte ich mich auch ab jetzt lieber aus diesem Thread heraus, und warte, bis der Fragensteller eventuell doch noch genauere Informationen über das gibt, was er genau wissen will, oder bis er einen neuen Thread aufmacht. 😉

    0
  • ?

    Vielen Dank für die zahlreichen Ratschläge,
    damit kann ich auf jeden Fall was anfangen 👍

    Muss Rekursion für ne Klausur können, desshalb wollte ich nich auf ein konkretes Beispiel eingehen!

    Kann sich kurz jeman diese kleine Übung anschauen und mir
    eventuell sagen, warum nur kauderwelsch bei rauskommt?

    Ich denke irgendwas beim Aufruf stimmt nicht, aber was??
    Es sollen Werte übergeben (z.B. 2314) werden und diese zusammen mit der
    Grösse des neuen "Vektors" (So nennt mein Prof Zeichenketten)
    vollständig angezeigt werden, also in diesem Fall 2221111 und die neue Anzahl 7
    Bitte meinen Anfängerstatus berücksichtigen 🙂

    ~#include <stdio.h>
    #include <stdlib.h>
    #define ANZAHL 20

    int modifiziert ( int folgeKurz[], int paarAnz, int *laenge, int folgeLang[]){
    int z1,z2,i;

    *laenge=1;
    i=1;

    for(z1=0;z1<=paarAnz*2-1;z1=z1+2){

    for (z2=0;z2<=folgeKurz[z1+1];z2++){

    folgeLang[i]=folgeKurz[z1];

    i++;
    *laenge=i-1;
    }
    }
    }
    int main(){
    int i1,i2;
    int kurzFolge[100],langFolge[100];
    int anzPaare,neuGroesse,ergebniss=1;

    for (i1=0; i1<=ANZAHL-1;i1++){

    printf("Bitte Anzahl der Paare eingeben: ");
    scanf("%d", &anzPaare);
    printf("Bitte Folge-Paare eingeben: ");
    scanf("%d",&kurzFolge[i1]);

    ergebniss=modifiziert(kurzFolge,anzPaare,&neuGroesse,langFolge);

    for(i2=0;i2<=ANZAHL-1;i2++){

    printf("\nModifizierte Folge: %d Sie ist %d Stellen lang", langFolge,neuGroesse);

    printf("\n\n");system("Pause");
    return 0;
    }
    }
    }~

    0
  • ?

    Wenn du die C/C++ Tags benutzst, dann sieht das so aus:

    #include <stdio.h>
#include <stdlib.h>
#define ANZAHL 20

int modifiziert ( int folgeKurz[], int paarAnz, int *laenge, int folgeLang[]){
int z1,z2,i;

*laenge=1;
i=1;

for(z1=0;z1<=paarAnz*2-1;z1=z1+2){

for (z2=0;z2<=folgeKurz[z1+1];z2++){

folgeLang[i]=folgeKurz[z1];

i++;
*laenge=i-1;
}
}
}
int main(){
int i1,i2;
int kurzFolge[100],langFolge[100];
int anzPaare,neuGroesse,ergebniss=1;

for (i1=0; i1<=ANZAHL-1;i1++){

printf("Bitte Anzahl der Paare eingeben: ");
scanf("%d", &anzPaare);
printf("Bitte Folge-Paare eingeben: ");
scanf("%d",&kurzFolge[i1]);

ergebniss=modifiziert(kurzFolge,anzPaare,&neuGroesse,langFolge);

for(i2=0;i2<=ANZAHL-1;i2++){

printf("\nModifizierte Folge: %d Sie ist %d Stellen lang", langFolge,neuGroesse);

printf("\n\n");system("Pause");
return 0;
}
}
}

    Wenn du es dann noch halbwegs vernünftig formatierst, dann sieht das so aus:

    #include <stdio.h>
#include <stdlib.h>
#define ANZAHL 20

int modifiziert ( int folgeKurz[], int paarAnz, int *laenge, int folgeLang[])
{
	int z1,z2,i;
	*laenge=1;
	i=1;

	for(z1=0;z1<=paarAnz*2-1;z1=z1+2)
	{

		for (z2=0;z2<=folgeKurz[z1+1];z2++)
		{
			folgeLang[i]=folgeKurz[z1];
			i++;
			*laenge=i-1;
		}
	}
}

int main()
{
	int i1,i2;
	int kurzFolge[100],langFolge[100];
	int anzPaare,neuGroesse,ergebniss=1;

	for (i1=0; i1<=ANZAHL-1;i1++)
	{

		printf("Bitte Anzahl der Paare eingeben: ");
		scanf("%d", &anzPaare);
		printf("Bitte Folge-Paare eingeben: ");
		scanf("%d",&kurzFolge[i1]);

		ergebniss=modifiziert(kurzFolge,anzPaare,&neuGroesse,langFolge);

		for(i2=0;i2<=ANZAHL-1;i2++)
		{
			printf("\nModifizierte Folge: %d Sie ist %d Stellen lang", langFolge,neuGroesse);
			printf("\n\n");system("Pause");
			return 0;
		}
	}
}
    0
  • S

    Bashar schrieb:

    BTW stimmt es eigentlich nicht so ganz, dass Iteration leichter zu verstehen ist. In schwierigeren Fällen wird die Betrachtung deutlich erleichtert, wenn man sich über Dinge wie Invarianten Gedanken macht.

    Ich bin jetzt nicht von einer konkreten Loesung ausgegangen, sondern von einer abstrakten Situation wo man Iteration <-> Rekursion erklaeren sollte.

    Iteration ist leicht zu erklaeren:
    du stehst in der frueh auf, gehst zaehne putzen, dann gehst du kaffee kochen und duschst dann, dann trinkst du den kaffe, dann ziehst du dich an

    und das alles jeden morgen. kann man sehr leicht nachvollziehen.

    bei bestimmten problemen bietet sich natuerlich oft eine rekursive oder iterative loesung allein aus der aufgabenstellung heraus an. aber wenn man rekursion nicht verstanden hat, dann ist das nicht so leicht zu sehen.

    0
Anmelden zum Antworten