POLITECHNIKA WARSZAWSKA
Instytut Automatyki i Robotyki
ZASADY PROGRAMOWANIA KOMPUTERÓW
ZAP  zima 2013
Język programowania: C/C++
Środowisko programistyczne: Qt
Wykład 8 . Zasięg zmiennych. Rekurencja.
2
Nagłówki funkcji main
Dwa możliwe nagłówki funkcji main:
int main ( ) {
...
tej wersji używamy w Qt
return 0;
}
int main ( int argc, char *argv[ ] ) {
...
return 0;
}
Parametry te mają znaczenie tylko przy uruchamianiu programu z linii komend
(wiersza poleceń):
" Parametr argc oznacza liczbę argumentów (parametrów) podawanych
wraz z nazwą programu w linii komend
" Tablica argv[ ] zawiera adresy tych argumentów - zostaną one
wykorzystane po uruchomieniu programu
3
Funkcje a zasięg zmiennych
Zasięg zmiennej (stałej, struktury)
" wszystkie miejsca w programie, z których możliwy jest dostęp do tej zmiennej
" ZMIENNE, STAA
E I STRUKTURY GLOBALNE
" zadeklarowane na zewnątrz wszystkich funkcji
" zasięgiem ich jest cały program wraz z funkcjami
" mogą być przesłonięte w każdej z funkcji
" ZMIENNE STAA
E I STRUKTURY LOKALNE
" zadeklarowane wewnątrz funkcji
" zasięgiem ich jest treść tej funkcji
" przesłaniają zmienne globalne o tej samej nazwie
" ZASI
G PARAMETRÓW FORMALNYCH W FUNKCJI
" zasięgiem ich jest treść tej funkcji
" mogą przesłonić zmienne globalne
Uwagi nt. zmiennych, stałych i struktur globalnych i lokalnych są aktualne nie tylko w
stosunku do treści funkcji, ale również w stosunku do dowolnego bloku, w którym jakaś
zmienna jest lokalnie zdefiniowana  vide wykład 2. Treść funkcji jest szczególnym przypadkiem
bloku i wewnątrz niej mogą być zagnieżdżone inne bloki wraz z ich lokalnymi zmiennymi.
4
Przykład  zasięg zmiennych
using namespace std;
const int N=15; // stała N - globalna
int p, j, b; // oraz zmienne globalne, dostępne w całym programie
// także wewnątrz wszystkich funkcji - chyba że zostaną przesłonięte
double policz ( ) {
char p, k; // zmienne lokalne, dostępne tylko w tej funkcji policz
........... // zmienna lokalna p typu char przesłania zmienną globalną p typu int
........ // tutaj można też używać zmiennej globalnej j
for (int k =0; j< N; j++) { // zmienne k lokalna w pętli for jest dostępna tylko w tej pętli
& // gdzie zasłania zmienną k lokalną w funkcji
}
Zalecane jest używanie:
if (& .) {
" stałych i struktur globalnych  bo
wtedy są dostępne dla wielu funkcji
double b; // zmienne b lokalna w bloku if
" zmiennych lokalnych w treści funkcji
& // zasłania zmienną globalną b
(wtedy nie będą mogły ulec zmianie
wskutek działania innych funkcji)
}
}
int main ( ) {
........... // tutaj nie można używać zmiennej k
........... // można zaś używać zmiennych globalnych p, j, b oraz stałej N
}
5
Rekurencja - wprowadzenie
" REKURENCJA zachodzi wówczas, gdy funkcja wywołuje samą siebie
bezpośrednio lub pośrednio (za pomocą innego funkcji)
" Funkcje rekurencyjne muszą charakteryzować się dwoma własnościami:
1. W ramach algorytmu musi być zdefiniowany warunek końca
2. Po każdym wywołaniu funkcji musi nastąpić zmiana wartości
zmiennych lub parametrów funkcji
REKURENCJA BEZPOŚREDNIA
" Funkcja zawiera w swojej treści bezpośrednie odwołanie do samej siebie
Przykład:
void dodaj (......) { // nagłówek funkcji dodaj
...........
if (warunek)
dodaj (......); // wywołanie funkcji dodaj
..........
}
6
Rekurencja pośrednia
REKURENCJA POŚREDNIA
" Funkcja A zawiera odwołanie do innej funkcji B, która zawiera pośrednie lub
bezpośrednie odwołanie do funkcji A.
Przykład:
void obliczTo(....); // tylko nagłówek, czyli deklaracja funkcji obliczTo
void zrobCos(...) {
....
obliczTo(....); // funkcja zrobCos wywołuje funkcję obliczTo
...
};
void obliczTo(....) {
...
if (...)
zrobCos(...); // funkcja obliczTo wywołuje funkcję zrobCos
...
}
int main( ) {
...
obliczTo(...); // wywołanie funkcji obliczTo, która wywoła zrobCos, a ta z kolei wywoła
// obliczTo - czyli obliczTo wywoła pośrednio samą siebie
}
7
Rekurencja ogonowa
Najprostszy rodzaj rekurencji - musi spelniać warunki:
" Wywołanie rekurencyjne jest ostatnią operacją wykonywaną przez funkcję - w
momencie tego wywołania nie ma już nic więcej do wykonania poza ewentualnym
return-em
" Wywołanie to jest jedynym wywołaniem funkcji przez samą siebie w treści tej funkcji
void czytaj_i_pisz ( ) {
double x;
cin >> x;
cout << x << endl;
if (x!=0)
Funkcja rekurencyjna - tu nie
czytaj_i_pisz ( );
ma jawnej pętli !
}
Rekurencję ogonową bardzo łatwo jest zastąpić pętlą:
Wczytuje i drukuje
ciąg liczb aż do
void czytaj_i_pisz ( ) {
napotkania zera
double x;
(zero też drukuje)
cin >> x;
cout << x << endl;
Funkcja nierekurencyjna
while (x!=0) {
cin >> x;
cout << x << endl;
}
}
8
Rekurencyjne wywoływanie podprogramów
Realizowane jest podobnie, jak zwykłe wywołania podprogramu w podprogramie.
" Zmienne przechowujące wartość parametrów aktualnych (w przypadku
parametrów formalnych przekazywanych przez wartość) i zmienne lokalne
podprogramu wywołującego są zapamiętywane na stosie wraz z adresem
powrotu do miejsca wywołania, po czym następuje wywołanie podprogramu z
nowymi parametrami aktualnymi i zmiennymi lokalnymi.
" Po wykonaniu tego podprogramu następuje powrót do podprogramu
wywołującego poprzez zdjęcie ze stosu zapamiętanych wartości i wówczas
zmienne lokalne oraz parametry aktualne tego podprogramu stają się znowu
aktywne.
" Dla podprogramu rekurencyjnego parametry formalne i zmienne lokalne mają
po każdym wywołaniu takie same nazwy i znaczenie, ale zwykle mają inne
wartości. Powstaje stos, który najpierw rośnie (i nawet może się przepełnić), a
póz
niej zanika. Jedynie rekurencja ogonowa nie wymaga stosu.
" Przekształcanie funkcji rekurencyjnej na iteracyjną wymaga zwykle jawnego
obsłużenia stosu.
Wersja rekurencyjna jest bardziej elegancka, poprawia czytelność kodu, lepiej
się samodokumentuje - w przypadkach, kiedy problem jest z natury
rekurencyjny. Ale zwykle jest wolniejsza od wersji iteracyjnej.
9
Przykład  Odwrotne drukowanie
Program drukowania w odwrotnej kolejności ciągu znaków wprowadzanych z klawiatury,
aż do napotkania znaku zapytania (jest on drukowany jako pierwszy znak ciągu
wynikowego).
znak
adres powrotu
Stos:
...
...
adres powrotu
void dr_wstecz ( ) {
znak znak znak
adres powrotu adres powrotu adres powrotu
char znak;
znak znak znak znak
... ...
adres do main adres do main adres do main adres do main
cin >> znak;
if (znak!= ? )
dr_ wstecz ( ) ;
cout << znak << endl;
}
Dla każdego wywołania procedury tworzona jest nowa zmienna lokalna znak.
Poziom: 1 2 ..... N
cin >> znak
cin >> znak
...... cin >> znak { znak== ? }
...... cout << znak
cout << znak
cout << znak
10
Przykład  Obliczanie silni
Definicja silni:
k !=k*(k-1)! dla k>1; k!=1 dla k=1.
int silnia (int k) {
if (k > 1)
return k * silnia (k-1);
else
return 1;
}
Dla każdego wywołania funkcji tworzona jest Podobny przykład: funkcja, która
nowa zmienna przechowująca wartość zwraca sumę ciągu liczb <100
zakończonych liczbą >=100.
parametru k.
Np.: dla wczytanej wartości k równej 3:
int policz ( ) {
Poziom: 1 2 3
int x;
cin >> x;
k=3
if (x<100)
k=2
k=1
return x+policz ( ) ;
silnia=1
else
return 0;
silnia=2*1
}
silnia=3*2
11
Przykład  Obliczanie wyrazów ciągu Fibonacciego
Program wyznaczania wyrazów ciągu Fibonacciego: 0 1 1 2 3 5 8 13 ...
Fib (n)= n jeśli n <2
Fib(n-2) +Fib (n-1)
int Fib (int n) {
if (n < 2)
return n;
else
return Fib (n-1) + Fib (n-2);
}
Przykład nadużywania rekurencji - te same wyrażenia obliczane są wielokrotnie
F(4)
F(2) F(3)
n= 6 13 wywołań
F(0) F(1) F(1) F(2)
n= 20 21 tys. wywołań
F(0) F(1)
n= 31 3 mln wywołań!
12
Przykład - FloodFill - wypełnianie wnętrza obszaru
oldColor
newColor
void Fill (x, y) {
if (getPixel (x, y) == oldColor) {
y
putPixel (x, y, newColor);
Fill (x, y + 1); //do góry
x
Fill (x-1, y); // w lewo
Fill (x, y-1); // w dół
Fill (x + 1, y); // w prawo
}
return;
}
// getPixel - pobierz kolor pixela
// putPixel - zamaluj pixel kolorem
13
FloodFill  kolejność analizowanych elementów
Przykład wypełniania (zamalowywania) wewnętrznego obszaru:
w powiększeniu:
element początkowy
wypełniania
Aby zamalować 4 wewnętrzne elementy, trzeba
przeanalizować kolejno następujące elementy
(co widać po włączeniu opcji Krokowo):
1 zamaluj, 2, 3, 4-zamaluj
5, 6, 7, 8-zamaluj, 9-zamaluj,
10, 11, 12, 13, (14-wróć do 8)
15, 16, 17, (18-wróć do 4), (19-wróć do 1), 20
14
Przykład - płatek śniegu Kocha
ile =
0
void Koch (int bok, int ile) {
if (ile==0)
rysuj_odcinek_o_dlugosci (bok);
else {
1
...// zapamiętaj położenie
Koch (bok/3, ile-1);
...// przesuń się o bok/3
...// obróć się o -60o
2
Koch (bok/3, ile-1);
...// przesuń się o bok/3
...// obróć się o 120o
Koch (bok/3, ile-1);
...// przesuń się o bok/3
3
...// obróć się o -60o
Koch (bok/3, ile-1);
...// wróć tam, gdzie byłeś
}
4
}