Informatique au lycée Faustin Fleret

Récursivité :

La récursivité est un concept qui est très proche de la notion mathématiques de la récurrence. On dit qu’une fonction est récursive si elle s’appelle elle-même.
Pour résoudre un problème ou effectuer un calcul, on se ramène à la résolution d’un problème similaire mais de complexité moindre. On recommence ainsi jusqu’à obtenir un problème élémentaire que l’on sait résoudre.

La plus-part des langages de programmation actuels permettent de mettre en œuvre directement cette réduction du problème, en autorisant une fonction à s’appeler elle-même : on parle alors de fonction récursive. On trouvera souvent deux versions possibles d'un même programme : itérative et récursive.

Cependant deux éléments sont indispensables à la terminaison d’une fonction récursive :

• il est nécessaire qu’il y ait une condition d’arrêt ;
• il ne doit pas y avoir de suite infinie d’appels récursifs.

Exemple :

def compte(n):
	if n >= 0:
		print(n)
		compte(n-1)
	return

• le test n ≥ 0 est une condition d’arrêt, obligatoire sinon le sous-programme peut boucler indéfiniment;
• la valeur de n est affichée si n est un nombre positif ou nul puis il y a un appel à la procédure elle-même en passant par le paramètre n −1, cet appel est dit récursif; la valeur n −1 passée en paramètre permet de faire décroître la valeur de n pour que le sous-programme ne boucle pas indéfiniment;
• la valeur de n −1 est affichée si n −1 est un nombre positif ou nul puis il y a un appel à la procédure elle-même en passant le paramètre n −2;
• les appels récursifs continuent jusqu’à ce que le paramètre passé à la procédure prenne la valeur −1;
• la dernière valeur affichée est donc 0.

Affichage de "4", appel de compte(3),
	Affichage de "3", appel de compte(2),
		Affichage de "2", appel de compte(1),
			Affichage de "1", appel de compte(0),
				Affichage de "0", appel de compte(−1)    ### Le test n’est plus vérifié, c’est terminé.

def factorielle_iterative(n):
		"""
		Entrée : n - entier positif
		Sortie : entier - produit des entiers de 1 à n
		"""
		resultat = 1
		for i in range(2,n+1):
			resultat *= i
		return resultat

La multiplication du paysan russe

La méthode du paysan russe est un très vieil algorithme de multiplication de deux nombres entiers déjà décrit (sous une forme légèrement différente) sur un papyrus égyptien rédigé vers 1650 av. J.-C. Il s’agissait de la principale méthode de calcul en Europe avant l’introduction des chiffres arabes, et les premiers ordinateurs l’ont utilisé avant que la multiplication ne soit directement intégrée dans le processeur sous forme de circuit électronique.

Cet algorithme repose sur les relations :

On pourra trouver deux versions possibles d'un même programme : itérative et récursive.

def multiply(x, y):
    """
    entrée : x, y - entier positif
    sortie : entier - produit de x et y
    """
    p = 0		# Initialisation de la variable p, qui accumulera le résultat final  
    while x > 0 : # Boucle qui continue tant que x est strictement positif
        if x % 2 == 1: # Si x est impair, on ajoute y à p
            p += y       
        x = x // 2 # On divise x par 2 en utilisant la division entière
        y = y + y # On double la valeur de y   
    return p # Retourne le produit final accumulé dans p

def multiply_recursive(x, y):
    """
    entrée : x, y - entier positif
    sortie : entier - produit de x et y
    """
    if x <= 0:
        return ...
    elif ............ :
        return multiply_recursive(x // 2, y + y)
    else:
        return multiply_recursive(x // 2, y + y) + y