Rekurzivní funkce

Rekurzivní funkce je v podstatě jen funkce, která volá sama sebe. Rekurzivní funkce nejsou unikátní pro JavaScript - jedná se o velmi běžnou programovací techniku, která může být použita ve většině programovacích jazyků s funkcemi. Také v JavaScriptu neexistuje žádná speciální notace pro rekurzivní funkce, což znamená, že nemusíte přidávat speciální klíčové slovo k deklaraci funkce nebo cokoli podobného - pokud funkce volá sama sebe, považuje se za rekurzivní funkci.

Ale proč byste kdy potřebovali, aby funkce volala sama sebe? Ve skutečnosti existuje mnoho případů použití této techniky, zejména když začnete řešit složitější úkoly. Pro tento tutoriál začneme jednoduchým příkladem, abychom vám ukázali, jak fungují.

Jednoduchý příklad rekurze: Odpočítávání

Předpokládejme, že chcete provést jednoduché odpočítávání, kde začneme s číslem, ukážeme ho uživateli, snížíme hodnotu o 1 a pak ukážeme uživateli nové číslo. Chceme funkci, která uživateli zobrazí číslo. Bez použití rekurzivních funkcí by to mohlo vypadat takto:

function CountDown(number)
{
	alert(number + "!");	
}

let number = 3;

CountDown(number--);
CountDown(number--);
CountDown(number--);

Toto řešení funguje, ale rozhodně není příliš elegantní! Můžeme to snadno napravit proměněním toho na rekurzivní funkci, ale jak? Jak bylo zmíněno, rekurzivní funkce se musí jen sama volat, aby byla rekurzivní, ale musíte být opatrní, jak to děláte - musí být něco, co zastaví rekurzivní volání v určitém bodě, protože jinak skončíte s nekonečnou smyčkou, která pravděpodobně způsobí pád prostředí JavaScriptu (např. prohlížeče).

Podívejme se na rekurzivní verzi našeho příkladu odpočítávání:

function CountDown(number)
{
	alert(number + "!");
	number--;
	if(number > 0)
		CountDown(number);
}

let number = 3;
CountDown(number);

V našem příkladu je kontrola zastavení poměrně jednoduchá: Funkci CountDown() voláme rekurzivně pouze v případě, že naše číslo je větší než 0, čímž zajistíme, že funkce je řádně ukončena, jakmile je odpočítávání hotovo.

Všimněte si také, že nyní naše funkce zvládá vše, včetně snižování čísla při každé iteraci, což nám umožňuje funkci zavolat jednou a pak je o vše postaráno.

Složitý příklad rekurze: Stromová struktura

Uznávám, že výše uvedený příklad byl velmi jednoduchý, možná trochu nudný a nedostatečně ilustrativní v tom, jak mocná může rekurzivní funkce být. Chci to napravit ukázáním složitějšího příkladu, který také ilustruje něco, pro co se rekurze často používá: K vytvoření stromové struktury.

Rychlé varování: V tomto příkladu budu používat těžkou směs polí a objektů a některé techniky, které v tomto tutoriálu ještě nebyly plně pokryty. Pokud se vám toto zdá příliš pokročilé v této fázi vašeho učebního procesu, neváhejte tento příklad přeskočit a vrátit se k němu později.

Stromové struktury se na počítačích používají poměrně často k ilustraci hierarchických dat, ale také ve skutečném světě, jako je rodinný strom atd. Pokud jste s počítači pracovali více než pár hodin, pravděpodobně jste viděli jeho složky a soubory zobrazené jako stromová struktura.

Pro můj příklad bych chtěl vzít nějaká hierarchická data, reprezentující (některé z) složky a soubory nalezené na počítači s Windows, a zobrazit je jako strom. V mém příkladu je vizuální reprezentace jen velmi jednoduchý strom pouze s textem, ale snadno byste ji mohli oživit vizuálně přidáním ikon atd. Takto to bude vypadat:

C:
----Program Files
--------Common Files
------------start.exe
------------readme.txt
----Windows
--------System32
------------Drivers
--------explorer.exe
--------notepad.exe
T:
----Data
----Secret Stuff

Opravdu jednoduchý strom, opravdu jednoduchý obsah, jaký lze najít na mnoha počítačích s Windows. Složky a soubory jsou uvedeny podle jejich názvu, a pokud mají jakékoli podsložky a/nebo soubory, jsou uvedeny níže s přidaným odsazením, aby bylo signalizováno, ke které nadřazené složce patří.

Pro generování tohoto potřebujeme funkci, která vezme pole položek, vytiskne názvy a pro každou položku také vytiskne její dětské položky (pokud nějaké má). Musí to dělat opakovaně, dokud neprojde všemi položkami a všemi dětskými položkami. Jinými slovy, potřebujeme rekurzivní funkci. Takto by to mohlo vypadat:

function PrintTree(items, level)
{		
	for(let item of items)
	{
		let indentation = "-".repeat(level * 4);
		console.log(indentation + item.name);		
		if(item.items != null)
			PrintTree(item.items, level + 1);
	}
}

Všimněte si, kolik málo řádků potřebujeme k vygenerování toho velkého stromu. Funkce je dokonce velmi jednoduchá - jak bylo slíbeno, pouze vypíše název s odpovídajícím množstvím odsazení. Odsazení založíme na aktuální úrovni, začínáme s 0, a pro každou úroveň stromu inkrementujeme proměnnou úrovně a předáme ji, když rekurzivně voláme funkci PrintTree(). Proměnnou úrovně používáme k vygenerování řetězce odsazení, který je jen hromada pomlček.

Takže s tím na místě se podívejme na kompletní příklad, kde kombinujeme stromová data ve formě objektů v polích s právě ukázanou funkcí:

let fileFolderTree = 
[
	{
		name: "C:",
		items:
		[
			{
				name: "Program Files",
				items:
				[
					{
						name: "Common Files",
						items:
						[
							{
								name: "start.exe"
							},
							{
								name: "readme.txt"
							}
						]
					}
				]
			},
			{
				name: "Windows",
				items: 
				[
					{
						name: "System32",				
						items: 
						[
							{
								name: "Drivers"
							}
						]
					},
					{
						name: "explorer.exe"
					},
					{
						name: "notepad.exe"
					}
					
				]
			}
		]
	},
	{
		name: "T:",
		items: 
		[
			{
				name: "Data"
			},
			{
				name: "Secret Stuff"
			}
		]
	}	
];


function PrintTree(items, level)
{		
	for(let item of items)
	{
		let indentation = "-".repeat(level * 4);
		console.log(indentation + item.name);		
		if(item.items != null)
			PrintTree(item.items, level + 1);
	}
}

PrintTree(fileFolderTree, 0);

Jak vidíte, vyžaduje to poměrně hodně kódu, aby obsahovalo všechny složky a soubory jako hierarchický soubor dat. Obvykle by to přišlo přímo z podkladového systému, ale protože k tomu z JavaScriptu-prohlížeče nemáme přístup, vytvořil jsem nějaká data, se kterými můžeme pracovat.

Po všech datech máme rekurzivní funkci nazvanou PrintTree(), o které jsme již mluvili. Na úplně posledním řádku máme naše jednoduché volání rekurzivní funkce, které to všechno rozhýbe - stačí ji zavolat jednou, protože si bude jistě volat sama sebe tolikrát, kolik bude potřeba. Jednoduše předám naše data a první úroveň (0) a naše rekurzivní funkce se postará o zbytek.

Shrnutí

Když funkce volá sama sebe, označuje se to jako rekurzivní funkce. A jak můžete vidět z příkladů tohoto článku, to může být opravdu užitečné. Rekurzivní funkce, které jsou běžnou programovací technikou a nejsou specifické pro JavaScript, se nepoužívají pořád, ale jsou extrémně praktické, když potřebujete řešit konkrétní problémy, např. při práci s hierarchickými daty.