Search
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.
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.
main
n
my_print(n)
void my_print (int n)
1
n-1
strlen()
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)
my_strlen(n,0)
int my_strlen (char* s, int l)
l
s
\0
l+1
my_strlen(char*)
my_strlen_body(char*, int)
revert()
getchar()
EOF
putchar()
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)
revert_h()
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; }
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:
fib.h
int fib (int i);
Implementaci (definici) pak napíšeme do zdrojového souboru fib.c:
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:
main.c
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.
-c
fib.o
gcc -c -o fib.o fib.c gcc -o main main.c fib.o ./main echo $?
fibit.c
fibrec.c
-fPIC -shared
gcc -shared -fPIC -o libfibit.so fibit.c gcc -shared -fPIC -o libfibrec.so fibrec.c
libfib.so
cp libfibrec.so libfib.so
gcc -o main -Wl,-rpath=. -L. -lfib
ldd main
time seq 40 | main > fib_recursion.txt
cp libfibit.so libfib.so && time seq 40 | main > fib_interation.txt
readelf
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:
my_strlen
my_strlen.c
my_strlen.h
int my_strlen(char*);
#include “my_strlen.h”
#ifndef HEADER_GUARD_MY_STRLEN_H #define HEADER_GUARD_MY_STRLEN_H 1 int my_strlen(char*); #endif
11, 12, 17, 21, 22, 27, 71, 72, 77