Rekurzija C#

Rekurzija C#

Avtor: Mateja Gorišek, pred. M.Lokar, prenos v NAUK Alja Gligić

Rekurzija

je postopek, ki je opisan sam s sabo.

(rekurzija1.png) (rekurzija3.png) (rekurzija2.png)

Pomen besede rekurzija 1


Rekurzija v SSKJ (slovar slovenjskega knjižnega jezika) ne obstaja, obstajata pa besedi rekurz in rekurirati:

  • rekúrz -a m (u) knjiž. vrnitev (na kako stvar, dejstvo): rekurz na že omenjana dognanja ni potreben / v njegovih romanih so pogosti rekurzi v preteklost ◊ jur. rekurz nekdaj pritožba zoper sklep v pravdnem postopku
  • rekurírati -am dov. in nedov. (i) knjiž. vrniti se (na kako stvar, dejstvo): pogosto rekurirati na nekatera dejstva, spoznanja ◊ jur. rekurirati nekdaj pritožiti se zoper sklep v pravdnem postopku

Pomen besede rekurzija 2


Definicijo rekurzije imamo dano v velikem slovarju tujk (rekurzija iz latinščine recurrere iti nazaj, vrniti se) :

  • definiranje funkcije ali postopka s samim seboj (informatika)
  • izvajanje veličine ali funkcije, ki jo je treba šele definirati na že znano veličino (matematika).

Pomen besede rekurzija 3


Rekurzijo srečamo tudi v vsakdanjem življenju. Definicija prednika neke osebe je lahko:

  • prednik osebe je eden od roditeljev osebe (osnovni primer)
  • prednik pa je tudi roditelj kateregakoli prednika (rekurzivni primer)

Pomen besede rekurzija 4

Rekurzijo si lahko predstavljamo tudi z geometrijskimi figurami, ki so določene rekurzivno:

(sierpinski.png)
Trikotnik Siepinskega
(kochova.png)
Kochova snežinka

Rekurzivna metoda

V matematiki in računalništvu pomeni rekurzija podajanje metode na tak način, da se v definiciji sklicujemo na isto metodo.

Metodam, ki kličejo samo sebe, pravimo rekurzivne metode. V metodah pogosto uporabljamo parameter, ki se povečuje ali zmanjšuje. Ko dosežemo neko vrednost, je rekurzije konec. Da se rekurzija konča, je vedno potreben ustavitveni pogoj. Ustavitveni pogoj pove, da v postopku ne kličemo metode na manjšem ali večjem problemu. Kot ustavitveni pogoj podamo enostaven, majhen problem. Če le tega ni, se izvajanje metode nikoli ne konča.

Rekurzivna metoda

rekurziva_metoda (problem
{
    if (majhen problem) vrnemo rešitev;
    else
    {
         razdelimo problem na enega ali več manjših problemov enake vrste
         rekurzivna_metoda(manjši problem);
    }
}

Lastnosti rekurzivne metode

Vse rekurzivne metode morajo torej imeti naslednje lastnost:

  • ustavitveni pogoj, ki prekine izvajanje rekurzije. Zanj uporabimo enega ali več osnovnih problemov (najbolj enostavne primere).
  • Vsak rekurzivni klic mora originalni klic poenostaviti tako, da se bo bližal ustavitvenemu pogoju, dokler se ne izenači z ustavitvenim pogojem. Ko se izenači se rekurzija konča.

Primer problema - Hanoiski stolpiči

Problem s Hanoiskimi stolpiči je rekurzivni problem, ki temelji na preprosti igri.
Za igro potrebujemo tri palice, na katere nato zlagamo okrogle ploščice različne velikosti. Število ploščic je poljubno, vse pa morajo biti različnega premera.

Cilj igre:
Prestaviti želimo vse ploščice na desno palico z najmanjšim možnim številom potez ob upoštevanju naslednjih pravil:

  • naenkrat lahko premaknemo samo eno ploščico
  • nobena ploščica ne sme biti na vrhu manjše pločice, razporejeno morajo biti od največje do najmanjše.
  • vsako ploščico moramo odložiti na eno od palic (nikoli ob strani)

  • premaknemo lahko le ploščico, ki je na vrhu ene od palic.

    (hanoi.png)

Reševanje problema:
Zapisali bomo rekurzivno metodo, ki bo nam vrnila vrstni red premaikanja ploščic. Tako, da bomo naredili kar se da malo potez.
Metoda bo za parameter prejela število pločic (). Nato pa bomo prestavljali obroče iz prvega stolpca na zadnji stolpec, s pomočjo srednjega stolpca.
Potek reševanja:

  • najprej rešimo problem velikost . Tako prestavimo vse ploščice (razen največje) na srednji stolpec, pomagamo si z zadnjim stolpcem.
  • sedaj imamo vse ploščice (razen največje) na srednjem stolpcu. Tako lahko največjo ploščico premaknemo na zadnji stolpec.

  • Sedaj lahko s pomočjo prvega stolpca premikamo ploščice iz drugega stolpca na zadnji stolpec, pri premikanju največjo ploščico pustimo na dnu stolpca. Sedaj smo prestavili vse ploščice na prvi stolpec, največja ploščica pa je ostala na drugem stolpcu. Tako največjo premaknemo na tretji stolpec.

    S takim postopkom nadaljujemo, dokler ne premaknemo še zadnjo ploščico.
    Več o Hanoiskih stolpičih si lahko preberete na povezavi: http://sl.wikipedia.org/wiki/Hanojski_stolpi

Koda v C#

Rekurzivna rešitev problema

Rekurzivna rešitev problema:

public static void hanoi(int n, string st1, string st2, string st3)
        {  /* metoda nam izpiše potek igre, kako naj prestavljamo pločice,
* da bomo naredili čimmanj potez prestavljanja pločic. Pločice moramo prestaviti
* iz prvega stolpca na tretji stolpec. */
            if (n == 1)
            {  // ustavitveni pogoj
                Console.WriteLine("Preloži s stolpca " + st1 + " na stolpec " + st3);
            }
            else
            {  // rekurzivni klic
                hanoi(n - 1, st1, st3, st2); // prestavljamo iz stolpca 1 na stolpec 2, s pomočjo tretjega stolpca
                Console.WriteLine("Preloži s stolpca " + st1 + " na stolpec " + st3);
                hanoi(n - 1, st2, st1, st3); // prestvaljamo iz 2 stolpca na 3 stolpec, s pomočjo prvega stolpca
            }

        }
        static void Main(string[] args)
        {
            Console.Write("Vnesi šrevilo ploščic: ");
            int n = int.Parse(Console.ReadLine());
            hanoi(n, "1", "2", "3");
            Console.ReadLine();
        }


V zgornji metodi metoda kliče samo sebe in to dvakrat. Če imamo problem velikost , v rekurzivnem klicu rešujemo problem . Torej najprej prestavljamo s prvega stolpca na drugi stolpec s pomočjo tretjega stolpca. Nato pa še z drugega stolpca na tretji stolpec s pomočjo prvega.

Primer problema

Podano imamo Fibonaccijevo zaporedje: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... Vsak člen zaporedja (razen prvih dveh) je vsota predhodnjih dveh členov. Označimo splošni n-ti člen tega zaporedja z F(n). Kako dobimo n-ti člen lahko izrazimo rekurzivno:

F(n) = F(n-1) + F(n-2), n = 3, 4, ...

Za začetna člena n = 1, 2 pa imamo poseben pogoj:

F(1) = 1 in F(2) = 1

Rekurzivno definicijsko enačbo lahko uporabimo direktno za izračun določenega člena zaporedja, naprimer za n = 4.

F(4) = F(3) + F(2) = (F(2)+ F(1)) + 1 = (1 + 1) + 1 = 3

Sedaj lahko zapišem rekurzivno metodo int Fibonacci(int n), ki za dani n izračuna in vrne ustrezno Fibonaccijevo število.
Zgornjo definicijo lahko uporabimo v metodi:

  • če je n = 1 ali n = 2, potem je Fibonacci(n) = 1,
  • sicer pa je Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-1)

Zapis kode v C# na naslednji strani: Koda v C#

Rekurzivna rešitev problema

Rekurzivna rešitev problema:

public static int Fibonacci(int n)
        {
            // rekurzivna metoda
            if (n == 1 || n == 2) return 1; // ustavitveni pogoj
            else return (Fibonacci(n - 1) + Fibonacci(n - 2));  // rekurzivni klic
        }
        static void Main(string[] args)
        {
            // Klic rekurzivne metode
            Console.WriteLine(Fibonacci(14));
            Console.ReadLine();
        }

V zgornji metodi, metoda kliče samo sebe in to dvakrat v stavku

return (Fibonacci(n - 1) + Fibonacci(n - 2))

To je rekurzija.
Iterativna rešitev problema:

public static int Fib(int n)
        {
            // Iterativna metoda
            if (n == 1 || n == 2) return 1;
            int f1 = 1;
            int f2 = 1;
            int pomozni;
            for (int i = 0; i < n - 2; i++)
            {
                pomozni = f2;
                f2 = f1 + f2;
                f1 = pomozni;
            }
            return f2;
        }

        static void Main(string[] args)
        {
            // Klic iterativne (klasične) metode
            Console.WriteLine(Fib(14));
            Console.ReadLine();
        }


Razlika med iterativno in rekurzivno rešitvijo problema

Rekurzivna rešitev je krajša, enostavnejša in jasnejša. V njej se tudi neposredno zrcali originalna matematična definicija Fibonaccijevega zaporedja in zato je tudi lažje razumljiva. V rekurzivni rešitvi opazimo tudi, da ni potrebna uporaba dodatnih spremenljivk.

Problem pri rekurzivni rešitvi je prostor in čas, ki ga porabi. Rekurzivna metoda traja nekoliko dlje kot iterativna metoda. V primeru (Fibonacci) je rekurzivna metoda še posebaj počasna, saj zahteva več seštevanj kot irerativna metoda.
Prav tako je problem tudi prostor, ki ga porabi. Vsak rekurzivni klic zahteva nekaj prostora. Podatki o rekurzivnem klicu se shranjujejo v pomnilniški sklad in če je globina tega sklada velika, potem je lahko pomnilnik preobremenjen. Torej so rekurzivni programi nekoliko potratnejši od iterativnih programov.

Rekurzija je dobra, toda počasna in lahko zavzame tudi veliko prostora, zato se ji poskušamo izgoniti, če je le mogoče.

Viri


0%
0%