Black Wolf - osobní stránky

Operace nad binárním stromem v C aneb rekurze vs. iterace

Operace nad binárním stromem v C aneb rekurze vs. iterace

Tento článek má dva cíle – jednak ukázat jednoduché, efektivní a elegantní řešení „školní” úlohy zmíněné v titulku, druhak krátce se zamyslet nad použitím rekurzivních a iterativních algoritmů.

Začnu tím prvním – jedná se o běžnou výukovou úlohu implementovat binární strom pomocí struktury a základní operace nad ním – nalezení a vložení prvku. Úlohu lze řešit dvěma způsoby – buď iterativně nebo rekurzivně. Co si pamatuji tak u nás to většina spolužáků řešila druhým způsobem. A výsledek byl zbytečně složitý po stránce kódu a také zbytečně neefektivní. Prvním způsobem to jde mnohem efektivněji a také jednodušeji – proč zbytečně psát spoustu kódu, když se to celé vejde téměř na jeden řádek;). Řešení pak vypadá takto jednoduše:

struct uzel_t{
   int cislo;
   uzel_t* levy;
   uzel_t* pravy;
};
uzel_t* vloz(uzel_t* strom, int cislo){
   uzel_t** pom;
   for(pom=&strom;*pom!=NULL&&(*pom)->cislo!=cislo;pom=cislo>(*pom)->cislo?&((*pom)->pravy):&((*pom)->levy));
   if(*pom==NULL){
      *pom = new uzel_t;
      (*pom)->cislo = cislo;
      (*pom)->levy = NULL;
      (*pom)->pravy = NULL;
   }
   return *pom;
}
uzel_t* hledej(uzel_t* strom, int cislo){
   uzel_t* pom;
   for(pom=strom;pom!=NULL&&pom->cislo!=cislo;pom=cislo>pom->cislo?pom->pravy:pom->levy);
   return pom;
}

Mazání prvku by se implementovalo obdobně, stačilo by přidat jeden cyklus navíc.

Teď je vhodný čas pro druhou část článku – proč je toto řešení efektivnější než rekurze? Odpověď je jednoduchá – kvůli nižším paměťovým nárokům. Celému algoritmu stačí malé místo na stacku pro volání funkce a její argumenty a pro jeden pomocný ukazatel, víc nepotřebuje.

Kdežto při rekurzivním volání funkce se při každém volání alokuje na stacku kus paměti pro režijní věci, pro argumenty funkce a pro všechny její lokální proměnné. To se stane při každém volání funkce a zabraná paměť se začne uvolňovat až když rekurze dojde na konec a vrací se zas zpátky.

Při iterativním řešení si veškerou paměť alokujeme sami – což je výhoda pokud žádnou nepotřebujeme (pak rekurze zbytečně zabírá paměť aniž by to mělo nějaký užitek), ale nevýhoda pokud ano (rozeberu za chviličku). Jinak jsou však obvykle obě řešení volně zaměnitelná – krom výjimečných případů (zatím jsem žádný takový v praxi nepotkal) problém který lze řešit rekurzivně je řešitelný i iterativně a naopak. Jediný rozdíl je tedy práce s pamětí.

Síla rekurze je právě v tom, že při každém volání funkce se alokuje paměť na stacku, což je extrémně rychlé (systém jen posune vrchol zásobníku), kdežto při iteraci si potřebnou paměť musíme alokovat sami a tato paměť se alokuje na heapu, což je výrazně pomalejší (a také hrozí fragmentace paměti).

Obecné pravidlo (spíše orientační než absolutní – vždy záleží na konkrétním kontextu a programátorovi) tedy zní – iteraci použít tam, kde není třeba ukládat si pomocná data při každém kroku výpočtu, rekurzi tam kde to potřeba je. Dobrým příkladem je AVL strom. Při vkládání prvku do AVL stromu musíme po jeho vložení procházet zpět navštívené uzly a vyvažovat je, přičemž v nejhorším případě se při zpětném chodu můžeme dostat až ke kořeni stromu. Při použití iterace by bylo třeba si navštívené uzly ukládat do zásobníku a po vložení prvku tento zásobník procházet – u rekurze za nás toto v podstatě udělá systém sám, tím jak funguje volání funkcí (viz. výše). Takové řešení by bylo nejen pomalejší, ale také z hlediska kódu komplikovanější a nepřehlednější, zatímco rekurze by byla rychlá, elegantní a intuitivní.

Publikováno 27.12.2007 18:23 v sekci IT
Trvalý odkaz
Komentářů: 2 (Zobrazit komentáře)