V této kapitole se zamyslíme nad tím, ve kterých situacích potřebujeme dynamickou správu paměti.

Pracujeme-li s daty, jejichž rozsah je předem znám, obvykle vystačíme se statickým přidělováním paměti. To znamená, že již při překladu programu lze určit, kde v paměti budou data umístěna a jakou velikost budou zabírat. Například v jazyce C je paměť pro veškeré proměnné deklarované na globální úrovni nebo označené klíčovým slovem static přidělována staticky. Podobně v následujícím programu v jazyce Pascal, jenž určí počty jednotlivých písmen malé abecedy ve vstupním textu, je pro proměnné pismena a c paměť přidělena staticky:

program Test(input, output);
var pismena: array ['a'..'z'] of Integer;
    c: Char;
begin
   for c := 'a' to 'z' do 
      pismena[c] := 0;
   while not Eof do begin
      Read(c);
      if c in 'a'..'z' then pismena[c] := pismena[c]+1
   end
   for c := 'a' to 'z' do 
      WriteLn('Znak "', c, '" => počet ', pismena[c])
end.

Pokud však není velikost nebo počet položek konkrétní datové struktury v době překladu známý, musíme použít dynamické přidělování paměti. Paměť je v tomto případě vyhrazena až za běhu programu, obvykle na základě volání speciální funkce nebo použitím operátoru pro přidělení paměti. V následující ukázce v C++ se na základě hodnoty parametru delka přidělí paměť pro vektor této délky a jeho složky se inicializují na nulu.

int* vytvor_vektor(int delka)
{
   int* vektor = new int[pocet];
   for(int i = 0; i < pocet; i++) 
      vektor[i] = 0;
}

	Úkol k zamyšlení
	Jakým způsobem se přiděluje paměť pro proměnné deklarované uvnitř funkce a pro parametry funkce, známe-li jejich velikost a počet již v době překladu? Je tato podmínka dostatečná pro statické přidělení?

Uvažujeme-li možnost rekurzivního volání funkcí, pak pro lokální proměnné a parametry funkce nemůžeme paměťový prostor přidělit staticky. Nevíme totiž, kolikrát bude v konkrétním okamžiku díky rekurzi konkrétní proměnná v paměti existovat. Každé volání funkce má obvykle své vlastní proměnné, jejichž hodnoty se mohou měnit zcela nezávisle na hodnotách stejně pojmenovaných proměnných z jiných volání téže funkce. Nevíme tedy, kolik současných výskytů jedné proměnné bude existovat - to je závislé na počtu úrovní rekurzivního volání. Paměť pro tyto proměnné tedy musíme přidělit dynamicky, vždy v okamžiku volání podprogramu.

Například při výpočtu hodnoty faktoriálu bude funkce faktorial volána rekurzivně až do úrovně dané hodnotou argumentu n. Prostor pro parametr n tedy musí být přidělen dynamicky, i když jeho velikost známe předem.

int faktorial(int n)
{
   return n == 0 ? 1 : n * faktorial(n-1);
}

Pro dynamické přidělování paměti existuje mnoho metod, které se od sebe liší jednak efektivitou využití paměti, která je pro vyhodnocení programu dostupná, jednak velikostí časové a prostorové režie, která se na správu paměti spotřebuje. V této kapitole se těmto algoritmům budeme věnovat podrobněji a ukážeme si, jak se používají v prostředí konkrétních programovacích jazyků a jak se jejich implementace na vlastnostech těchto jazyků projeví.