Helló C#! Helló Világ! 2.1

  2. Home
  4. Docs
  6. Helló C#! Helló Világ! 2.1
  8. 5. Osztályok, objektumok
  10. Metódusok – Rekurzió

Metódusok – Rekurzió

A metódusok lehetnek rekurzívak vagy nem rekurzívak. Egy vicces programozói mondás szerint ahhoz, hogy megértsük a rekurziót, először meg kell értenünk a rekurziót.

Rekurzió és a problémák

Rekurzió és a problémák – https://xkcd.com/1739/

Köznapibb, emészthető formában egy metódus akkor rekurzív, ha a metódus a blokkjában saját magát hívja meg.

A rekurzív metódusok használata nem minden esetben a legjobb választás. Minden rekurzív metódus némi trükközéssel átalakítható ciklusos működésűvé és minden ciklus felépíthető rekurzív metódusként. A rekurzív metódusok problémája, hogy ha egy komplex problémát kell megoldani, akkor a metódus hívás közben hatalmas mennyiségű információ halmozódik fel a paraméterek átadására szolgáló veremben1, ami StackOverFlow kivétel keletkezéséhez vezethet.

Leginkább olyan algoritmusokban szokás alkalmazni a rekurzív metódusokat, ahol célravezetőbb rekurzívan megoldani a problémát. Például ilyen probléma egy gráf2 vagy fa3 csomópontjainak bejárása.4

A rekurzió bemutatására klasszikus példaprogram a faktoriális számítás. Az alábbi példaprogram ezt mutatja be:

using System;

namespace PeldaRekurzivmetodus
{
    class Program
    {
        static int call;

        static long Faktorialis(int n)
        {
            if (n <= 1) { return 1; }
            call++;
            return n * Faktorialis(n - 1);
        }

        static void Main(string[] args)
        {
            for (int i = 0; i < 21; i++)
            {
                call = 1;
                var fakt = Faktorialis(i);
                Console.WriteLine("{0}! = {1}, call: {2}", i, fakt, call);
            }
            Console.ReadKey();
        }
    }
}

A program kimenete:

$
0! = 1, call: 1
1! = 1, call: 1
2! = 2, call: 2
3! = 6, call: 3
4! = 24, call: 4
5! = 120, call: 5
6! = 720, call: 6
7! = 5040, call: 7
8! = 40320, call: 8
9! = 362880, call: 9
10! = 3628800, call: 10
11! = 39916800, call: 11
12! = 479001600, call: 12
13! = 6227020800, call: 13
14! = 87178291200, call: 14
15! = 1307674368000, call: 15
16! = 20922789888000, call: 16
17! = 355687428096000, call: 17
18! = 6402373705728000, call: 18
19! = 121645100408832000, call: 19
20! = 2432902008176640000, call: 20

  1. “A verem (vagy veremtár) a számítógép memóriájának egy része, amelybe más adatok mellett a processzor azokat a memóriacímeket menti el, ahova az egyes eljárások befejeztével visszatér.” – https://hu.wikipedia.org/wiki/Verem_(adatszerkezet)↩

  2. „A gráf a matematikai gráfelmélet és a számítógép-tudomány egyik alapvető fogalma. A gráf dolgok (csomópontok, csúcsok) és rajtuk értelmezett összeköttetések (élek) halmaza. Egy gráfot megadhatunk csúcsainak és éleinek felsorolásával, vagy szemléletesebben egy diagram formájában, ahol a pontok felelnek meg a gráf csúcsainak, az őket összekötő ívek pedig az éleknek. A két megadási mód ekvivalens, azaz a gráf pusztán egy struktúra, semmilyen megjelenítési információt nem tartalmaz, így különböző diagramok is tartozhatnak ugyanahhoz a gráfhoz.” – https://hu.wikipedia.org/wiki/Gráf↩

  3. A fa egy összefüggő, körmentes egyszerű gráf. A fa elsőfokú csúcsait levélnek hívjuk. Egy nem levél csúcs a fában belső csúcs. Néha van a fának egy megkülönböztetett csúcsa, a gyökér. A gyökeres fa olyan fa, melyben van gyökér. Az irányított gyökeres fák éleit általában a gyökértől elfelé mutató irányítással látjuk el. Olyan kontextusban, ahol a fák általában gyökeresek, a nem gyökeres fákat szabad fáknak is nevezik.↩

  4. A fájlrendszer mappaszerkezete is felfogható gráfként. Leginkább fájlkezelés során fogjuk használni a rekurziót.↩

Tags , ,