{{indexmenu_n>10}}
====== 10 - Rekurzivní funkce, sdílené knihovny ======

  * pro vyučující: [[courses:b0b36prp:internal:tutorialinstruction:10|]]


===== Rekurzivní funkce =====

<note important>Při rekurzivním řešení výpočetního problému volá funkce seba sama, proto je důležité definovat ukončovací podmínku, kdy k volání už nedojde a naopak se vracíme z volaných funkcí. Typicky má funkce nějaký argument, který tak v podstatě hraje roli řídicí proměnné, podobně jako v cyklu.</note>
==== Úkoly ====

  * Napište rekurzivní funkci, která vypíše $n$-krát text "Hello world", kde $n$ je vstupní parametr. 

++++ Nápověda... | Funkce ''main'' nechť načte uživatelův vstup ''n'' a zavolá funkci ''my_print(n)''. Funkce ''void my_print (int n)'' vytiskne "Hello world\n" a pokud je předaná hodnota ''n'' je větší než ''1'', zavolá sebe sama s ''n-1''. ++++

  * Napište rekurzivní funkci, která vrátí délku textového řetězce (stejně jako ''strlen()'').

++++ Nápověda... | Funkce ''main'' načte zadaný text a předá ho funkci ''my_strlen(n,0)''. Funkce ''int my_strlen (char* s, int l)'' se podívá na ''l''-tý znak v ''s''. Pokud se jedná o ''\0'', vrátí ''l''. Jinak vrátí výsledek volání sebe sama s ''l+1''. Případně oddělte první volání jako ''my_strlen(char*)'' a další volání jako ''my_strlen_body(char*, int)''++++

  * Napište funkci, která vypíše zadaný vstup (do \''n'') po zpátku.
++++ Nápověda... | Protože cvičíme rekurzi, odpustíme si složité načítání a alokování paměti a využijeme rekurzivního volání funkce, která bude rekurzivně načítat jeden znak ''getchar()'' a následně vytiskne načtený znak. Volání končí pokud dojde k chybě nebo je načten konec řádku ''\0''.  ++++


  * Způsobte přeteční zásobníku (stack overflow) a zjistěte kolik rekurzivních volání bylo potřeba.

++++ Poznámka... |

Přetečení zásobníku znamená, že při definici lokálních proměnných nebo volání funkcí dojde prostor pro uložení hodnot na zásobníku a přistupovali bychom mimo přidělený paměťový prostor. To typicky způsobí chybu //Segmetation fault// bez dalšího upozornění, stejně jako při nesprávné práci s dynamicky alokovanou pamětí. Pro ladění programu můžeme použít alternativní správce paměti nebo programu ''valgrind'', který umí vysvětlit situaci detailněji...

++++

<note tip>Inspirujte se například příkladem z přednášky [[courses:b0b36prp:lectures:start|lec05]].</note>

  * Nástrojem ''ulimit'' změňte velikost zásobníku programu.

++++ Řešení... |

''ulimit -a'' zobrazí aktuální nastavení. ''ulimit -s <velikost>'' nastaví velikost stacku nově spuštěných programů.

++++

==== Další úkoly na procvičení rekurze (na konec cvičení) ====

  * Vygenerujte pomocí rekurzivní funkce všechna $k$-ciferná čísla obsahující pouze zadané číslice. Například pro délku 2 a pole číslic {1,2,7} bude výsledek: ''11, 12, 17, 21, 22, 27, 71, 72, 77''.

/*
++++ Nápověda... | 

Vaše funkce dostane pole znaků ''p'', které jsou k dispozici, jejich počet ''n'' (délku pole ''p'') a požadovaný řád čísla ''r''.

++++
*/

  * Vytvořte program, který rekurzivně rozmístí n dam na šachovnici o velikosti n, vizte [[https://en.wikipedia.org/wiki/Eight_queens_puzzle|Eight queens puzzle]]. 
  * Vypište počet všech možných kombinací rozmístění dam pro různé velikosti šachovnice 	
  * Vymyslete, jak upravit program, aby našel [[https://cs.wikipedia.org/wiki/Jezdcova_proch%C3%A1zka|Jezdcovu procházku.]]	





===== (Sdílené) knihovny =====

  * Často používaný univerzální kód se typicky vyjímá z daného projektu do knihovny, aby šel použít i v jiných projektech. Procvičte si, co jsou to vlastně knihovny a jak se s nimi pracuje.
  * Připomeňte si proces kompilace: Preprocesor - Překlad - Linkování - Načtení (spuštění). Při překladu vznikne soubor, který obsahuje binární kód se symboly, které slouží pro fázi linkování. Tyto symboly mohou reprezentovat nějakou knihovní funkci nebo externí proměnnou, jejíž definice zatím není k dispozici.
  * Při statickém linkování se všechny tyto symboly "nahradí" binárním kódem z knihovního "object file" a všechny potřebné binární kódy se pak zapíší do jednoho výsledného souboru.
  * Při dynamickém linkování se vybrané symboly pouze speciálně označí a až při spuštění programu systémový dynamický linker najde a načte správný knihovní binární kód.
==== Motivační příklad: Fibonacciho posloupnost ====

Výpočet Fibonacciho posloupnosti je již jednou známý a dále neměnný. Nemá smysl jej pořád implementovat odznovu, proto jej chceme zařadit do knihovny, kterou budeme přepoužívat. Chceme, aby nám knihovna uměla vypočítat $n$-tý člen posloupnosti. Deklaraci (rozhraní) této funkcionality napíšeme do hlavičkového souboru ''fib.h'':

<code c>
int fib (int i);
</code>

Implementaci (definici) pak napíšeme do zdrojového souboru ''fib.c'':

<code c>
#include "fib.h"
int fib (int i){
  ... // TODO: Implement me :-)
}
</code>

Knihovnu pak můžeme použít v našem programu ''main.c'', který spočítá třicáté Fibonacciho číslo:

<code c>
int main (){
  return fib(30);
}
</code>

Nyní vše stačí zkompilovat. Knihovnu zkompilujeme s přepínačem ''-c'', což vytvoří nespustitelný "object file" ''fib.o''. Druhý příkaz zkompiluje soubor ''main.c'' a načte již hotový ''fib.o'' a "spojí" je dohromady do spustitelného souboru ''main''.

<code bash>
gcc -c -o fib.o fib.c
gcc -o main main.c fib.o
./main
echo $?
</code>


<note tip>Rozdělování kódu do menších kompilačních jednotek je také výhodné pro šetření času při kompilaci rozsáhlého projektu.
Nástroje jako [[https://www.gnu.org/software/make/manual/make.html|make]], [[https://ninja-build.org/|ninja]] nebo [[https://cmake.org/|cmake]] slouží k organizaci kompilačních jednotek a kompilačních příkazů a zajištění, že se překompiluje vždy jen to, co je zrovna potřeba.</note>
==== Sdílené knihovny: Porovnání efektivity implementací Fibonacciho posloupnosti ====

<note tip>Inspirujte se například příkladem z přednášky [[courses:b0b36prp:lectures:start|lec07]].</note>


  * Porovnejte efektivitu výpočtu Fibonacciho posloupnosti implementovaného interací a rekurzí.
  * Obě verze algoritmu napište jako implementace knihovny ''fib.h'' do ''fibit.c'', resp. ''fibrec.c'' a zkompilujte jako sdílenou knihovnou ("shared object files")  'libfibit.so' a 'libfibrec.so' (přepínače ''-fPIC -shared'').

<code bash>
gcc -shared -fPIC -o libfibit.so fibit.c
gcc -shared -fPIC -o libfibrec.so fibrec.c
</code>

  * Rekurzivní verzi knihovny vezmeme jako výchozí ''libfib.so''. (Představme si, že vývojář byl líný a implementaci "odbyl". Do světa se proto dostala neefektivní rekurzivní varianta, kterou záhy použijeme v našem programu.)

<code bash>
cp libfibrec.so libfib.so
</code>

  * Vytvořte program ''main.c'', který načte seznam čísel, a využije knihovnu ''fib.h'', aby pro každé načtené číslo $n$ spočítal $n$-té Fibonacciho číslo.
  * Program ''main.c'' přeložte a slinkujte proti ''libfib.so''.
<code bash>
gcc -o main -Wl,-rpath=. -L. -lfib
</code>
  * Příkazem ''ldd main'' zkontrolujte, že dynamický linker správně najde naší knihovnu.
  * Nyní spusťte program a změřte jak dlouho se vykonává.
<code bash>
time seq 40 | main > fib_recursion.txt
</code>
  * Pomalou rekurzivní implementaci můžeme nahradit efektivnější iterativní implementací, aniž bychom museli kompilovat náš program:
<code bash>
cp libfibit.so libfib.so && time seq 40 | main > fib_interation.txt
</code>

  * Pomocí příkazu ''readelf'' se můžeme podívat, jak vypadá obsah zkompilovaných souborů pokud linkujeme staticky nebo dynamicky.
  * Další čtení včetně informace o systémových konvencích pro hledání instalovaných knihoven např. na [[https://tldp.org/HOWTO/Program-Library-HOWTO/shared-libraries.html|TLDP]], [[https://www.cprogramming.com/tutorial/shared-libraries-linux-gcc.html|cprogramming.com]],  [[https://www.geeksforgeeks.org/working-with-shared-libraries-set-1/|Geeks for Geeks]], nebo [[https://man.freebsd.org/cgi/man.cgi?query=ld.so|manuál dynamického linkeru na FreeBSD]].


==== Header Guards ====

Knihovnu lze samozřejmě používat v mnoha překladových jednotkách našeho projektu. Například funkce pro práci s textovými řetězci se budou používat často a na mnoha místech. Programátorům stačí znát deklaraci knihovních funkcí v hlavičkovém souboru. Problém může nastat, pokud se deklarace z hlavičkového souboru během preprocessingu "vloží" do zdrojového kódu na více míst. Demonstrujte:

  * Dřívější implementaci ''my_strlen'' zabalte do knihovny ''my_strlen.c'' s hlavičkovým souborem ''my_strlen.h'', který obsahuje pouze

<code c>
int my_strlen(char*);
</code>


  * V souboru ''main.c'' i v ''fibit.c'' přidejte ''#include "my_strlen.h"''.
  * Zkusme zkompilovat Fibonacciho program. Uvidíme, že kvůli dvojitému vložení deklarace dojde k chybě.
  * V knihovně ''my_strlen.h'' je proto potřeba ošetřit tuto situaci pomocí "hlídacích maker". (Makra se mohou jmenovat jakkoliv, pokud nebudou kolidovat s jinými makry.)

<code c>
#ifndef HEADER_GUARD_MY_STRLEN_H
#define HEADER_GUARD_MY_STRLEN_H 1
int my_strlen(char*);
#endif
</code>