A programok a korábban megtárgyalt vezérlési szerkezetek alapján nem tudnának működni, ezért már a programozás kora hajnalán létrehozták a szubrutinokat, a procedurális programozás esetén a függvényeket, eljáráshívásokat, illetve az objektum orientált programok esetén a metódusokat. Ezek mind ugyanannak a gondolatnak a különböző megvalósításai. A gondolat lényege, hogy bizonyos szempontból összetartozó utasításokat vonjunk egy kódblokkba, adjunk neki nevet és a későbbiekben használhatjuk ezt a nevet ugyanúgy, mintha a programozási nyelv egy alapvető utasítása lenne.
A programban a programblokk egy helyén deklaráljuk a kódblokkot. Megadjuk a nevét, a paraméterlistáját a visszatérési értékével, és megírjuk a kódblokk belsejét.
A program másik helyén pedig meghívjuk a kódblokkot.
Eljárás (szubrutin, procedura)
Eljárásnak hívunk egy kódblokkot akkor, ha nincsen visszatérési értéke. Ilyenkor a kódblokk elvégez valamilyen tevékenységet, de ő maga nem képvisel semmiféle értéket. A különböző programozási nyelveken ezt másképpen jelölik, a C#-ben a visszatérési értéke void, azaz üres. Például egy egyszerű kiíró eljárás deklarálása így néz ki:
static void Üzenet(){
Console.WriteLine("Helló világ!");
}Ez a kis kód semmi mást nem csinál, mint kiírja a konzolra, hogy "Helló világ!" és nincsen visszatérési értéke.
Megjegyzés
A static kulcsszó azért kell, hogy a program más részéről is elérhető legyen az eljárás. Ennek az eljárásnak most nincsen paramétere!
Hogyan hívjuk meg ezt az eljárást? Például így:
public static void Main(string[] args){
Üzenet();
Console.ReadKey(true);
}Függvény (function)
A függvények olyan eljárások, amelyeknek van deklarált típusú visszatérési értékük. Ezek a függvények úgy viselkednek, mint például egy táblázatkkezelőben használt függvények. A deklarálásuk során meg kell adni, hogy milyen típusú értéket képviselnek majd, azaz milyen típusú értéket adnak vissza. A függvény deklarálásakor egy return utasítással adjuk vissza az értéket és egyúttal kilépünk a kódblokkból is. A visszatérési érték típusa lesz a függvény típusa.
A híváskor pedig olyan kifejezésekben kell használni őket, amelyek tudják kezelni a visszatérési értékeket. Átadtuk egy számtani sorozat első elemének értékét, a differenciát és azt, hogy hányadik elemig akarom a sorozat összegét kiszámítani, a függvény pedig visszaadja az első megadott számú elem összegét.
public static void Main(string[] args){
Console.ReadKey( Szamtanisorösszeg(5, 10, 7));
Console.ReadKey(true);
}A függvény deklarációja pedig így néz ki:
static int Szamtanisorösszeg(int a1, int d, int n));
int osszeg;
// n * (a1 + an) / 2 => n * ( 2*a1 + (n-1)*d ) / 2
osszeg = db * (2*a1 + (n - 1 )*d ) / 2;
return osszeg;
}A függvény típusa int és az összeg nevű változó értékét adja vissza az utolsó előtti sorában.
Megjegyzés
Egyébként ezt a függvényt kehetne rövidebben is írni...
Eljárások függvények működésének megvalósulása különböző programozási nyelvekben
Minden program futás közben "tudja", hogy a memóriában éppen hol tart, ugyanis a processzoroknak van egy program számlálójuk (Program Counter = PC). Ez a számláló minden utasítás után automatikusan növekszik az utasítás hosszával. Amikor egy függvényt vagy eljárást meghívunk a programban mielőtt a vezérlés átkerül az eljárásba az alábbiak történnek:
A program elmenti a program számlálót a memória egy speciális részébe, amit veremnek (stack) hívnak.
Az eljárásnak átadott paramétereket is a verembe teszi. (Ez így nem teljesen pontos, de a következő leckében ezt pontosítom).
Átugrik a vezérlés a meghívott eljárás kezdetére és a program számlálóba bekerül az új programrész memóriacíme
Végrehajtja a program az eljárás utasításait, közben lép a programszámláló.
Amikor eléri az eljárás végét a program és a visszatérési utasításhoz ér (Return), két eset lehetséges: ha ez egy függvény, akkor a visszatérési értéket a verem tetejére helyezi, ha visszatérés nélküli eljárás, akkor nem történik érték elhelyezése.
Betölti a programszámlálóba a hívás előtt a verembe lementett korábbi memóriacímet.
Ennek hatására a vezérlés visszakerül a hívás utáni utasításra.
Függvény esetén kiveszi a visszatérési értéket és feldolgozza, a verem tetejét is visszaállítja a hívás előtti állapotba, vagyis eldobja a verem korábbi tartalmát.
A hívó programból többé nem érhető el a verem tartalma.
Ha a meghívott eljárás újabb eljárást hív meg, akkor az akkori program számlálót elmenti a verembe és a fenti folyamat ismétlődik.
Rekurzió
Ha egy programban egy eljárás egyik utasítása meghívja saját magát, ezt rekurziónak hívják. A fenti folyamat annyiszor ismétlődik, ahányszor a program meghívja saját magát.
Ez azt eredményezi, hogy a verem - amely véges mennyiségű adatot tud csak tárolni - előbb-utóbb betelhet. Ekkor a program hibával leáll. Ez azt jelenti, hogy a rekurzívan megírt függvényben kell lennie olyan résznek, amely biztosítja, hogy a rekurzió megszakadjon, vagyis kell egy kilépési feltétel. Ha a kilépési feltétel miatt a rekurzió megszakad, akkor a verem nem telik be és a program tovább tud folytatódni.
Rekurzív algoritmusok
Rekurzív algoritmusokat akkor használunk, ha olyan problémát kell algoritmizálni, amelynek nincsen un. zárt képlet-szerű megoldása. Ilyen probléma gyakran adódik matematikai problémák esetén, de például a QuickSort (= Bináris rendezés, gyorsrendezés stb...) is vermet használ és rekurzív módon zajlik.
Megjegyzés
A QuickSort olyan rendezési algoritmus, amely 1000 adatot legrosszabb esetben 1 millió lépés alatt rendez, átlagosan 10000 lépés alatt. Minden más rendezési algoritmus 1000 adatot 1 millió lépés alatt rendez le legalább!
A rekurzív algoritmus használatakor szükséges kilépési feltételt deklarálni, amely meggátolja a végtelen rekurziót.
Példa egy rekurzív algoritmusra,
Az N faktoriális az egész számok szorzata 1-től N-ig. Rekurzívan megfogalmazva:
Ha n=1, akkor 1, különben Fakt(n) = n*Fakt(n-1);
static int Faktorialis(int n))
if(n == 1) {
return 1;
}else{
return n*Faktorialis(n-1);
}
}Meghívása:
Console.WriteLine(Faktorialis(10));
//Az eredmény: 10*9*8*7*6*5*4*3*2*1 lesz 3 628 800
Megjegyzés
Minden rekurzív algoritmusnak elméletileg létezik ciklussal megoldható algoritmusa is, de az átírás nem mindig magától értetődő!