Rekurencja

Dzisiaj zajmujemy się rekursją tj. funkcjami rekurencyjnymi i nierekurencyjnymi ich wersjami. Funkcje rekurencyjne to takie które wewnątrz swojej definicji, mają odwołanie do siebie samej. Przykład poniżej opisuje jak rekurancyjnie można sumować n kolejnych liczb:


int suma_kolejnych (int n){
if (n==0) return 0;
else return n + suma_kolejnych(n-1);
}
W drugiej części zajęć zamieszczam zadania które sprowadzają się do napiania kilku funkcji i użycia ich jednej wewnątrz drugiej (i tak dalej).

Zad 1 Silnia

Napisz rekurencyjną funkcję obliczająca silnię.

Zad 2 Ciąg Fibonacciego

Napisz funkcję rekurencyjną Fibonacci, która
przyjmuje wartość naturalną n większe od 1 i oblicza
wartość n-tego wyrazu ciągu Fibonacciego, który
zdefiniowany jest tak: dla n=1 wynosi 1, dla n=2 tez 1
a dla n większych od 2 jest równy sumie jego wartości
dla n-1 i n-2. Następnie napisz program, który wypisuje pierwszych 9 wyrazów tego ciągu.

wpisz n: 9
1 1 2 3 5 8 13 21 34

Zad 3 Symbol Newtona

Napisz rekurencyjną funkcję o nazwie symbol która oblicza symbol Newtona "n nad k". Skorzystaj z faktu że
(n nad k) = (n-1 nad k) + (n-1 nad k-1)
Sprawdź jej działanie pisząc krótki program który wypisuje wszystkie symbole Newtona dla n=5. Przyjmij że n nad 0 to 1

Dla n = 5 symbole Newtona to:
1 5 10 10 5 1

Zad 4 Prawdopodobieństwo k sukcesów w n próbach

Napisz funkcję o nazwie Ksukcesow, która oblicza prawdopodobieństwo k sukcesów w n próbach rzutu fałszywą monetą, dla której prawdopodobieństwo wypadnięcia orła wynosi p a reszki 1-p , gdzie p jest liczbą rzeczywistą z przedziału [0,1].
Funkcja powinna mieć 3 argumenty: n, k, i p .
Uwaga1: przy podawaniu z klawiatury danych typu double należy używać kropki np. 0.5 w przeciwnym wypadku otrzymamy nieprawidłowe wyniki.
Uwaga2: skorzystaj w tym celu z funkcji z zad 1

Podaj n: 4
Podaj k: 1
Podaj p: 0.5
Prawdopodobieństwo 1 sukcesow w 4 probach wynosi 0.25

Zad 5 K lub mniej sukcesów

Napisz funkcję o nazwie Cumulative która oblicza prawdopodobieństwo zdarzenia wypadnięcia k lub mniej orłów w n niezależnych próbach o rozkładzie p, 1-p.

Podaj n: 4
Podaj k: 1
Podaj p: 0.5
Prawdopodobieństwo 1 lub mniej sukcesow w 4 probach 
wynosi: 0.3125

Zad 6 Nierekurencyjne obliczanie symbolu Newtona za pomocą tablic

Napisz nierekurencyjną funkcję która oblicza symbol Newtona w tym celu zadeklaruj (globalną zmieną) tablicę tab 2-wymiarową 10 na 10 typu int i wypełnij jej zerową kolumnę oraz diagonalę 1-kami.
W kolejnych wierszach tablicy pomiędzy kolumną a diagonalą wypełnij ją stosując wzór:
tab[i][j] = tab[i-1][j-1] + tab[i-1][j]
gdzie i przebiega wiersze, a j kolumny (jest to zależność rekurencyjna podaną w zadaniu 1).

UWAGA: celem tego ćwiczenia nie są wskaźniki, dlatego sugeruję zmienną globalną, ale jeśli wystarczy Państwu czasu, możecie zmienić funkcję na taką która pobiera tylko adres zerowego elementu tablicy i dzięki temu ją modyfikuje. Na tą chwilę ważne jest aby Państwo umieli to zadanie rozwiązać ze zmienną globalną (ustalamy deklarację int tab[10][10] zaraz po include, przed definicją funkcji).
Następnie napisz program, który wczytuje n i k i wypisje (n nad k): (n nad k) to tab[n][k]