Récursivité

1. Écrire une fonction récursive int palindrome_rec(char str[], int lo, int hi) qui détermine si la chaîne de caractères str entre les indices lo et hi est un palindrome. La fonction renvoie 1 si elle l'est et 0 sinon. La chaîne vide (lo > hi) est considérée comme un palindrome.
   
   Par exemple, a, aba, abba, radar et esoperesteetserepose sont des palindromes.
2. Écrire une fonction wrapper int palindrome(char str[]) qui appelle la fonction précédente avec les bons paramètres.

On veut écrire des fonctions récursives qui affichent les n premiers entiers positifs séparés par des espaces. Ce n'est pas nécessaire de retourner à la ligne.

1. Écrire une fonction récursive void increasing_sequence_rec(int n) qui affiche les entiers de 1 à n séparés par des espaces.
2. Écrire une fonction récursive void decreasing_sequence_rec(int n) qui affiche les entiers de n à 1 séparés par des espaces.

On veut écrire des fonctions qui comptent le nombre d'occurrences dans un tableau t. Les indices lo et hi indiquent la partie du tableau qui sera prise en compte.

1. Écrire une fonction récursive int count(int t[], int lo, int hi, int elt) qui compte et renvoie le nombre d'occurrences de l'élément elt dans le tableau t.
2. Écrire une fonction récursive int max_count(int t[], int lo, int hi) qui renvoie le nombre maximal d'occurrences d'un élément dans le tableau t.
   
   Par exemple pour le tableau [1, 4, 3, 3, 2, 3, 3, 4], la fonction max_count renverra 4 comme l'élément 3 est le plus fréquent ayant 4 occurrences.

On souhaite écrire une fonction qui prend en argument un entier positif n et qui calcule la somme des chiffres qui le forment.

Par exemple la somme des chiffres qui forment 912942 est 27.

1. Écrire une fonction itérative int sum_digits_iter(int n) qui calcule cette valeur.
2. Écrire une fonction récursive int sum_digits_rec(int n) qui calcule cette valeur.

On souhaite maintenant écrire une fonction qui répète le calcul précédent (somme des chiffres) sur son résultat tant que ce résultat est un nombre qui n'est pas un chiffre.

Par exemple, la somme des chiffres de 912942 est 27 mais on souhaite ici obtenir 9, qui est la somme des chiffres de 27. Pour 99992, on veut que cette nouvelle fonction donne 2 qui est la somme des chiffres de 11, 11 étant la somme des chiffres de 38, lui-même est la somme des chiffres de 99992...

On cherche la longueur de la plus longue suite croissante dans un tableau t. Une suite d'entiers t[a], t[a+1], ..., t[b-1], t[b] est croissante si t[a] < t[a+1] < ... < t[b-1] < t[b].

Exemples :

Pour le tableau [1, 2, 3, 2, 4, 6, 8, 3], la fonction renverra 4 comme la suite la plus longue est 2, 4, 6, 8.
Pour le tableau [1, 2, 3, 1, 2, 3, 4, 5], la fonction renverra 5 comme la suite la plus longue est 1, 2, 3, 4, 5.

On cherche une fonction avec une complexité linéaire dans la taille du tableau. Elle devrait donc être rapide sur un tableau de longueur 1000000.

1. Écrire une fonction int longest_incr_iter(int t[], int lo, int hi) qui cherche la longueur de la plus longue suite croissante de manière itérative.
2. Écrire une fonction récursive int first_incr(int t[], int lo, int hi) qui renvoie la longueur de la suite croissante qui commence par t[lo]. Si lo > hi alors la fonction renvoie 0.
   
   Par exemple pour le tableau [1, 3, 5, 2, 3, 4, 5, 3], la fonction renverra 3 comme la suite croissante au début du tableau a la longueur 3.
3. En utilisant la fonction first_incr, écrire la fonction int longest_incr_rec(int t[], int lo, int hi) qui cherche la longueur de la plus longue suite croissante de manière récursive.
4. Modifiez vos fonctions pour qu'elles communiquent le premier indice de la suite la plus longue ainsi que sa longueur. Il y a (au moins) deux solution pour faire cela : soit vous passez l'adresse à l'indice et la longueur comme paramètres à la fonction, soit vous pouvez retourner une struct avec les deux informations.