Récurrences

De nombreux problèmes numériques d'usage courant sont résolus à l'aide de suites récurrentes ; la convergence de ces suites permet de calculer une solution approchée du problème.

L'algorithme de Newton-Raphson permet de calculer un zéro d'une fonction de classe $C^2$, par un schéma récurrent ayant une convergence quadratique, s'il converge (ce qui dépend du choix de $x_0$). L'équation de récurrence

$$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}, \qquad x_0\ \mbox{donné}$$

se traduit immédiatement en une définition récursive de fonction :

double newton(int n, double x0) {
  if (n == 0) {
    return x0;
  } else {
    double x = newton(n-1, x0);      // variable locale

    return x - f(x)/fprime(x);
  }
}

On a défini une variable locale x dans le bloc composant la branche else.