Récursivité Flashcards
Qu’est ce qu’une récursion terminale?
C’est lorsqu’un appel récursif est la dernière opération effectuée avant que la fonction ne retourne une valeur. Cela signifie qu’il n’y a pas d’opération à effectuer après l’appel récursif.
How do you calculate the number of permutations possible?
P(n,r) = n! ÷ (n-r)!
n = the total number of items in the set
r = the amount of items being selected
Quelle est la “complexité algorithmique” du tri par sélection?
La “complexité algorithmique” du tri par sélection est O(n^2)
Quelle est la “complexité algorithmique” du tri fusion?
O(n log n)
Que permet de faire la recherche dichotomique?
La recherche dichotomique permet de trouver
rapidement la position d’une valeur x dans un
tableau trié
Comment fonctionne une recherche dichotomique si on veut trouver la position d’un élément x?
Puisque le tableau est trié, on peut savoir dans quel coté du tableau l’élément recherché se trouve.
1. On prend l’élément y qui se situe au milieu du tableau et on la compare à notre élément x
- Si x > y, alors x doit nécessairement se trouver dans la partie droite du tableau, de y+1 à n. Donc on cherche récursivement dans cette partie du tableau.
- si x < y, alors x dans nécessairement se trouver dans la partie gauche du tableau, du début jusqua la l’index de y-1. Donc on cherche récursivement dans cette partie du tableau.
- Si par chance l’élément du milieu y est égale à notre élément recherché x, alors on retourne sa position.
- Si notre tableau est de longueur 0, on retourne -1 puisque l’élément ne peut être dans le tableau.
Que fait os.path.isdir(path) ?
Il verifie si le chemin d’accès fourni est un répértoire. Renvoie un Boolean.
Que fait os.listdir(path) ?
retourne un tableau qui contient tout le contenu du repertoire path.
Qu’est ce qu’une recursion mutuelle?
Deux fonctions ou plus s’appellent mutuellement dans un cycle récursif.
Qu’est ce qu’une recursion directe?
Une seule fonction s’appelle elle même.
