Rekursion mit Ausgabe mehrerer Zahlen im Hauptprogramm

Luka_one

Hallo zusammen!
Der Titel umfasst mein Problem. Die meisten rekursiven Funktionen, die ich als Beispiel gesehen habe, lieferten zum schluss nur eine Zahl.
Meinetwegen die Fakultät von 5, die 6. Potenz, oder die 10. Fibonaccizahl.
Was ist nun aber, wenn im Hauptprogramm alle Zwischenschritte ausgeben werden sollen?
Also bei Fibaonacci 1 1 2 3 5 8 usw.
Mein Ansatz war, dass in einem Array zwischengespeichert werden soll, und dieses dann zum Schluss wieder mit return an das Hauptprogramm geliefert wird. Aber die Idee hat das Programm nicht zum laufen gebracht.
Da ich kein Beispiel dafür gefunden habe, frage ich hier mal nach, wie man so etwas bewerkstelligen kann.
bye,

c.rackwitz

fib(0) = 1
fib(1) = 1
fib(n) = fib(n-1) + fib(n-2)

for (i = 0; i < 1000; ++i)
    printf("%d", fib(i));

die rekursion kannst du optimieren mit "memoization".

Luka_one

Danke für die schnelle Antwort!
Obwohl ich jetzt keine Ahnung hab, was "memoization" ist.
Auch ne super Idee, mit der Ausgabe.
Habe nicht daran gedacht, dass ich jede einzelne Zahl rekursiv berechnen kann.
Frage: Könnte die Zahlenreihe auch im Hauptprogramm ausgegeben werden, wenn man nur einmal die rekursive Funktion geht?
Danke für die Lösung!

c.rackwitz

theoretisch geht das auch, aber dann am besten in verbindung mit memoization.

memoization:

#include <stdio.h>

#define CACHELEN 100

typedef unsigned long u32;

u32 facs[CACHELEN] = {0};

u32 fac(u32 n);

int main(void)
{
	facs[0] = facs[1] = 1; /* wichtig */
	fac(50);
	return 0;
}

u32 fac(u32 n)
{
	u32 res;

	if (n < CACHELEN && facs[n]) /* ergebnis schon gecacht */
		return facs[n];

	res = fac(n-1) + fac(n-2); /* berechnen, weil noch nicht im cache */

	printf("fac(%ld) = %ld\n", n, res); /* kann doppelt ausgeben, n > CACHELEN */

	if (n < CACHELEN) /* wenns in den cache passt, dort speichern */
		facs[n] = res;

	return res;
}

sinn: alles wird nur einmal berechnet und das ergebnis gecacht.

Luka_one

Danke für die super Antwort!
Und dann auch noch so schnell
Werde mich dann mal durch das Programm kämpfen.