Matematyka dyskretna/Rekurencja
Z Wikibooks, biblioteki wolnych podręczników.
Spis treści |
[edytuj] Wstęp
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.
[edytuj] Silnia
Jak wiadomo 0!=1 i 1!=1 dodatkowo (n+1)!=n!*(n+1) możemy to zapisać"
[edytuj] program silnia
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)
[edytuj] Ciąg Fibonacciego
Kolejnym przykłdem zastosowania rekurencji jest ciąg Fibonacciego.
ciag ten definiujemy 
Kolejne wartości ciagu Fibonacciego to
0,1,1,2,3,5,8,13,21,34,55...
Ciąg Fibonacciego można też zdefiniować 
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).
[edytuj] Program Fibonacci
Program Fibonacci;
var
n,i:byte;
poprzedni, przedpoprzedni, przedprzedpoprzedni: longint;
begin
write ('ktory wyraz mam obliczyc:');
readln(n);
if=0
//Dokończyć
[edytuj] Wieża z Hanoi
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.
