Fragen zur Rekursion in C!

bandchef

Hi Leute!

Ich hab einige Fragen zur Rekursion in C. Wenn man z.B. die Fibonacci-Zahlen durch Rekursion berechnen möchte, dann macht man ja das mit folgender Formel:

Fib(n) = Fib(n-2)+Fib(n-1), mit Fib(0) = 0 und Fib(1) = 1

(Rekursion für die Fibonacci-Zahlen ist nicht so vorteilhaft; ich weiß.)

Ich denke aber, dass es als Beispiel für meine Fragen recht gut geeignet ist. Nun meine Frage:

Hier ist ein Link mit einer Grafik die mein bisheriges Wissen über Rekursion darstellt. Link: http://yfrog.com/5b97245841j

Wenn ich nun meine Funktion Fib mit der Zahl 3 aufrufe wird quasi die Funktion Fib(3-2)=1 aufgerufen/berechnet dann wird wieder die Funktion Fib(1-2)=-1 aufgerufen/berechnet. Mit dem anderen Teil der Berechnung wird Fib(3-1)=2 aufgerufen/berechnet dann wird Fib(2-1)=1 aufgerufen/berechnet und dann noch Fib(1-1)=1 aufgerufen/berechnet. Und das würde ja jetzt so weiter gehen. Man will aber doch dass die Rekursion irgendwann auch mal wieder abgebaut wird. Wie geht das dann?

HighLigerBiMBam

Mit einer Abbruchbedingung z.B. Anzahl der Rekursionen durch statische Variablen, wenn Fehlerwert kleiner einem Grenzwert ist, etc. sei kreativ.

In der Funktion mußt du natürlich testen ob die übergebene Zahl 0 oder 1 ist und dann 0 oder 1 zurückgeben. Wenn nicht rufst du halt nochmal fib() auf.
Die Zahl kann also nicht negativ werden.

Die Bedingungen von Herrn Fibonacci bezüglich 0 und 1 haben also ihren Sinn.

fib(3)
       /     \
fib(1)=1     fib(2)
            /     \  
        fib(0)=0   fib(1)=1

bandchef

Danke für deine Antwort.

Ich soll nun durch Rekursive Programmierung mit dem Grundsatz "Teile und Herrsche" eine Min-Max-Suche durchführen. Ich darf ein short Array mit fest definierter Länge selbst mit unterschiedlichen Zahlen belegen. Aus diesem Array soll ich dann den kleinsten und größten Wert herausfinden. Den Min-Wert und den Max-Wert soll ich dann in einem Long ausgeben. In diesem Long soll in den oberen 16Bit der Max-Wert und in den unteren 16Bit soll der Min-Wert stehen. Ich hab hier mal angefangen zu programmieren. Mein code sieht so aus:

#include<iostream>
using namespace std;

//minmax
void minmax(short array[6])
{
	short teil1[3], teil2[3];

	cout << "Teil1: ";

	for(int i=0; i<3; i=i+1)
	{
		teil1[i] = array[i];
		cout << teil1[i];
	}

	cout << endl << "Teil2: ";

	for(int j=3; j<6; j=j+1)
	{
		teil2[j-3] = array[j];
		cout << teil2[j-3];
	}
}

int main()
{
    short array[6] = {4,3,7,2,1,6};

    minmax(array);

system("pause");
return 0;
}

Ich hab hier nun aber das Problem dass ich nicht weiß wie bzw. wo ich hier nun die Funktion innerhalb meiner Funktion wieder aufrufen soll. Vor allem: Wenn ich nun die Funktion wieder aufrufe, dann muss ich mir ja eigentlich das Array Teil1 bzw. Teil2 wieder in zwei Teilarrays aufteilen, was aber doch mit den beiden forschleifen nicht gehen sollte, weil der Laufindex nicht mehr stimmt... Ich weiß jetzt quasi nicht wie ich meinen Code dafür "flexibel" genug mache.

Könnt ihr mir draufhelfen?

Deine Funktion minmax sollte zumindest mal diesen long Wert zurückgeben. Zudem solltest du die Arraylänge übergeben.

long minmax(short array[], int len)
{
  return (max verknüpft_mit min);
}

Dann kannst du das Array schön teilen und die Länge mitgeben.
Wenn nur noch 2 Werte in dem Array sind sollte min max zu finden ganz leicht sein.

PS: Dein Programm ist aber C++

bandchef

Ich programmiere eigentlich C. Laut unserem Prof. sollen (!) wir aber iostream wegen der einfacheren ein und ausgabe verwenden.

Dann kannst du das Array schön teilen und die Länge mitgeben.

Was verstehst du unter schön teilen? Hab ich das array mit den beiden for-Schleifen schon schön geteilet? Oder wie hast du das gemeint?

Hier steht auch eine Menge zu Rekursion: http://www.mikrocontroller.net/topic/200725

... aber das weißt du ja schon.

long minmax(short min,short max,short *arr,size_t i){
  short s = arr[i];
  if(min > s)
    min = s;
  if(max < s)
    max = s;
  return i ? minmax(min,max,arr,i-1) : ((max<<16) | min);
}

struct ret{
  union{
    struct{
      short min;
      short max;
    }mm;
    long ret;
  };
};
struct ret rr;
short array[6] = {4,3,7,2,1,6};
rr.ret = minmax(SHRT_MAX,SHRT_MIN,array,5);

evtl. geht das so in die richtung?

wxSkip

Pseudocode:

Funktion minmax(Pointer auf Array, Länge des Arrays)
{
    Wenn die Länge zwei ist, gib kleineres und größeres verknüpft zurück
    Wenn die Länge eins ist, gib den einen short mit sich selbst verknüpft zurück
    Sonst
        Rufe die Funktion minmax für zwei fast gleich große Teile des Arrays auf (Größenunterschied 0 oder 1)
        Nimm die beiden max-Teile der Ergebnisse und schreibe das größere davon in das Gesamtergebnis der Funktion
        Mache das gleiche für die Min-Teile
        Gib das Gesamtergebnis zurück
}