Récursivité dans l'algorithmique et la programmation/Exercices/Introduction

Puissance entière d'un entier

La fonction puissance entière peut être définie ainsi : ${\begin{array}{l r}x^{n}={\begin{cases}1&{\mbox{si }}n=0\\x.x^{(n-1)}&{\mbox{si }}n>0\end{cases}}&x,n\in \mathbb {N} \end{array}}$

1. Cette définition respecte-t-elle les caractéristiques d'une définition récursive intéressante ?

2. Écrivez l'algorithme de la fonction ipower(x,n) correspondante.

Solution

1. Cette définition respecte les caractéristiques d'une définition récursive intéressante car

• il y a un appel récursif avec un problème de taille plus petite ( de ipower(x,n) on appelle ipower(x,n-1)
• il y a bien une condition d'arrêt : cas où n vaut 0

2. L'algorithme de la fonction power(x,n) est le suivant :

Début de l'exemple

Algorithme : Puissance entière

${\begin{array}{|l}\operatorname {\underline {fonction}} \ ipower(x,n)\\\operatorname {\underline {debut}} \\{\begin{array}{|l}\operatorname {\underline {si}} \ n=0\ \operatorname {\underline {alors}} \\\ \ ipower\leftarrow 1\\\operatorname {\underline {sinon}} \\\ \ ipower\leftarrow x*ipower(x,n-1)\\\operatorname {\underline {fsi}} \\\end{array}}\\\operatorname {\underline {fin}} \\\end{array}}$

Fin de l'exemple