T-3.2 Récursivité

Vous savez très bien utiliser une boucle for pour calculer une somme :

• On initialise la variable somme
• On itère
• Dans la boucle on ajoute les éléments

C'est un accumulateur. Exemple :

Exemple : Calculer la sommes des inverse des carrés des entiers de 1 à n

def sum_inverse_carres(n: int) -> float: """ :param n: un entier stictement positif :returns: un float : la somme des inverse des carrés : 1/1 + 1/2² + 1/3² + ... + 1/n² """ somme = 0 for i in range(1, n+1) : somme += 1/i**2 return somme print(sum_inverse_carres(4))

Pour la petite histoire, cette somme tend vers π²/6, cela peut être démontré mais ce n'est pas notre propos.

Il existe une autre façon de calculer cette somme. L'idée est la suivante :

On ajoute (dans somme) 1/n² puis la somme des inverses des carrés des entiers de 1 à n-1.

Mais en fait nous n'allons pas utiliser de variable somme. On va renvoyer le résultat. En fait on peut écrire :

Ce qui, dans le code, ce traduit par :

somme_inverse_carres(n) = 1/n**2 + somme_inverse_carres(n - 1)

Nous allons voir comment programmer cela. L'idée est donc que la fonction sum_inverse_carres s'appelle elle même. On désigne cela par le terme de fonction récursive.

Toutefois, il faut que le processus s'arrête.... Ici on appelle la fonction avec n-1 donc la valeur de l'argument décroit. Jusqu'où ???

En fait, dans tout programmation récursive on doit définir un cas de base, un cas simple où le résultat est trivial, et on peut renvoyer ce résultat sans rappeler la fonction.

Ici le cas de base est n = 1, et la valeur renvoyée dans ce cas est 1.

Exemple : version récursive du code précédent

def sum_inverse_carres(n: int) -> float: """ :param n: un entier strictement positif :returns: un float : la somme des inverses des carrés : 1/1 + 1/2² + 1/3² + ... + 1/n² """ # cas de base: if n == 1: return 1 # cas général: else : return 1/n**2 + sum_inverse_carres(n - 1) print(sum_inverse_carres(4))

Exercice 1 : somme des entiers de 0 à n

Exercice de code : Somme des entiers de 0 à n

Vous savez programmer cela en itératif avec une boucle for, mais ici vous devez le faire de façon récursive.

COnTRAINTE : vous ne pouvez pas utiliser for ou while dans cet exercice.

Vous devez créer un compte et vous connecter avant de poser une question.

def somme(n : int) -> int: """ :param n: int : n positif ou nul :returns: int : la somme des entiers de 0 à n """ # vérifier les préconditions : assert type(n) == int , "somme : l'argument n doit être un entier" assert n>=0 , "somme : l'argument n doit être positif ou nul" # A vous

Plus d'actions... Réinitialiser code Aide

Exercice 2 :

Oui... je sais, nous l'avons déjà vu en exemple .... mais saurez vous le refaire ?

Exercice de code : calculer

Vous devez créer un compte et vous connecter avant de poser une question.

def exponant(a: int, n: int) -> int: """ :param a: int : n positif ou nul :returns: int : la valeur de a**n """ # testez (avec assert) que : # a est un float # que n est un int # que n >= 0 # codez la fonction

Plus d'actions... Réinitialiser code Aide

Il faut toujours penser à vérifier les cas "limites".
Votre fonction renvoie-t-elle le bon résultat pour ?

Indice 
Réponse