RÉCURSIVITÉ

La récursivité est la caractéristique d'un programme ou d'une procédure de s'appeler par lui-même (au moins une fois). Grâce à la récursivité, on peut résoudre de façon simple et concie de nombreux problèmes informatiques. Du fait de cette puissance, faut faire attention, car ce point positif peut revenir contre nous. Le programme ou la procédure peut s'ils ont mal été programmés s'appeler indéfiniment et causer l'arrêt de la machine. Il faut donc bien faire attention à la condition d'arrêt qu'on utilise.

Factoriel

Nous allons débuter par les factoriels. Voici la définition de la récurence des factoriels

n! = n * (n-1) * (n-2) * ... * 1

l! = 1

La fonction factorielle sans l'utilisation de récursion

>function Factorielle(number:integer):integer;
var
  factoriel,i:integer;
begin
  if number = 0 then factoriel := 0
  else
  begin
    factoriel := 1;
    for i := number downto 1 do
      factoriel := factoriel * i
  end;
  result := factoriel;
end;

La fonction factorielle avec la récursion

function factorielle_recursion( n: integer): integer;
begin
  if n <= 0 then
    factorielle_recursion := 1		
  else
  result := n * factorielle_recursion( n - 1 );	{return n*(n-1)! }
end;

On peut remarquer que la fonction des factoriels qui utilise la récursion est plus courte. La pile est grandement utilisée puisque que chaque appel à la fonction créée à nouveau les variables... le tout est ajouté à la pile. La récursivité est un gouffre pour la mémoire.

Fibonacci

Voici la définition de la récurence de Fibonacci

Fib(n) = Fib(n-1) + Fib(n-2) for n > 1

Fib(0) = 0

Fib(1) = 1

La fonction fibonacci sans la récursion

function fibonacci(n:integer):integer;
var 
 i, Un, Un_1, Un_2 : integer;
begin
  Un_1 := 1 ;
  Un_2 := 1 ;
  for i:=2 to n do
  begin
    Un := Un_1 + Un_2 ;
    Un_2 := Un_1 ;
    Un_1 := Un ;
  end;
  result := Un ;
end;

La fonction fibonacci avec la récursion

function fib( n: integer): integer;
begin
  if n <= 1 then
    fib := n	
  else
    fib := fib(n-1) + fib(n-2);	
end;

Vous allez vous rendre compte rapidement des différences de performances qu'il y a entre les deux versions de fibonacci, et ce, aussitôt qu'une valeur de 20 et plus sera attribuée à n.

Pour de plus amples renseignements sur la récursivité, rendez-vous à l'excellent tutoriel sur Chambily.

Article écrit par: Marc Collin