Racine carré successive Résolu/Fermé

Question

Bonjour, 

Il se trouve que je n'arrive pas à trouver la solution à un problème malgré mes innombrables efforts. Voila ce qu'il en est.

J'ai une suite A(n) qui s'exprime comme une successions de racine carré de 1 comme ceci :

==> A(n)=sqrt(1+sqrt(1+sqrt(1+sqrt(1).... , avec n radicaux, vous l'aurez compris. 

La question est la suivante : comment faire un programme python qui renverrai la valeur exacte de cette suite. Je n'arrive pas à comprendre comment faire pour modéliser une suite infinie sur python.

Merci d'avance...

Configuration: Windows / Opera 75.0.3969.171

mamiemando · Answer

Bonjour,

Réponse courte

La mnière la plus simple se résout en écrivant une fonction récursive, mais tu peux également accumuler le résultat du calcul en partant de la racine la plus imbriquée et remonter de racine en racine.

Réponse détaillée

Prenons un exemple plus simple, suppons qu'on veuille calculer la somme des entiers de 0 à n exclu. En python on écrirait bien sûr sum(range(n)) mais que se passe-t'il si on s'interdit d'utiliser sum et range ?

Dans ce cas tu vas vouloir écrire une fonction (appelons-la somme) dans laquelle tu itères de 0 à n, et au cours de laquelle tu mets progressivement à jour le résultat (appelons le s).

Pour réaliser une telle itération, il y a deux écoles.

 La méthode itérative :

def somme(n):
    s = 0
    for i in range(n):
        s += i
    return s

 La méthode récursive (pense au "raisonnement par récurrence que tu as dû voir en cours de maths) :

def somme(n, i = 0):
     if i > n - 1:
         return 0
     return i + somme(n, i + 1)

Si on prend le temps de regarder la forme récursive :

 le paramètre i = 0 correspond à la première "moitié" de for i in range(n) de la version itérative (on compte à partir de 0)
 le test i > n -1 correspond à la seconde "moitié" de for i in range(n) de la version itérative (on compte s'arrête quand on dépasse n -1)
 l'instruction return 0 correspond à s = 0 (quel est le résultat quand on n'a pas pu itérer), c'est l'initialisation du raisonnement par récurrence.
 l'instruction i + somme(n, i + 1), c'est la récurrence elle-même. Elle signifie dans cette exemple : la somme des entiers de 0 à n est égale à "0 + somme(k = 1 à n) = 0 + (1 + somme(k = 2 à n)) = 0 + (1 + (2 + ... + (i + (somme(k = i + 1 à n))...)"

Ce sont donc deux manières différentes de calculer la même chose. Comme tu l'as compris, cette exemple peut facilement s'adapter pour calculer des factorielles.

Récursif ou itératif

Selon ce que tu as faire, il est plus facile/naturel d'écrire la version itérative ou récursive d'un problème.

Il faut garder que d'un point de vue informatique, si tu appelles récursivement une fonction un trop gros nombre de fois, python peut planter. Ceci est inhérent à la manière dont marche un programme. Quand on appelle une fonction le runtime garde trace de la pile d'appel des fonctions (ce qui permet, quand une sous fonction se termine, de reprendre le programme où il faut et comme il faut dans la fonction appelante). Comme d'un point de vue système, la taille de la pile d'appel est limité, un trop grand nombre d'appel récursif peut saturer la pile d'appel. On parle alors de débordement de pile (stack overflow en anglais, terme à l'origine d'un célèbre site). De plus cette mise en pile réclame du "travail" à l'ordinateur et sera donc moins performante qu'une écriture itérative équivalente. C'est pourquoi les récursions doivent être utilisées avec parcimonie.

Au contraire, la version itérative ne met en jeu qu'un seul appel à la fonction somme et ne maintient en mémoire que peut d'information (les valeurs de s, i, et n) et donc passe mieux à l'échelle.

Pour aller plus loin: à noter que ça ne signifie pas qu'il faut systématiquement proscrire une écriture récursive. En particulier, toute la branche de la programmation dynamique, qui permet de décomposer un problème sous forme récursive en mémorisant des résultats intermédiaire, s'écrit en pratique sous forme récursive. Quelques exemples classiques : [les suites de Fibonnacci], la plupart des distances d'éditions, etc.

Retour à ton exercice

Dans ton cas, tu peux facilement adapter la récurrence pour calculer des racines carrées imbriquées et en utilisant la fonction math.sqrt pour calculer des racines carrées :

from math import sqrt
print(sqrt(9))

Une fois que ce sera bien clair pour toi, tu peux t'entraîner à écrire le programme dans sa version itérative.

Bonne chance

Racine carré successive

1 réponse

Discussions similaires