Éléments de Théorie de la Calculabilité

:

L'idée principale de la récursion est que si l'on peut calculer g et h, alors on peut calculer f. La récursion est donc un moyen de définir de nouvelles fonctions calculables à partir d'autres fonctions. f(x,0) = g(x) f(x, n + 1) = h(f(x, n), x, n).