Récursivité

Résumé du document

Programmation en Pascal

Récursivité

Extraits

[...] Comment écrire en récursif ? Décomposer un problème en un problème plus simple. Soit un tableau de n cases, pour décomposer en un problème plus simple, on peut chercher un minimum dans un tableau plus petit (enlever une case, i.e prendre en compte les premières cases), et comparer ce minimum avec la case enlevée. Si le minimum a du tableau plus petit cases : est inferieur à la valeur b de la case ignorée (indice n : le minimum du tableau est sinon c'est b. [...]

[...] Trouver un cas d'arrêt. Dans un tableau de taille on peut calculer la somme sans décomposer le problème, sans faire d'appel récursif. Exemple : Somme des éléments d'un tableau, récursif. const TabMax = 10 ; type Tab = array [ TabMax] of integer ; {retourne la somme des n premières valeurs de function sommeTab : Tab ; n : integer) : integer ; begin if n = 1 then sommeTab else sommeTab sommeTab + end ; Exemple : itératif function sommeTab2 : Tab ; n : integer) : integer ; var i : integer ; somme integer ; begin somme 0 ; for i 1 to n do somme somme + ; sommeTab2 somme ; end ; L'écriture récursive est souvent plus courte et plus simple Moyenne des éléments d'un tableau. [...]

[...] Récursivité I. Principe Comment calculer la factorielle d'un entier n donné ? Rappel : = 1x2x3x x(n-1)xn On utilise la propriété : = x n (pour Pour définir la fonction factorielle, on utilise la fonction factorielle. Exemple : Factorielle 4 3!x4 (2!x3)x4 ((1!x2)x3)x4 (((0!x1)x2)x3)x4 Or par convention donc (((0!x1)x2)x3)x4=24 Définition : Un algorithme (ou un sous programme) est dit récursif quand il contient ou (ou des) appels(s) à lui- même. La récursivité peut être indirecte dans le cas où un sous programme sp1 fait appel à un sous programme sp2 qui fait appel à sp1. [...]

[...] L'utilisation d'une fonction récursive n'a donc aucun intérêt. Exemple : Moyenne function moyenneTab : Tab ; n : integer) : integer ; begin moyenneTab sommeTab div n end ; 3. Recherche dans un tableau trié Problème : Chercher si une valeur entière donnée apparaît parmi les éléments d'un tableau. La particularité est que ce tableau est trié dans l'ordre croissant. Exemple : Savoir des petits tableaux, une recherche par dichotomie n'est guère plus rapide (10 alors que sur des grands tableaux la dichotomie est nettement plus rapide (100000 17). [...]

[...] Exemple : Program minTableau ; const TabMax = 10 ; type Tab = array [ TabMax] of integer ; {retourne le mini parmi les n premières valeur de function minTableau :Tab ; n :integer) : integer ; var min1 : integer ; begin if n = 1 then minTableau else begin min1 minTableau ; if min1=1. IV. Exemples 1. Somme des éléments d'un tableau Problème : Ecrire (en récursif) un sous programme qui calcule la somme des éléments d'un tableau d'entiers. Comment écrire en récursif ? Décomposer un problème en un problème plus simple. L'opérateur + ne peut être utilisé qu'avec deux entiers ( et ne peut pas être utilisé sur un tableau). [...]