[C] Drzewo wywołań w obliczaniu rekurencyjnym ciągu Fibonacciego

[Springfield]

Mam napisac funkcję wyswietlajaca takie drzewo wywołań:

Kod: Zaznacz cały

# Uzupełnij funkcję rekurencyjną o elementy, które pozwolą wypisać drzewo wywołań rekurencyjnych. Nie korzystamy ze zmiennych globalnych.

Głębokość(kropki), Działanie, l=liczba wywołań
0, Obliczam f(6)=f(5)+f(4),l=1
1., Obliczam f(5)=f(4)+f(3),l=2
2.., Obliczam f(4)=f(3)+f(2),l=3
3..., Obliczam f(3)=f(2)+f(1),l=4
4...., Obliczam f(2)=f(1)+f(0),l=5
5....., Zwracam f(1),l=6
5....., Zwracam f(0),l=7
4...., Zwracam f(1),l=8
3..., Obliczam f(2)=f(1)+f(0),l=9
4...., Zwracam f(1),l=10
4...., Zwracam f(0),l=11
2.., Obliczam f(3)=f(2)+f(1),l=12
3..., Obliczam f(2)=f(1)+f(0),l=13
4...., Zwracam f(1),l=14
4...., Zwracam f(0),l=15
3..., Zwracam f(1),l=16
1., Obliczam f(4)=f(3)+f(2),l=17
2.., Obliczam f(3)=f(2)+f(1),l=18
3..., Obliczam f(2)=f(1)+f(0),l=19
4...., Zwracam f(1),l=20
4...., Zwracam f(0),l=21
3..., Zwracam f(1),l=22
2.., Obliczam f(2)=f(1)+f(0),l=23
3..., Zwracam f(1),l=24
3..., Zwracam f(0),l=25
rFibonacci (6) = 8

Mam problem z licznikiem liczby wywołań i wyswietlaniem głebokości(kropki to wiadomo jak juz bedzie glebokosc to jakas pętla). Udało mi się napisac cos takiego:

Kod: Zaznacz cały

unsigned long long fib(int n){
unsigned long long wyraz;	
	if (n==1){
	printf("zwracam f(1)\n");
	return 1;
	}
	else if(n==0){
	printf("zwracam f(0)\n");
	return 0;
	}
printf("obliczam f(%d)=f(%d)+f(%d) \n", n, n-1, n-2);
wyraz=fib(n-1)+fib(n-2);


return wyraz;
}

[Ja_Szczur]

poczytaj o zmiennych statycznych

btw. po co tworzysz dodatkową zmienną wyraz? :>
nie lepiej od razu: return fib(n-1)+fib(n-2); ..?

[Springfield]

Dziękuję za pomoc.
Mam jeszcze kilka pytań:
1)Dla czego wyświetla mi wynik z tymi wcieciami przed niektórymi numerami poziomów? (zaczęło się tak dziac po dodaniu wyswietlania liczby pożądkowej.
2) Jak wyzerowac zmienna statyczną po zakonczeniu dzialania programu? tzn jak np wpisze n=6 to liczba pożądkowa po zakończeniu działania funkcji wynosi 25, jak podam kolejną liczbę n to zmienna statyczna ma juz wartośc 25 i od tej liczby zaczyna mi wypisywac liczby pożądkowe.
ps. zmienna wyraz utworzylem dla więkrzej przejrzystości.

Kod: Zaznacz cały

0, obliczam f(6)=f(5)+f(4), l=1
 1., obliczam f(5)=f(4)+f(3), l=2
 2.., obliczam f(4)=f(3)+f(2), l=3
 3..., obliczam f(3)=f(2)+f(1), l=4
 4...., obliczam f(2)=f(1)+f(0), l=5
 5....., zwracam f(1), l=6
5....., zwracam f(0), l=7
4...., zwracam f(1), l=8
3..., obliczam f(2)=f(1)+f(0), l=9
 4...., zwracam f(1), l=10
4...., zwracam f(0), l=11
2.., obliczam f(3)=f(2)+f(1), l=12
 3..., obliczam f(2)=f(1)+f(0), l=13
 4...., zwracam f(1), l=14
4...., zwracam f(0), l=15
3..., zwracam f(1), l=16
1., obliczam f(4)=f(3)+f(2), l=17
 2.., obliczam f(3)=f(2)+f(1), l=18
 3..., obliczam f(2)=f(1)+f(0), l=19
 4...., zwracam f(1), l=20
4...., zwracam f(0), l=21
3..., zwracam f(1), l=22
2.., obliczam f(2)=f(1)+f(0), l=23
 3..., zwracam f(1), l=24
3..., zwracam f(0), l=25

Kod: Zaznacz cały

unsigned long long fib(int n, int glebokosc_tmp){
unsigned long long wyraz;	
static int licznik=0;
int i;
licznik++;
glebokosc_tmp++;
printf("%d", glebokosc_tmp);	
for (i=0;i<glebokosc_tmp;i++)
printf(".");

	if (n==1){
	printf(", zwracam f(1), l=%d\n", licznik);
	return 1;
	}
	else if(n==0){
	printf(", zwracam f(0), l=%d\n", licznik);
	return 0;
	}
printf(", obliczam f(%d)=f(%d)+f(%d), l=%d\n ", n, n-1, n-2, licznik);
wyraz=fib(n-1, glebokosc_tmp)+fib(n-2, glebokosc_tmp);


return wyraz;
}

[Ja_Szczur]

popraw błędy: "porządkowa", "dlaczego" ;-)

1)Dla czego wyświetla mi wynik z tymi wcieciami przed niektórymi numerami poziomów?

printf(", obliczam f(%d)=f(%d)+f(%d), l=%d\n ", n, n-1, n-2, licznik); // "\n " <-

2) Jak wyzerowac zmienna statyczną po zakonczeniu dzialania programu? tzn jak np wpisze n=6 to liczba pożądkowa po zakończeniu działania funkcji wynosi 25, jak podam kolejną liczbę n to zmienna statyczna ma juz wartośc 25 i od tej liczby zaczyna mi wypisywac liczby pożądkowe.

hm, najprościej zrobić trzeci, domyślny argument funkcji:

Kod: Zaznacz cały

unsigned long long fib(int n, int glebokosc, bool start = 0)
{
	int i;
	static int licznik;

	if (start) {
		licznik = 0;
	}
// ...
	return fib(n-1, glebokosc)+fib(n-2, glebokosc);
}

int main(void)
{
	fib(3, 0, 1);
	printf("\n----------------\n");
	fib(5, 0, 1);
	printf("\n----------------\n");
	fib(10, 0, 1);
	
	return 0;
}