Programmation en Pascal
Récursivité
[...] 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). [...]
avec notre liseuse dédiée !
En cliquant sur OK, vous acceptez que Pimido.com utilise des cookies ou une technologie équivalente pour stocker et/ou accéder à des informations sur votre appareil. Ces informations personnelles peuvent être utilisées pour mesurer la performance publicitaire et du contenu ; en apprendre plus sur votre utilisation du site ; ou pour vous permettre d'interagir avec les réseaux sociaux. Vous pouvez paramétrer vos choix pour accepter les cookies ou non. Vous pourrez également modifier vos préférences à tout moment en cliquant sur le lien "Paramètres des cookies" en bas de page de ce site. Pour en savoir plus, consultez notre Politique de confidentialité