Wstęp
do programowania
Wykład 6  rekurencja
Zmienne globalne i lokalne
Można zdefiniować pewne zmienne,
które będą widoczne we wszystkich
funkcjach danego programu  sÄ… to tzw
zmienne globalne
Wewnątrz funkcji można definiować
zmienne, które są zmiennymi lokalnymi
tej funkcji
Nazwa zadeklarowana na zewnÄ…trz wszystkich funkcji
ma zasięg globalny, czyli jest dostępna wewnątrz
wszystkich funkcji umieszczonych w danym pliku
wðNazwa jest widziana dopiero poniżej linii w której zostaÅ‚a
zadeklarowana
Zmienna lokalna danej funkcji jest widoczna tylko w
tej funkcji w której została zadeklarowana
Nie można zatem w jednej funkcji odwołać się do
zmiennej lokalnej innej funkcji...
Dwie funkcje mogą mieć zmienne lokalne o takich
samych nazwach
Nazwy zmiennych lokalnych i globalnych mogą być
jednakowe (zmienne lokalne przysłaniają zmienne
globalne)
" Jeśli w obrębie funkcji definiujemy jakieś zmienne,
to są one zazwyczaj pamiętane na tzw. stosie (czyli
w obszarze  podręcznym ).
Zmienne globalne są pamiętane w  normalnym
obszarze pamięci
 Normalny obszar pamięci przed uruchomieniem
programu jest zerowany. Niezainicjalizowana zmienna
globalna ma zatem na początku wartość 0 (odpowiednią
dla danego typu)
Zmienne podręczne nie są zerowane przy  powoływaniu
do życia . Mają wartość losową
Po zakończeniu bloku, w którym została powołana do życia
zmienna lokalna, przestaje ona istnieć.
" Przy ponownym wejściu do danego bloku  np. ponownym
wywołaniu tej samej funkcji  zmienna jest powołana do
życia po raz kolejny
" oczywiście przerwanie wykonywania jednej funkcji przez
wywołanie innej nie powoduje zlikwidowania zmiennych
pierwszej funkcji znajdujÄ…cych siÄ™ na stosie
program zmienne_globalne1;
{$APPTYPE CONSOLE} {$O-,Q+,R+}
uses SysUtils;
var a,zm_globalna :integer;
Function efekt_ub:integer;
Var a,zm_lok :Integer;
Begin
a:=2; writeln('a=' ,a);
zm_globalna:=5;
zm_lok:=1;
result:=zm_globalna;
end;
var b:byte;
begin
zm_globalna:=1;
a:=10;
writeln(efekt_ub);
writeln(zm_globalna, 'a= ',a ); //5
zm_globalna:=8;
writeln(efekt_ub);
writeln(zm_globalna ); //5
readln;
END.
program z1;
{$APPTYPE CONSOLE} {$O-,Q+,R+}
uses SysUtils;
var x :integer;
function zad1(a:integer; var b:integer):integer;
function wew1(c,d :integer):integer;
begin
d:=c+d;
wew1:=d+x; //Result:=d+x;
end;
begin
a:=a+b;
b:=a+b;
Result:=wew1(a,b); //zad1:=wew1(a,b);
end;
BEGIN
x:=2;
writeln(zad1(x,x)); //z=16 x=6
writeln(zad1(x,x)); //z=48
writeln(x); readln; //x=18
END.
Funkcje rekurencyjne
Rekurencja polega na tym że funkcja może
wywoływać samą siebie.
vðMoże to robić każda funkcja, tyle że jeÅ›li nie ma w niej
warunku zatrzymującego rekurencję, to funkcja będzie się
wywoływała się w nieskończoność, tzn. aż do wyczerpania
pamięci
vðGdy funkcja rekurencyjna wywoÅ‚uje samÄ… siebie, na
stosie są już zmienne lokalne będące własnością
pierwszego wywołania tej funkcji.
vðKolejne jej wywoÅ‚anie umieszcza na stosie swoje wÅ‚asne
zmienne lokalne
Procedura rekurencja
Program procedura_rek;
{$APPTYPE CONSOLE} {$O-,Q+,R+}
uses SysUtils;
var k : integer;
procedure inkrementacja ( x : integer);
begin
x:= x+1;
if x < 4 then inkrementacja(x)
else writeln(' Koniec wywoływania rekursyjnego dla x = ',x);
writeln('Jestem ostatnim poleceniem na poziomie ',x);
end;
begin
k:=0;
inkrementacja (k);
Readln;
end.
__________________________________________________________
Funkcje rekurencyjne
program silnia_rekurencyjna;
{$APPTYPE CONSOLE} {$O-,Q+,R+}
uses SysUtils;
function Rsilnia(liczba:integer):Cardinal;
begin
if liczba=0 then Rsilnia:=1
else Rsilnia:=liczba*Rsilnia(liczba-1)
end;
Var n: byte;
Begin
writeln('Podan n');
readln(n);
writeln (' n! = ', Rsilnia(n)); // writeln (' 4! =  , Rsilnia(4));
Readln;
end.
program NWPnierekur;
Funkcje rekurencyjne
{$APPTYPE CONSOLE}
uses SysUtils;
function NWP(a, b :cardinal) :cardinal;
program NWPrekur;
var
{$APPTYPE CONSOLE}
r :cardinal;
uses SysUtils;
begin
while b <> 0 do
function NWP(a, b :cardinal) :cardinal;
begin
begin
r := a mod b;
if b = 0 then
a := b;
Result := a
b := r;
else
end;
Result := NWP(b, a mod b);
Result := a;
end;
end;
begin
begin
writeln(NWP(18,24));
writeln(NWP(18,24));
readln;
readln;
end.
end.
program FibNieRekur;
Rekurencja
{$APPTYPE CONSOLE} {$O-,Q+,R+}
uses SysUtils;
program FibRekur;
function Fib(k :cardinal) :cardinal;
{$APPTYPE CONSOLE} {$O-,Q+,R+}
Var i, F_k_1, F_k_2 :cardinal;
begin
Uses SysUtils;
Result := k;
// F_0=0 F_1=1 F_k = F_k-1+F_k-2
if k > 1 then begin
function Fib(k :cardinal) :cardinal;
F_k_1 := 1; F_k_2 := 0;
begin
for i := 2 to k do
if k <= 1 then
begin
Result := k
Result := F_k_1 + F_k_2;
else
F_k_2 := F_k_1;
Result := Fib(k-1)+Fib(k-2);
F_k_1 := Result;
end;
end;
end;
Var i :Integer;
end;
Begin //writeln(Fib(10));
Var i :Integer;
for i := 0 to 40 do
begin
writeln(i:4,': ',Fib(i));
for i := 0 to 40 do writeln(i:4,': ',Fib(i));
readln;
readln; end.
end.
Dany jest pewien ciÄ…g rekurencyjny q:
Rekurencja
q0 = 1,
q1 = 2
qn = (qn-1-qn-2)*qn-2
Należy zaprojektować algorytm funkcji rekurencyjnej obliczający wartość
dowolnego wyrazu ciÄ…gu. Rozwizanie - rekurencja :
Wśród wyrazów ciągu q, zgodnie z def., możemy wyróżnić trzy grupy:
- wyraz q0,
- wyraz q1,
- pozostałe wyrazy qn.
Taki podział pozwala skonstruować warunki stopu. W przypadku dwóch
pierwszych wyrazów, wartość jest znana, więc należy wyliczyć wyraz q0
albo q1 i podać jako wynik odpowiednio 1 i 2.
W przypadku następnych wyrazów należy wyliczy , wartość ze
wzoru na qn.
Rekurencja
Algorytm zapisany w postaci listy kroków wygląda następująco
( n jest parametrem formalnym i oznacza indeks wyrazu ciÄ…gu
wyliczenia):
Krok 1: Jeśli n=0 to zwróć wynik 1, w przeciwnym razie,
Krok 2: Jeśli n=1 to zwróć wynik 2, w przeciwnym razie,
Krok 3: Jako wynik działania zwróć wartość :
((Wywołaj funkcje dla n-1)-(Wywołaj funkcje dla n- 2))*(Wywołaj funkcje dla n-2)
Krok 4: Zakończ działanie.
Rekurencja
program Rek_ciag;
{$APPTYPE CONSOLE} {$O-,Q+,R+}
Uses SysUtils;
function ciag(n :integer) :integer;
begin
if n = 0 then ciag:=1
else
if n=1 then ciag:=2
else ciag:=(ciag(n-1)-ciag(n-2))*ciag(n-2);
end;
Var n :integer;
Begin
write('Podaj n='); readln(n);
writeln(n,' _ty wyraz ciagu q= ',ciag(n));
readln;
end.
Rekurencja
Należy opracować rekurencyjny algorytm odwracania ciągu liter
(jeden z parametrów formalnych typu string).
Algorytm rekurencyjny będzie
działał na następujących zasadach:
" Warunkiem stopu będzie
napotkanie końca wyrażenia,
" Dla każdego kolejnego znaku
odwrócenia dokonujemy wywołując
funkcje dla pozostałej części ciągu
i dodajÄ…c do niej aktualny element
na koniec,
" Jeśli osiągniemy koniec ciągu
należy, jako wynik zwracamy ciąg
pusty   .
Rekurencja
program Rek_odwracanie;
{$APPTYPE CONSOLE} {$O-,Q+,R+}
Uses SysUtils;
function rewers(indeks :integer; tekst :string):string;
begin
if indeks <= length(tekst) then
rewers := rewers(indeks+1,tekst) + tekst[indeks]
else rewers := '';
end;
var tekst :string;
i:integer;
Begin
//atak, rak, arak, Napis, Hetman, ??
write('Podaj tekst='); readln(tekst);
writeln(rewers(i,tekst));
readln;
end.
Typ proceduralny
Typ proceduralny deklarowany słowami kluczowymi Type oraz
procedur lub function stworzony został aby traktować
procedury lub funkcje jako wartości pewnych zmiennych.
W przykladzie wartość zmiennej typu proceduralnego
 mFunkcja staje siÄ™ odpowiedniÄ… funkcjÄ… realizujÄ…cÄ…
odpowiednie zadania wybrane przez użytkownika.
Typy i zmienne proceduralne można również definiować w
sekcji deklaracji zmiennych np.
Var mojaFunkcja: function (a,b:byte):real;
program PTYP_procedur2;
{$APPTYPE CONSOLE}
var
uses SysUtils;
mFunkcja:Tfunkcja;
type
x1,x2:integer;
Tfunkcja=function(a,b:integer):real;
zn:char;
begin
function
writeln('Podaj dwie liczby');
dodaj(skladnik1,skladnik2:integer):real;
readln(x1,x2);
begin
writeln('wybierz dzialanie: +
result:=skladnik1+skladnik2;
dodawanie, - odejmownie, * mnozeni
end;
/ dzielenie');
function odejmij(sklad1,sklad2:integer):real;
repeat
begin
Readln(zn);
result:=sklad1-sklad2;
until zn in ['+','-','*','/'];
end;
case zn of
function pomnoz(czynnik1,
'+':mFunkcja:=dodaj;
czynnik2:integer):real;
'-':mFunkcja:=odejmij;
begin
'*':mFunkcja:=pomnoz;
result:=czynnik1*czynnik2;
'/':mFunkcja:=podziel;
end;
end;
function podziel(dzielna,dzielnik:integer):real;
writeln('wynik wynosi:  ,
begin
mfunkcja(x1,x2));
if dzielnik<>0 then result:=dzielna/dzielnik;
readln;
end;
end.
Procedury kierujace działaniem programu :
exit, halt, abort, sleep, runerror
Exit  procedura ta służy do przerwania bieżącego podprogramu
(procedury lub funkcji) i powrotu do programu głównego. Jeśli wywołana
Jest z programu głównego to kończy jego działanie.
Halt  Procedura ta kończy działanie programu przekazując sterowanie
do systemu operacyjnego. Procedura halt może być wywolana
bez parametru lub z jednym typu integer, którego wartość jest zwracana
Systemowi operacyjnemu jako kod wyjścia. (kod zero = jeśli brak
Parametru)
Runerror  procedura wywoływana bez parametów lub jednym typu
Byte przerywa działanie programu zwracają kod błedu wykonywania
Programu (run-time-error) (kod zero = jeśli brak Parametru)
Procedury kierujace działaniem programu :
exit, halt, abort, sleep, runerror
Sleep - procedura wywoływana z jednym parametrem typu cardinal
Powoduje zatrzymanie programu na liczbę milisekund równą wartości
Podanego parametru
Abort - procedura wywołana bez parametru kończy działanie programu
Z wywołaniem wyjątku  Eabort (o tym póżniej)
@ - OPERATOR ten zwraca wskaz
nik do zmiennej funkcji, procedury
Lub metody dla której jest wywołany. Efektem jest stworzenia
Wskaz
nika do zmiennej na której wykonano operację.
program Pr_exit;
{$APPTYPE CONSOLE}
uses SysUtils;
var i:byte;
begin
procedure zewnetrzna;
writeln('wywolujemy procedure
procedure wewnetrzna;
zewnetrzna');
begin
writeln('To napisala procedura
zewnetrzna;
wewnetrzna');
readln;
exit;
exit;
writeln('a tego nigdy nie zobaczymy');
end;
writeln('ten napis tez sie nie pojawi');
readln;
begin
end.
writeln('To napisala procedura zewnetrzna');
wewnetrzna; //tu wyw. procedure wewnetrzna
writeln('ten napis sie pojawi, kiedy wewnetrzna
przekaze sterowanie do zewnetrznej');
exit;
writeln('A ten napis juz sie nie pojawi');
end;
program Pr_sleep_halt;
{$APPTYPE CONSOLE}
uses SysUtils;
var
s:string;
i:byte;
begin
s:='Dziala opoznienie- (sleep)';
for i:=1 to length(s)
do
begin
write(s[i]);
sleep(400);
end;
readln;
writeln ('a teraz zadziała procedura Halt za 5 sekund');
sleep(5000);
Halt;
Writeln('Tego napisu nie zobaczymy')
end.
program PR_operator_wsk;
{$APPTYPE CONSOLE}
uses SysUtils;
type Ttablica=array[1..10] of byte;
var MojaTablica:Ttablica;
WskaznikNaLiczbe:^byte;
i:byte;
begin
for i:=1 to 10 do MojaTablica[i]:=100-i;
//tablica zostaje wypełniona liczbami od 99 do 90
WskaznikNaLiczbe:=@MojaTablica[1];
//Zmienna wskazujaca zostaje ustawiona na pierwszy element tablicy
inc(WskaznikNaLiczbe);
//wskaznik zostaje zwiekszony
//UWAGA: zwiekszony zostaje adres, na ktory wskazuje wskaznik
//a nie wartosc zmiennej wskazywanej.
//Wskaznik wskazuje teraz na drugi element tablicy
writeln(wskazniknaliczbe^);
//W drugim elemencie tablicy jest zapisana liczba 100-2=98
readln;
end.