9 - Rekurzivní funkce, sdílené knihovny

Cíle cvičení

  • Rekurze a Stack memory (vs Heap memory).
  • Vytvoření a prolinkování sdílené knihovny.

Rekurzivní funkce

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.

Úkoly - Rekurzivní volání a ukončení

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

Úkoly - Stack vs Heap paměť

  1. Napište rekurzivní funkci revert(), která pomocí getchar() načte přesměrovaný vstup (končící EOF) a pomocí putchar() jej vypíše po zpátku. Nápověda...
  2. V debug spuštění odkrokujte jednotilvá rekurzivní volání funkce a pozorujte změnu stavu v zásobníku (Call stack). Příklad
  3. Způsobte přeteční zásobníku (stack overflow). Poznámka...
  4. Napište funkci revert_h() se stejnou funkčností jako revert(), ale s použitím cyklu a alokace paměti. Pokud nemáte alokované načítání znaků po ruce tak...
  5. Experimentujte a diskutujte rozdíly mezi funkčně stejnými, ale technicky odlišnými funkcemi revert() a revert_h().

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:

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 $?

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 make, ninja nebo 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.

Sdílené knihovny: Porovnání efektivity implementací Fibonacciho posloupnosti

Inspirujte se například příkladem z přednášky lec07.
  • Porovnejte efektivitu výpočtu Fibonacciho posloupnosti implementovaného iterací 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 main.c -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

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

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

Pokročilé úlohy

  • 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.
courses/b0b36prp/labs/lab09.txt · Last modified: 2024/11/24 23:58 by feberja1