10 - Rekurzivní funkce, sdílené knihovny

• pro vyučující

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

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.

• Napište program, který provede součet cifer celého čísla, např.

Např.

1234 -> 10
4135 -> 13
1516 -> 13
1361 -> 11
39831 -> 24

Nápověda

int sum_of_digits(int n);
 
int main(void)
{
   int vals[] = { 1234, 4135, 1516, 1361, 39831 };
   for (int i = 0;  i < 5; ++i) {
      printf("%d -> %d\n", vals[i], sum_of_digits(vals[i]));
   }
   return 0;
 
}
 
int sum_of_digits(int n)
{   
   if (n == 0) {
      return 0;
   } else {
      return // digit sečteme s výsledkem volání sum_of_digits pro další digit
   }
}

• Napište program, který vypíše textový řetězec po zpátku, např.

Např.

1234 -> 4321
hello -> olleh
a b c -> c b a
PRP -> PRP
I like PRP -> PRP ekil I

Nápověda

#include <stdio.h>
 
void print_reverse(char *str);
 
int main(void)
{
   char *strings[] = { "1234", "hello", "a b c", "PRP", "I like PRP", NULL};
   char **cur = strings;
   while (*cur) {
      printf("%s -> ", *cur);
      print_reversed(*cur);
      cur += 1;
      putchar('\n');
   }
   return 0;
}
 
void print_reversed(char *str) {}

• Napište program, který otestuje zdali je textový řetězec palindromem, např.

Is palindrom "1234" -  no
Is palindrom "-121" -  no
Is palindrom "121" -  yes
Is palindrom "abba" -  yes
Is palindrom "abca" -  no
Is palindrom "A man, a plan, a canal: Panama!" -  no

Nápověda

#include <stdio.h>
#include <string.h>
 
_Bool is_palindrom(const char *str);
 
int main(void)
{
   char *strings[] = { "1234", "-121", "121", "abba", "abca", "A man, a plan, a canal: Panama!", NULL };
   char **cur = strings;
   while (*cur) {
      printf("Is palindrom \"%s\" -  %s\n", *cur, is_palindrom(*cur) ? "yes" : "no");
      cur += 1;
   }
   return 0;
}
 
static _Bool isPalindrom(const char *str, int start, int end)
{  
   ....
}
 
_Bool is_palindrom(const char *str)
{
   return isPalindrom(str, 0, strlen(str) - 1);
}

• Upravte program tak, aby test zoohledňoval pouze znaky abecedy (is_alpha() zknihovny ctype.h). Bude v takové případě poslední řetězec v příkladu palindromem?

• Vytvořte program, který vypíše všechny permutace znaků v řetězci, např.

Permute "12"
12
21

Permute "abc"
abc
acb
bac
bca
cba
cab

Nápověda

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
void permute(char *str);
 
int main(void) 
{
   char strings[][4] = { "12", "abc", "\0"}; //2D pole znaků, proto "\0".
 
   for (char (*cur)[4] = (char (*)[4])strings; cur[0][0]; cur += 1) {
      permute(*cur);
   }
   return 0;
}
 
static void swap(char *a, char *b)
{
 char t = *b;
 *b = *a;
 *a = t;
}
 
static void print_permutation(char *str, int l, int r) { ... }
 
void permute(char *str)
{
   printf("Permute \"%s\"\n", str);
   print_permutation(str, 0, strlen(str) - 1);
   putchar('\n');
}

• Proč je nutné řetězce alokovat jako 2D pole znaků a nkoliv jako pole ukazatelů na texotvé literály?

  char *strings[] = { "12", "abc", "\0"};

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

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... Využijte rekurzivní volání funkce, která bude rekurzivně načítat jeden znak a následně vytiskne načtený znak.
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...

   Zasobnik ma k dispozici relativne malo pameti. Staci zjistit jaky je jeji limit a ten prekrocit
   $ ulimit -s
   8192
   $ tr -dc A-Za-z < /dev/urandom | head -c 20000000 > file_big
   $ tr -dc A-Za-z < /dev/urandom | head -c 5 > file_small
   $ cat file_small; echo
   QzaFT
   $ ./main < file_small; echo
   TFazQ
   $ ./main < file_big; echo
   Segmentation fault (core dumped)

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

   char* read_input(size_t *index, size_t *size) {
       *size = 10;
       *index = 0;
       char *chars = (char *)malloc(sizeof(char)* *size);
       if (chars == NULL) {
           printf("Memory allocation failed\n");
           return NULL;
       }
       char buff;
       while ((buff = getchar()) != EOF) {
           chars[*index] = buff;
           (*index)++;
           if (*index == *size) {
               *size *= 2;
               char* chars_ = (char *)realloc(chars, sizeof(char)* *size);
               if (chars_ == NULL) {
                   free(chars);
                   printf("Memory reallocation failed\n");
                   return NULL;
               }
               chars = chars_;
           }
       }
       return chars;
   }

5. Experimentujte a diskutujte rozdíly mezi funkčně stejnými, ale technicky odlišnými funkcemi revert() a revert_h().

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

• 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

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