Wikipedysta:Yusek/Matematyka dyskretna/Rekurencja

Wstęp[edytuj]

Rekurencja jest to zdolność funkcji, procedury bądz programu do odwoływania się do samej siebie. Rekurencja jest często wolniejsza od metody iteracyjnej jednakże do wielu problemów takich jak na przykład oblicznie silnii rekurencja jest niemalże idealna. I to właśnie na przykładzie silnii wyjaśnie jak działa rekurencja.

Silnia[edytuj]

Jak wiadomo 0!=1 i 1!=1 dodatkowo (n+1)!=n!*(n+1) możemy to zapisać"
${\begin{cases}0!=1\\1!=1\\n!=(n-1)!*n\end{cases}}$

program silnia[edytuj]

program silnia;
var
n,i : Byte;
Silnia :longint;
begin
silnia:=1;
wirte ('Podaj liczbe');
readln (n);
for i=1 to n do
silnia:=silnia*i;
writeln (n,'!='silnia)
readln;
end.

UWAGA! Silnia rośnie bardzo szybko więc argumenty powinny być stosunkowo niewielkie (w przypadku longint 14)

Ciąg Fibonacciego[edytuj]

Kolejnym przykłdem zastosowania rekurencji jest ciąg Fibonacciego.
ciag ten definiujemy ${\begin{cases}F(0)=0\\F(1)=1\\F(n)=F(n-1)+F(n-2)\end{cases}}$
Kolejne wartości ciagu Fibonacciego to
0,1,1,2,3,5,8,13,21,34,55...

Ciąg Fibonacciego można też zdefiniować $F(n)={\frac {{\frac {1+{\sqrt {5}}}{2}}^{n}-{\frac {1-{\sqrt {5}}}{2}}^{n}}{\sqrt {5}}}$
Ciąg ten zdefiniowany iteracyjnie pokazuje nam że ciąg Fibonacciego rośnie wykładniczo czy bardzo szybko (jednakże nie aż tak szybko jak silnia).

Program Fibonacci[edytuj]

Program Fibonacci;
var
n,i:byte;
poprzedni, przedpoprzedni, przedprzedpoprzedni: longint;
begin
write ('ktory wyraz mam obliczyc:');
readln(n);
if=0

//Dokończyć

Wieża z Hanoi[edytuj]

Klasyką zadań rekurencyjnych jest problem wieży z Hanoi. W wieży z Hanoi należy przenieść krążki z jednego palika na inny przy pomocy trzeciego. Możemy przenosić krążki pojedyńczo, dodatkowo możemy położyć tylko mniejszy krążek na większy (nie koniecznie bezpośrednio większy). W przypadku przenoszenia 1 krążka nie ma problemu bo poprostu przekładamy z jednego palika na drugi. W przypadku 2 krążków też nie ma większego problemu. Schody zaczynają się kiedy mamy powyżej 2 krążków. (Klasyczny przykład to 3 krążki) jednakże za pomocą rekurencji możemy sprowadzić zadanie z n krążków do n-1 i tak dalej aż dojdziemy do 2.