cours_6.md

title: "Récursivité et complexité"
date: "2021-11-03"
patat:
  eval:
    tai:
      command: fish
      fragment: false
      replace: true
    ccc:
      command: fish
      fragment: false
      replace: true
  images:
    backend: auto
int factorial(int n) {
    if (n > 1) { // Condition de récursivité
        return n * factorial(n - 1);
    } else {     // Condition d'arrêt
        return 1;
    }
}

. . .

* Code impératif

    ```C
    int factorial(int n) {
        int f = 1;
        for (int i = 1; i < n; ++i) {
            f *= i;
        }
        return f;
    }
    ```

# Exercice: réusinage et récursivité (1/4)

## Réusiner le code du PGCD avec une fonction récursive

## Étudier l'exécution

```C
42 = 27 * 1 + 15
27 = 15 * 1 + 12
15 = 12 * 1 + 3
12 = 3  * 4 + 0
42 = 27 * 1 + 15   |   PGCD(42, 27)
27 = 15 * 1 + 12   |   PGCD(27, 15)
15 = 12 * 1 +  3   |   PGCD(15, 12)
12 =  3 * 4 +  0   |   PGCD(12,  3)
42 = 27 * 1 + 15   |   PGCD(42, 27)
27 = 15 * 1 + 12   |   PGCD(27, 15)
15 = 12 * 1 +  3   |   PGCD(15, 12)
12 =  3 * 4 +  0   |   PGCD(12,  3)
PGCD(12,  3)    |     3
PGCD(15, 12)    |     3
PGCD(27, 15)    |     3
PGCD(42, 27)    |     3
int pgcd(int n, int m) {
    if (n % m > 0) {
        return pgcd(m, n % m);
    } else {
        return m;
    }
}
int fib(int n) {
    if (n > 1) {
        return fib(n - 1) + fib(n - 2);
    }
    return n;
}
int fib_imp(int n) {
    int fib0 = 1;
    int fib1 = 1;
    int fib  = n == 0 ? 0 : fib1;
    for (int i = 2; i < n; ++i) {
        fib  = fib0 + fib1;
        fib0 = fib1;
        fib1 = fib;
    }
    return fib;
}
int pow(x, n) {
    if (0 == n) {
        return 1;
    }
    for (int i = 1; i < n; ++i) {
        x *= x;
    }
    return x;
}
int pow(x, n) {
    if (n != 0) {
        return x * pow(x, n-1);
    } else {
        return 1;
    }
}
double pow(double x, int n) {
    if (1 == n) {
        return x;
    } else if (n % 2 == 0) {
        return pow(x, n / 2) * pow(x, n/2);
    } else {
        return x * pow(x, (n-1));
    }
}
#include <time.h>
struct timespec tstart={0,0}, tend={0,0};
clock_gettime(CLOCK_MONOTONIC, &tstart);
// some computation
clock_gettime(CLOCK_MONOTONIC, &tend);
printf("computation about %.5f seconds\n",
       ((double)tend.tv_sec + 1e-9*tend.tv_nsec) -
       ((double)tstart.tv_sec + 1e-9*tstart.tv_nsec));
source_codes/complexity$ make bench
RUN ONCE -O0
the computation took about 0.00836 seconds
RUN ONCE -O3
the computation took about 0.00203 seconds
RUN THOUSAND TIMES -O0
the computation took about 0.00363 seconds
RUN THOUSAND TIMES -O3
the computation took about 0.00046 seconds
int sorted_list[N];
bool in_list = is_present(N, sorted_list, elem);
bool is_present(int n, int tab[], int elem) {
    for (int i = 0; i < n; ++i) {
        if (tab[i] == elem) {
            return true;
        } else if (elem < tab[i]) {
            return false;
        }
    }
    return false;
}
bool is_present_binary_search(int n, int tab[], int elem) {
    int left  = 0;
    int right = n - 1;
    while (left <= right) {
        int mid = (right + left) / 2;
        if (tab[mid] < elem) {
            left = mid + 1;
        } else if (tab[mid] > elem) {
            right = mid - 1;
        } else {
            return true;
        }
    }
    return false;
}
for (i = 2; i < sqrt(N); ++i) {
    if (N % i == 0) {
        return false;
    }
}
return true;
min = MAX;
for (i = 0; i < N; ++i) {
    if (tab[i] < min) {
        min = tab[i];
    }
}
return min;
ind = 0
while (ind < SIZE-1) {
    min = find_min(tab[ind:SIZE]);
    swap(min, tab[ind]);
    ind += 1
}