10 - Rekurzivní funkce, sdílené knihovny

• pro vyučující: 10

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

Nápověda...

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

Nápověda...

• Napište funkci, která vypíše zadaný vstup (do \n) po zpátku.

Nápověda...

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

Poznámka...

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

Řeš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.

• Vytvořte program, který rekurzivně rozmístí n dam na šachovnici o velikosti n, vizte 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 Jezdcovu procházku.

• Č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.

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:

int fib (int i);

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

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

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

int main (){
  return fib(30);
}

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.

gcc -c -o fib.o fib.c
gcc -o main main.c fib.o
./main
echo $?

• 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).

gcc -shared -fPIC -o libfibit.so fibit.c
gcc -shared -fPIC -o libfibrec.so fibrec.c

• 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.)

cp libfibrec.so libfib.so

• 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.

gcc -o main -Wl,-rpath=. -L. -lfib

• 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á.

time seq 40 | main > fib_recursion.txt

• Pomalou rekurzivní implementaci můžeme nahradit efektivnější iterativní implementací, aniž bychom museli kompilovat náš program:

cp libfibit.so libfib.so && time seq 40 | main > fib_interation.txt

• 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 TLDP, cprogramming.com, Geeks for Geeks, nebo manuál dynamického linkeru na FreeBSD.

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

int my_strlen(char*);

• 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.)

#ifndef HEADER_GUARD_MY_STRLEN_H
#define HEADER_GUARD_MY_STRLEN_H 1
int my_strlen(char*);
#endif