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



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.



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



Gdy funkcja rekurencyjna wywołuje samą siebie, na

stosie są już zmienne lokalne będące własnością

pierwszego wywołania tej funkcji.



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.

Funkcje rekurencyjne

program NWPrekur;
{$APPTYPE CONSOLE}
uses SysUtils;

function NWP(a, b :cardinal) :cardinal;
begin

if b = 0 then

Result := a

else

Result := NWP(b, a mod b);

end;

begin

writeln(NWP(18,24));
readln;

end.

program NWPnierekur;
{$APPTYPE CONSOLE}
uses SysUtils;

function NWP(a, b :cardinal) :cardinal;
var

r :cardinal;

begin

while b <> 0 do
begin

r := a mod b;
a := b;
b := r;

end;
Result := a;

end;

begin

writeln(NWP(18,24));
readln;

end.

Rekurencja

program FibRekur;
{$APPTYPE CONSOLE} {$O-,Q+,R+}

Uses SysUtils;
// F_0=0 F_1=1 F_k = F_k-1+F_k-2
function Fib(k :cardinal) :cardinal;
begin

if k <= 1 then

Result := k

else

Result := Fib(k-1)+Fib(k-2);

end;

Var i :Integer;
Begin //writeln(Fib(10));

for i := 0 to 40 do

writeln(i:4,': ',Fib(i));

readln;

end.

program FibNieRekur;
{$APPTYPE CONSOLE} {$O-,Q+,R+}
uses SysUtils;
function Fib(k :cardinal) :cardinal;
Var i, F_k_1, F_k_2 :cardinal;
begin

Result := k;
if k > 1 then begin

F_k_1 := 1; F_k_2 := 0;
for i := 2 to k do
begin

Result := F_k_1 + F_k_2;
F_k_2 := F_k_1;
F_k_1 := Result;

end;

end;

end;
Var i :Integer;
begin
for i := 0 to 40 do writeln(i:4,': ',Fib(i));

readln; end.

Rekurencja

Dany jest pewien ciąg rekurencyjny q:

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 do

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}

uses SysUtils;

type

Tfunkcja=function(a,b:integer):real;

function

dodaj(skladnik1,skladnik2:integer):real;

begin

result:=skladnik1+skladnik2;

end;

function odejmij(sklad1,sklad2:integer):real;

begin

result:=sklad1-sklad2;

end;

function pomnoz(czynnik1,

czynnik2:integer):real;

begin

result:=czynnik1*czynnik2;

end;

function podziel(dzielna,dzielnik:integer):real;

begin

if dzielnik<>0 then result:=dzielna/dzielnik;

end;

var

mFunkcja:Tfunkcja;

x1,x2:integer;

zn:char;

begin

writeln('Podaj dwie liczby');

readln(x1,x2);

writeln('wybierz dzialanie: +

dodawanie, - odejmownie, * mnozenie,

/ dzielenie');

repeat

Readln(zn);

until zn in ['+','-','*','/'];

case zn of

'+':mFunkcja:=dodaj;

'-':mFunkcja:=odejmij;

'*':mFunkcja:=pomnoz;

'/':mFunkcja:=podziel;

end;

writeln('wynik wynosi: ‘ ,

mfunkcja(x1,x2));

readln;

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 wskaźnik do zmiennej funkcji, procedury

Lub metody dla której jest wywołany. Efektem jest stworzenia

Wskaźnika do zmiennej na której wykonano operację.

program Pr_exit;

{$APPTYPE CONSOLE}

uses SysUtils;

var i:byte;

procedure zewnetrzna;

procedure wewnetrzna;

begin

writeln('To napisala procedura

wewnetrzna');

exit;

writeln('a tego nigdy nie zobaczymy');

end;

begin

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;

begin

writeln('wywolujemy procedure

zewnetrzna');

zewnetrzna;

readln;

exit;

writeln('ten napis tez sie nie pojawi');

readln;

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.