05. Függvények, eljárások, rekurzió

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égelen 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ő!