This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
The solution using the formula: `sumTo(n) = n*(n+1)/2`:
La solution utilisant la formule: `sumTo(n) = n*(n+1)/2`:
```js run
function sumTo(n) {
Expand All
@@ -33,8 +33,8 @@ function sumTo(n) {
alert( sumTo(100) );
```
P.S. Naturally, the formula is the fastest solution. It uses only 3 operations for any number `n`. The math helps!
P.S. Naturellement, la formule est la solution la plus rapide. Elle n’utilise que 3 opérations pour n’importe quel nombre `n`. Le calcul aide!
The loop variant is the second in terms of speed. In both the recursive and the loop variant we sum the same numbers. But the recursion involves nested calls and execution stack management. That also takes resources, so it's slower.
La variante de boucle est la seconde en termes de vitesse. Dans la variante récursive et la variante de boucle, nous additionnons les mêmes nombres. Mais la récursion implique des appels imbriqués et la gestion de la pile d'exécution. Donc, cela prend des ressources, donc c'est plus lent.
P.P.S. Some engines support the "tail call" optimization: if a recursive call is the very last one in the function (like in `sumTo` above), then the outer function will not need to resume the execution, so the engine doesn't need to remember its execution context. That removes the burden on memory, so counting `sumTo(100000)` becomes possible. But if the JavaScript engine does not support tail call optimization (most of them don't), there will be an error: maximum stack size exceeded, because there's usually a limitation on the total stack size.
P.P.S. Certains moteurs prennent en charge l'optimisation du "tail call (dernier appel)": si un appel récursif est le dernier de la fonction (comme dans la somme ci-dessus), le moteur n'a pas besoin de reprendre son contexte d'exécution. Cela supprime la charge en mémoire, donc compter `sumTo(100000)` devient possible. Toutefois, si le moteur JavaScript ne prend pas en charge l'optimisation des appels en bout de ligne, il y aura une erreur: maximum stack size exceeded (la taille maximale de la pile est dépassée), car la taille totale de la pile est généralement limitée.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
By definition, a factorial is `n!` can be written as `n * (n-1)!`.
Par définition, une factorielle est `n!` peut être écrit `n * (n-1)!`.
In other words, the result of `factorial(n)` can be calculated as `n` multiplied by the result of `factorial(n-1)`. And the call for `n-1` can recursively descend lower, and lower, till `1`.
En d'autres termes, le résultat de `factorial(n)` peut être calculé comme `n` multiplié par le résultat de `factorial(n-1)`. Et l'appel de `n-1` peut récursivement descendre plus bas, et plus bas, jusqu'à `1`.
```js run
function factorial(n) {
Expand All
@@ -10,7 +10,7 @@ function factorial(n) {
alert( factorial(5) ); // 120
```
The basis of recursion is the value `1`. We can also make `0` the basis here, doesn't matter much, but gives one more recursive step:
La base de la récursivité est la valeur `1`. Nous pouvons aussi faire de `0` la base ici, ça importe peu, mais donne une étape récursive supplémentaire:
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
The [factorial](https://en.wikipedia.org/wiki/Factorial) of a natural number is a number multiplied by `"number minus one"`, then by `"number minus two"`, and so on till `1`. The factorial of `n` is denoted as `n!`
Le [factorielle](https://en.wikipedia.org/wiki/Factorial) d'un nombre naturel est multiplié par `"nombre moins un"`, ensuite par `"nombre moins deux"`, et ainsi de suite jusqu'à `1`. La factorielle de `n` est noté comme `n!`
We can write a definition of factorial like this:
Nous pouvons écrire une définition de factorielle comme ceci:
```js
n! = n * (n - 1) * (n - 2) * ...*1
```
Values of factorials for different `n`:
Valeurs des factorielles pour des `n` différents:
```js
1! = 1
Expand All
@@ -22,10 +22,10 @@ Values of factorials for different `n`:
5! = 5 * 4 * 3 * 2 * 1 = 120
```
The task is to write a function `factorial(n)` that calculates `n!` using recursive calls.
La tâche est d'écrire une fonction `factorial(n)` qui calcule `n!` en utilisant des appels récursifs.
```js
alert( factorial(5) ); // 120
```
P.S. Hint: `n!` can be written as `n * (n-1)!` For instance: `3! = 3*2! = 3*2*1! = 6`
P.S. Indice: `n!` peut être écrit `n * (n-1)!` Par exemple: `3! = 3*2! = 3*2*1! = 6`
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
The first solution we could try here is the recursive one.
La première solution que nous pourrions essayer ici est la solution récursive.
Fibonacci numbers are recursive by definition:
Les nombres de Fibonacci sont récursifs par définition:
```js run
function fib(n) {
Expand All
@@ -9,14 +9,14 @@ function fib(n) {
alert( fib(3) ); // 2
alert( fib(7) ); // 13
// fib(77); // will be extremely slow!
// fib(77); // Sera extrêmement lent!
```
...But for big values of `n` it's very slow. For instance, `fib(77)` may hang up the engine for some time eating all CPU resources.
...Mais pour les grandes valeurs de `n` c'est très lent. Par exemple, `fib(77)` peut bloquer le moteur pendant un certain temps en consommant toutes les ressources du processeur.
That's because the function makes too many subcalls. The same values are re-evaluated again and again.
C'est parce que la fonction crée trop de sous-appels. Les mêmes valeurs sont réévaluées encore et encore.
For instance, let's see a piece of calculations for `fib(5)`:
Par exemple, voyons un calcul pour `fib(5)`:
```js no-beautify
...
Expand All
@@ -25,68 +25,68 @@ fib(4) = fib(3) + fib(2)
...
```
Here we can see that the value of `fib(3)` is needed for both `fib(5)` and `fib(4)`. So `fib(3)` will be called and evaluated two times completely independently.
Ici, nous pouvons voir que la valeur de `fib(3)` est nécessaire pour les deux `fib(5)` et `fib(4)`. Alors `fib(3)` sera appelé et évalué deux fois de manière totalement indépendante.
We can clearly notice that `fib(3)` is evaluated two times and `fib(2)` is evaluated three times. The total amount of computations grows much faster than `n`, making it enormous even for `n=77`.
Nous pouvons clairement remarquer que `fib(3)` est évalué deux fois et `fib(2)` est évalué trois fois. La quantité totale de calculs augmente beaucoup plus vite que `n`, le rendant énorme même pour `n=77`.
We can optimize that by remembering already-evaluated values: if a value of say `fib(3)` is calculated once, then we can just reuse it in future computations.
Nous pouvons optimiser cela en nous rappelant les valeurs déjà évaluées: si une valeur de `fib(3)` est calculé une fois, alors nous pouvons simplement le réutiliser dans les calculs futurs.
Another variant would be to give up recursion and use a totally different loop-based algorithm.
Une autre variante consisterait à abandonner la récursion et à utiliser un algorithme totalement différent basé sur des boucles.
Instead of going from `n` down to lower values, we can make a loop that starts from `1` and `2`, then gets `fib(3)` as their sum, then `fib(4)` as the sum of two previous values, then `fib(5)` and goes up and up, till it gets to the needed value. On each step we only need to remember two previous values.
Au lieu de partir de `n` jusqu'à des valeurs plus basses, nous pouvons faire une boucle qui commence à partir de `1` et `2`, puis obtient `fib(3)` comme leur somme, ensuite `fib(4)` comme la somme de deux valeurs précédentes, ensuite `fib(5)` et monte, jusqu'à ce qu'il atteigne la valeur nécessaire. À chaque étape, il suffit de rappeler deux valeurs précédentes.
Here are the steps of the new algorithm in details.
Voici les étapes du nouvel algorithme en détails.
The start:
Le début:
```js
// a = fib(1), b = fib(2), these values are by definition 1
// a = fib(1), b = fib(2), ces valeurs sont par définition 1
let a = 1, b = 1;
// get c = fib(3) as their sum
// obtien c = fib(3) comme leur somme
let c = a + b;
/* we now have fib(1), fib(2), fib(3)
/* nous avons maintenant fib(1), fib(2), fib(3)
a b c
1, 1, 2
*/
```
Now we want to get `fib(4) = fib(2) + fib(3)`.
Maintenant, nous voulons obtenir `fib(4) = fib(2) + fib(3)`.
Let's shift the variables: `a,b` will get `fib(2),fib(3)`, and `c` will get their sum:
Passons aux variables: `a,b` aura `fib(2),fib(3)`, et `c` obtiendra leur somme:
```js no-beautify
a = b; // now a = fib(2)
b = c; // now b = fib(3)
a = b; // maintenant a = fib(2)
b = c; // maintenant b = fib(3)
c = a + b; // c = fib(4)
/* now we have the sequence:
/* maintenant nous avons la séquence:
a b c
1, 1, 2, 3
*/
```
The next step gives another sequence number:
L'étape suivante donne un autre numéro de séquence:
```js no-beautify
a = b; // now a = fib(3)
b = c; // now b = fib(4)
a = b; // maintenant a = fib(3)
b = c; // maintenant b = fib(4)
c = a + b; // c = fib(5)
/* now the sequence is (one more number):
/* maintenant la séquence est (encore un numéro):
a b c
1, 1, 2, 3, 5
*/
```
...And so on until we get the needed value. That's much faster than recursion and involves no duplicate computations.
...Et ainsi de suite jusqu'à l'obtention de la valeur nécessaire. C'est beaucoup plus rapide que la récursion et n'implique aucun calcul en double.
The full code:
Le code complet:
```js run
function fib(n) {
Expand All
@@ -105,6 +105,6 @@ alert( fib(7) ); // 13
alert( fib(77) ); // 5527939700884757
```
The loop starts with `i=3`, because the first and the second sequence values are hard-coded into variables `a=1`, `b=1`.
La boucle commence par `i=3`, parce que les première et deuxième valeurs de séquence sont codées en dur dans des variables `a=1`, `b=1`.
The approach is called [dynamic programming bottom-up](https://en.wikipedia.org/wiki/Dynamic_programming).
Cette approche s'appelle la [programmation dynamique de bas en haut](https://fr.wikipedia.org/wiki/Programmation_dynamique).
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
The sequence of [Fibonacci numbers](https://en.wikipedia.org/wiki/Fibonacci_number) has the formula <code>F<sub>n</sub> = F<sub>n-1</sub> + F<sub>n-2</sub></code>. In other words, the next number is a sum of the two preceding ones.
La séquence des [Numéros de Fibonacci](https://fr.wikipedia.org/wiki/Nombre_de_Fibonacci) a la formule <code>F<sub>n</sub> = F<sub>n-1</sub> + F<sub>n-2</sub></code>. En d'autres termes, le nombre suivant est la somme des deux précédents.
First two numbers are `1`, then `2(1+1)`, then `3(1+2)`, `5(2+3)` and so on: `1, 1, 2, 3, 5, 8, 13, 21...`.
Les deux premiers chiffres sont `1`, puis `2(1+1)`, ensuite `3(1+2)`, `5(2+3)` etc: `1, 1, 2, 3, 5, 8, 13, 21...`.
Fibonacci numbers are related to the [Golden ratio](https://en.wikipedia.org/wiki/Golden_ratio) and many natural phenomena around us.
Les nombres de Fibonacci sont liés au [nombre d'or](https://fr.wikipedia.org/wiki/Nombre_d%27or) et de nombreux phénomènes naturels autour de nous.
Write a function `fib(n)` that returns the `n-th` Fibonacci number.
Écrire une fonction `fib(n)` qui retourne le Numéro de Fibonacci `n-th`.
An example of work:
Un exemple de travail:
```js
function fib(n) { /* your code */ }
function fib(n) { /* votre code */ }
alert(fib(3)); // 2
alert(fib(7)); // 13
alert(fib(77)); // 5527939700884757
```
P.S. The function should be fast. The call to `fib(77)` should take no more than a fraction of a second.
P.S. La fonction devrait être rapide. L'appel de `fib(77)` devrait prendre pas plus d'une fraction de seconde.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Please note that we use a temporary variable `tmp` to walk over the list. Technically, we could use a function parameter `list` instead:
Veuillez noter que nous utilisons une variable temporaire `tmp` pour parcourir la liste. Techniquement, nous pourrions utiliser un paramètre de fonction `list` à la place:
```js
function printList(list) {
Expand All
@@ -43,15 +43,15 @@ function printList(list) {
}
```
...But that would be unwise. In the future we may need to extend a function, do something else with the list. If we change `list`, then we loose such ability.
...Mais ce ne serait pas sage. Dans le futur, nous allons peut-être devoir étendre une fonction, faire autre chose avec la liste. Si nous changeons `list`, nous perdons cette capacité.
Talking about good variable names, `list` here is the list itself. The first element of it. And it should remain like that. That's clear and reliable.
Parlant des bons noms de variables, `list` est la liste elle-même. Le premier élément de celui-ci. Et ça devrait rester comme ça. C'est clair et fiable.
From the other side, the role of `tmp` is exclusively a list traversal, like `i` in the `for` loop.
De l’autre côté, le rôle de `tmp` est exclusivement une liste de traversée, comme `i` dans la boucle `for`.
# Recursive solution
# Solution récursive
The recursive variant of `printList(list)` follows a simple logic: to output a list we should output the current element `list`, then do the same for `list.next`:
La variante récursive de `printList(list)` suit une logique simple: pour afficher une liste, il faut afficher l'élément courant `list`, puis faire de même pour `list.next`:
```js run
let list = {
Expand All
@@ -70,19 +70,19 @@ let list = {
function printList(list) {
alert(list.value); // output the current item
alert(list.value); // affiche l'élément en cours
if (list.next) {
printList(list.next); // do the same for the rest of the list
printList(list.next); // fait la même chose pour le reste de la liste
}
}
printList(list);
```
Now what's better?
Maintenant qu'est-ce qui est le mieux?
Technically, the loop is more effective. These two variants do the same, but the loop does not spend resources for nested function calls.
Techniquement, la boucle est plus efficace. Ces deux variantes font la même chose, mais la boucle ne dépense pas de ressources pour les appels de fonction imbriqués.
From the other side, the recursive variant is shorter and sometimes easier to understand.
De l'autre côté, la variante récursive est plus courte et parfois plus facile à comprendre.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Translate recursion in french language #37
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Uh oh!
There was an error while loading. Please reload this page.
Translate recursion in french language #37
Filter by extension
Viewed files
Uh oh!
There was an error while loading. Please reload this page.
Uh oh!
There was an error while loading. Please reload this page.
There are no files selected for viewing
Uh oh!
There was an error while loading. Please reload this page.