récursif, programme - informatique.

récursif, programme - informatique. récursif, programme, programme demandant sa propre exécution au cours de son déroulement. Le mot récurrence provient du latin recurrens qui signifie « qui revient en arrière «. La notion de récursivité n'est pas propre au domaine informatique. C'est un concept puissant qui permet de décomposer un problème en plusieurs situations de même nature. En mathématiques, une relation récursive est une relation qui définit un terme de rang donné d'une suite, en fonction d'un ou plusieurs termes de rang inférieur. En informatique, la récursivité s'applique soit aux actions, dans le cas de sous-programmes (procédures ou fonctions) récursifs, soit aux objets, lorsqu'ils contiennent un ou plusieurs composants du même type. Par exemple, la factorielle d'un entier N, notée N !, peut être définie par : N ! = Fact (N - 1) ! x N avec 0 ! = 1 Cette formule ne donne pas immédiatement la valeur de N!. Le résultat attendu est différé, car il dépend de celui calculé par la factorielle de (N - 1). On peut en déduire que : 3!=2!x3 = (1 ! x 2) x 3 = [(0 ! x 1) x 2] x 3 La condition 0 ! = 1 étant posée, le calcul de la factorielle d'un entier N par ce type de programme s'obtient de manière moins directe que s'il est effectué manuellement ; dans ce dernier cas, le calcul de N ! s'obtient de manière plus directe ; par exemple, 5 ! se traduit par l'équation : 5 ! = 5 x 4 x 3 x 2 x 1 = 120 alors que la récursivité voudrait que l'on calcule d'abord à 1 !, puis à 2 !, etc. Ainsi, lors de l'écriture d'un algorithme, le même raccourci est appliqué pour le codage, en utilisant un algorithme itératif. Appliqué à l'exemple précédent du calcul factoriel de N, on a l'algorithme suivant : Fonction factorielle (N : entier) : entier ; Début Si N > 0 alors factorielle := N × factorielle (N - 1) sinon factorielle := 1 FinSi Fin À partir d'un algorithme récursif (qui ne se termine pas), l'utilisation d'un algorithme itératif permet le passage à un schéma récursif terminal (qui a une fin). Dans de nombreux cas, les problèmes rencontrés peuvent être traités par des algorithmes récursifs ; mais ces derniers sont extrêmement gourmands en ressources de calcul et de mémoire. De plus, tous les langages ne gèrent pas la récursivité. Ces deux conditions font que les développeurs sont souvent contraints de programmer des algorithmes itératifs. Microsoft ® Encarta ® 2009. © 1993-2008 Microsoft Corporation. Tous droits réservés.