background image

Podstawy programowania 

wykład 12 

Dr inż. Jakub Bauman 

jakub.bauman@gmail.com 

background image

Rekurencja 

Dr inż. Jakub Bauman 

jakub.bauman@gmail.com 

background image

Rekurencja 

Często stajemy przed problemem, który 
łatwo byłoby rozwiązać, gdybyśmy 
mieli w ręku odpowiedź dla mniejszych 
danych. 

background image

Silnia 

Definicja rekurencyjna 

definicja nierekurencyjna  

background image

int silnia(int n){ 
   if (n==0){  
 

return 1;  

   } 
   else { 
 

return n*

silnia(n-1)

; 

   } 
 } 

Silnia – funkcja rekurencyjna 

background image

Postać rekurencyjna 

 i nierekurencyjna 

Ciąg T0, T1… 

Za pomocą indukcji matematycznej możemy 
udowodnić że: 

background image

Istnieją problemy, dla których nie znamy postaci 
nierekurencyjnej 

lub nie możemy w prosty sposób jej zastosować 

Problemy 

background image

Ciąg Fibonacciego 

Definicja rekurencyjna 

Wzór Bineta 

background image

int Fibo(int n) { 
 if (n <= 1) { 
   Fibo = n;  
 } 
 else { 
  Fibo = 

Fibo(n-2) 

+ 

Fibo(n-1)

; 

 } 
} 
 

Fibo – algorytm rekurencyjny 

background image

Fibo(4) = Fibo(2) + Fibo(3) 

Program obliczy: Fibo(2) 

I będzie obliczał Fibo(3) = Fibo(1) + Fibo(2) 

Ponieważ wartość Fibo(2) nie jest znana musi obliczyć 
ją obliczyć jeszcze raz 

Problem 

background image

Problem wielokrotnego obliczania tych samych liczb 
należy zastosować tablicę zapamiętującą obliczone 
już wartości 
 

Przykład oprogramowania takiej funkcji 

Problem 

background image

Wieże Hanoi 

background image

Pytania 

 

Dyskusja 

background image

Dziękuję za uwagę! 

Dr inż. Jakub Bauman 

jakub.bauman@gmail.com