| Strukture podataka i algoritmi |
| Rekurzivna definicija liste |
Listu mozemo da definisemo kao:
Lista moze da se obilazi rekurzivnom funkcijom:
npr. da bi prebrojali broj elemenata u listi:
int ListCount( List l ) {
if ( l == NULL ) return 0;
else return 1 + ListCount( l->next );
}
Medjutim, mnogo je brze napisati ovu funkciju bez rekurzivnog poziva:
int ListCount( List l ) {
int cnt = 0;
while ( l != NULL ) {
cnt++;
l = l->next;
}
return cnt;
}
Gubitak prilikom poziva funkcije je dovoljno veliki na svakoj masini,
tako da se druga iterativna verzija izvrsava brze.
(Jos jedan faktor je da performanse modernih masina
veoma mnogo zavise od kes memorije:
iterativni kod druge verzije ne koristi toliko mnogo memorije za stek poziva
i time bolje iskoristava kes memoriju.)
|
Nazad na Stabla Nazad na Sadrzaj |