Une page de Wikiversité, la communauté pédagogique libre.
En raison de limitations techniques, la typographie souhaitable du titre, «
Exercice : IntroductionRécursivité dans l'algorithmique et la programmation/Exercices/Introduction », n'a pu être restituée correctement ci-dessus.
La fonction puissance entière peut être définie ainsi :
x
n
=
{
1
si
n
=
0
x
.
x
(
n
−
1
)
si
n
>
0
x
,
n
∈
N
{\displaystyle {\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
f
o
n
c
t
i
o
n
_
i
p
o
w
e
r
(
x
,
n
)
d
e
b
u
t
_
s
i
_
n
=
0
a
l
o
r
s
_
i
p
o
w
e
r
←
1
s
i
n
o
n
_
i
p
o
w
e
r
←
x
∗
i
p
o
w
e
r
(
x
,
n
−
1
)
f
s
i
_
f
i
n
_
{\displaystyle {\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
