UNE SIMPLE REMARQUE ....

Référence : le précédent billet...

... pour en remettre une petite couche.

Je trouve la récursivité "en action", programmée et exécutée par la machine, fascinante, pour être d'une génération où tout se faisait "à la main".

AINSI, le schéma classique de calcul d'une approximation de la racine carrée de 3 à l'aide des termes successifs de la suite récurrente :

u(0)=2

u(n) = [u(n-1) + 3/u(n-1)]/2

dont la racine carrée de 3 est justement la limite pour n tendant vers l'infini.

Le calcul de u(3) par exemple se fait tranquillement "à la main" par les étapes :

u(0)=2

u(1) = [2 + 3/2]/2 = 7/4

u(1) = 1,75                    

u(2) = [7/4 + 3/(7/4)]/2 = [7/4 + 12/7]/2 = 97/56

u(2) # 1.732142857

u(3) = [97/56 + 3/(97/56)]/2 = [97/56 + 168/97]/2 = [(97x97 + 168x56)/(56x97)]/2 = 18 817/10864

u(3) # 1.73205081

Si l'on souhaite réfléchir à la même séquence en terme de récursivité "à la façon d'un programme machine", on peut calquer sa démarche sur les appels récursifs d'un programme tel que celui-ci, écrit en langage Python : 

def u(n):
if n ==0:
    return 2
else:
    return 0.5*(u(n-1)+3/u(n-1))

print("u(",n,")= ", u(n))

Que "fait-il"?

Il teste (if) si n est égal à 0, auquel cas, il renvoie 2 comme résultat. Sinon (else), il s'appelle lui-même en descendant l'indice n d'un cran dans la formule de récurrence. Mais, si n-1 n'est pas nul, il n'engage pas cette formule puisqu'il doit d'abord de nouveau s'appeler lui-même au rang ((n-1)-1), soit (n-2) pour espérer calculer u(n-1) à partir de u(n-2). Mais pour calculer ce u(n-2), sauf si n-2 est égal à 0, il recommence à s'appeler avec l'indice n-3. Etc.

Jusqu'à - en quelque sorte - l'appel à u(n-n), soit u(0), qui lui permet de cesser les appels internes itérés en renvoyant la valeur de u(0) - soit ici 2 - puis en remontant de l'intérieur toute la chaîne pour aboutir à la valeur de u(n). 

Présentation manuscrite. Bien difficile à lire, je le reconnais. Désolé.

On devine évidemment la complexité de notation pour u(n) si on s'obstine dans cette voie d'écriture.

Le petit programme Python ci-dessus, par contre, gère instantanément ses appels récursifs et affiche par exemple pour n variant de 0 à 9 les résultats :

 u( 0 )= 2

u( 1 )= 1.75
u( 2 )= 1.7321428571428572
u( 3 )= 1.7320508100147274
u( 4 )= 1.7320508075688772
u( 5 )= 1.7320508075688772
u( 6 )= 1.7320508075688772
u( 7 )= 1.7320508075688772
u( 8 )= 1.7320508075688772
u( 9 )= 1.7320508075688772

On notera la stabilité des résultats affichés à partir de n = 4. On ne gagne plus, au-delà, en précision.

Une calculatrice de type lycée donne, elle , pour la racine carrée de 3, l'approximation directe : 1.732050808