Problème — Faire tourner une image

Problème — Faire tourner une image.

Une image carrée de $n\times n$ pixels, avec $n$ puissance de $2$, est représentée par une liste de $n$ lignes, chaque ligne étant une liste de $n$ pixels. On veut la faire tourner d'un quart de tour dans le sens des aiguilles d'une montre, par la méthode « diviser pour régner » :

• on découpe l'image en quatre quarts : A (haut gauche), B (haut droite), C (bas gauche), D (bas droite) ;
• on fait tourner chaque quart, récursivement ;
• on recompose l'image en déplaçant les quarts.

• Dans un quart de tour horaire, où vont les quarts A, B, C et D ?
• Écrire la fonction récursive rotation(M) qui renvoie l'image tournée, et la tester sur la matrice $4\times 4$ des nombres de $1$ à $16$ écrits ligne par ligne.
• Évaluer le coût en fonction du nombre de pixels $N=n^2$.