User:Dereckson/Notes 2015-08-11: Difference between revisions
(Created page with "== Définition formelle de la récursivité == ''Source:'' rama La récursion se compose de deux choses : # une façon de passer de l'étape N à l'étape N+1 (en fonction...") |
|||
| (5 intermediate revisions by 2 users not shown) | |||
| Line 9: | Line 9: | ||
la démonstration par récurrence se résume ainsi à "je prouve que si $PROPERTY est vraie pour x_(n), elle est vrai pour n_(n+1), ET j'exhibe un cas x_0 pour lequel c'est vrai ; c'est donc vrai pour tout x_n avec n entre 0 et l'infini". | la démonstration par récurrence se résume ainsi à "je prouve que si $PROPERTY est vraie pour x_(n), elle est vrai pour n_(n+1), ET j'exhibe un cas x_0 pour lequel c'est vrai ; c'est donc vrai pour tout x_n avec n entre 0 et l'infini". | ||
== Approche intuitive de la récursivité == | |||
La récursivité est une fonction qui s'appelle elle-même. | |||
Si tu as un Android, l'application AirDroid permet de prendre une photo, en l'afficher la caméra sur l'écran. Photographie l'écran qui affiche la photographie et tu obtiendras quelque chose comme ceci : | |||
[[File:Recursivity intuitive.jpg]] | |||
== Copier un tableau en C++ == | == Copier un tableau en C++ == | ||
http://nadeausoftware.com/articles/2012/05/c_c_tip_how_copy_memory_quickly#Method1Loopwitharrayindexes | http://nadeausoftware.com/articles/2012/05/c_c_tip_how_copy_memory_quickly#Method1Loopwitharrayindexes | ||
== Exercices == | |||
Refaire la factorielle, findmin | |||
Calculer par récursivité la somme des nombres d'un tableau | |||
<code> | |||
int findsum (int numbers[], int size) | |||
e.g. findsum([1, 4, 7, 26], 4) should return 38. | |||
</code> | |||
Déterminer si un chaîne de caractères est ou non un palindrome. | |||
<code> | |||
bool isPalindrome (char word[], int len); | |||
e.g. isPalindrome("kayak", 5) should return true. | |||
</code> | |||
== Pour aller plus loin == | |||
* Les articles de Wikipédia qui couvre le sujet : | |||
** [[w:Recursion]] | |||
** [[w:Recursion (computer science)]] | |||
** [[w:Recurrence relation]] | |||
* [https://en.wikipedia.org/wiki/Recursion_%28computer_science%29#Recursion_versus_iteration Quand utiliser la récursivité, quand utiliser une boucle ?] | |||
Latest revision as of 18:11, 11 August 2015
Définition formelle de la récursivité
Source: rama
La récursion se compose de deux choses :
- une façon de passer de l'étape N à l'étape N+1 (en fonction de l'étapge N, voire d'autres étapes antérieures)
- un ancrage (i.e. la première occurrence)
la démonstration par récurrence se résume ainsi à "je prouve que si $PROPERTY est vraie pour x_(n), elle est vrai pour n_(n+1), ET j'exhibe un cas x_0 pour lequel c'est vrai ; c'est donc vrai pour tout x_n avec n entre 0 et l'infini".
Approche intuitive de la récursivité
La récursivité est une fonction qui s'appelle elle-même.
Si tu as un Android, l'application AirDroid permet de prendre une photo, en l'afficher la caméra sur l'écran. Photographie l'écran qui affiche la photographie et tu obtiendras quelque chose comme ceci :
Copier un tableau en C++
Exercices
Refaire la factorielle, findmin
Calculer par récursivité la somme des nombres d'un tableau
int findsum (int numbers[], int size)
e.g. findsum([1, 4, 7, 26], 4) should return 38.
Déterminer si un chaîne de caractères est ou non un palindrome.
bool isPalindrome (char word[], int len);
e.g. isPalindrome("kayak", 5) should return true.
Pour aller plus loin
- Les articles de Wikipédia qui couvre le sujet :
