Pour progresser...

Exercice 1 : Longueur de chaînes de caractères

Question

Soit une chaîne de caractères, écrire un algorithme récursif permettant de déterminer sa longueur.

Indice

Une chaîne vide doit renvoyer 0...

Solution

1
def longueur(ch):
2
    if not ch:
3
        return 0
4
    else:
5
        return 1+longueur(ch[1:])
6
7
8
ma_chaine = "Hello World!"
9
print(longueur(ma_chaine))

Exercice 2 : Représentation binaire d'un nombre décimal

Pour convertir un nombre entier positif N de la base décimale à la base binaire, il faut opérer par des divisions successives du nombre N par 2. Les restes des divisions constituent la représentation binaire.

Illustration d'une fonction binaire( )Informations[1]

Question

Écrire une fonction récursive binaire() permettant d’imprimer à l’écran la représentation binaire d’un nombre N.

Indice

On pourra utiliser soit des chaines de caractères, soit des listes pour renvoyer le résultat.

Solution

1
def binaire(N):
2
	if N == 0:
3
		return ''
4
	else:
5
		return str(binaire(N//2)) + str(N % 2)
6
7
print(binaire(128))
Exercice 3 : Palindrome
Un mot est un palindrome si on peut le lire dans les deux sans de gauche à droite et de droite à gauche.
Exemple KAYAK est un palindrome.
Question
Écrire une fonction récursive palindrome(), renvoyant True ou False, permettant de vérifier si un mot est palindrome.
La casse ne sera pas prise en compte.
Indice
On peut commencer à comparer la première et la dernière lettre, puis ainsi de suite...
Solution
1
def palindrome(ch):
2
    if len(ch) == 1 or len(ch)==0:
3
        return True
4
    if ch[0] == ch[-1]:
5
        return palindrome(ch[1:len(ch)-1])
6
    return False
7
 
8
 
9
mot = "KAYAK"
10
print(palindrome(mot))
Exercice 4 : Maximum d'un tableau
Nous allons utiliser la notion de recherche dichotomique :
  • on coupe notre tableau en 2
  • on recherche notre maximum dans chacun des tableaux...
Question
Soit un tableau X de N entiers, écrire une fonction récursive simple permettant de déterminer le maximum du tableau.
Indice
Le principe est donc de couper notre tableau en 2 sous-tableau et de tester si le maximum se trouve dans le tableau de gauche ou de droite...
Solution
1
def maximum(T):
2
	if len(T) == 1:
3
		return T[0]
4
	m = len(T)//2
5
	max1 = maximum(T[:m])
6
	max2 = maximum(T[m:])
7
	if max1 > max2:
8
		return max1
9
	return max2
10
11
tab = [1, 10, 3, 4, 5, 6, 7, 8, 9]
12
print(maximum(tab))
13
Exercice 5 : Tableau trié ?
Un tableau X est trié par ordre croissant si \(x(i) \leq x(i+1), \forall i\).
Question
Écrire une fonction récursive est_trie( ) permettant de vérifier qu’un tableau X est trié ou non.
Indice
Commençons par tester les premiers éléments et ensuite réduisons notre tableau avec un nouveau appel de la fonction est_trie()
Solution
1
def est_trie(T):
2
    if len(T) == 0 or len(T) == 1:
3
        return True
4
    if T[0] <= T[1]:
5
        return est_trie(T[1:])
6
    return False
7
 
8
 
9
tab = [1, 2, 3, 4, 4, 5, 7, 8]
10
print(est_trie(tab))