Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Recursion and stack#163

New issue

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 ourterms of service andprivacy statement. We’ll occasionally send you account related emails.

Already on GitHub?Sign in to your account

Merged
otmon76 merged 1 commit intojavascript-tutorial:masterfromotmon76:1.6.1
Jun 3, 2025
Merged
Show file tree
Hide file tree
Changes fromall commits
Commits
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
32 changes: 16 additions & 16 deletions1-js/06-advanced-functions/01-recursion/01-sum-to/solution.md
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -1,40 +1,40 @@
The solution using a loop:
Řešení pomocí cyklu:

```js run
functionsumTo(n) {
letsum = 0;
functionsečtiDo(n) {
letsoučet = 0;
for (let i = 1; i <= n; i++) {
sum += i;
součet += i;
}
returnsum;
returnsoučet;
}

alert(sumTo(100) );
alert(sečtiDo(100) );
```

The solution using recursion:
Řešení pomocí rekurze:

```js run
functionsumTo(n) {
functionsečtiDo(n) {
if (n == 1) return 1;
return n +sumTo(n - 1);
return n +sečtiDo(n - 1);
}

alert(sumTo(100) );
alert(sečtiDo(100) );
```

The solution using the formula: `sumTo(n) = n*(n+1)/2`:
Řešení pomocí vzorce: `sečtiDo(n) = n*(n+1)/2`:

```js run
functionsumTo(n) {
functionsečtiDo(n) {
return n * (n + 1) / 2;
}

alert(sumTo(100) );
alert(sečtiDo(100) );
```

P.S.Naturally, the formula is the fastest solution. It uses only 3 operations for any number `n`. The math helps!
P.S.Nejrychlejší řešení je pochopitelně pomocí vzorce. Pro jakékoli číslo `n` vykonává pouze 3 operace. Matematika pomáhá!

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.
Druhá nejlepší co do rychlosti je varianta s cyklem. V rekurzívní i v cyklové variantě sčítáme stejná čísla, ale rekurze vyžaduje vnořená volání a správu prováděcího zásobníku. To vyžaduje další zdroje, takže je pomalejší.

P.P.S.Some engines support the "tail call" optimization: if a recursive call is the very last one in the function, with no other calculations performed, 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. 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.Některé motory podporují optimalizaci „koncového volání“: je-li rekurzívní volání ve funkci úplně poslední a žádné další výpočty se neprovádějí, pak se nemusí obnovovat provádění vnější funkce, takže si motor nemusí pamatovat její prováděcí kontext. Tím se sníží paměťová zátěž. Pokud však motor JavaScriptu nepodporuje optimalizaci koncového volání (a většina motorů ji nepodporuje),nastane chyba: bude překročena maximální velikost zásobníku, protože celková velikost zásobníku je obvykle omezena.
34 changes: 17 additions & 17 deletions1-js/06-advanced-functions/01-recursion/01-sum-to/task.md
View file
Open in desktop
Original file line numberDiff line numberDiff line change
Expand Up@@ -2,35 +2,35 @@ importance: 5

---

#Sum all numbers till the given one
#Sečtěte všechna čísla až do zadaného

Write a function `sumTo(n)` that calculates the sum of numbers `1 + 2 + ... + n`.
Napište funkci `sečtiDo(n)`, která vypočítá součet čísel `1 + 2 + ... + n`.

For instance:
Například:

```js no-beautify
sumTo(1) = 1
sumTo(2) = 2 + 1 = 3
sumTo(3) = 3 + 2 + 1 = 6
sumTo(4) = 4 + 3 + 2 + 1 = 10
sečtiDo(1) = 1
sečtiDo(2) = 2 + 1 = 3
sečtiDo(3) = 3 + 2 + 1 = 6
sečtiDo(4) = 4 + 3 + 2 + 1 = 10
...
sumTo(100) = 100 + 99 + ... + 2 + 1 = 5050
sečtiDo(100) = 100 + 99 + ... + 2 + 1 = 5050
```

Make 3solution variants:
Vytvořte 3varianty řešení:

1.Using a for loop.
2.Using a recursion, cause `sumTo(n) = n +sumTo(n-1)`for `n > 1`.
3.Using the [arithmetic progression](https://en.wikipedia.org/wiki/Arithmetic_progression) formula.
1.Pomocí cyklu for.
2.Pomocí rekurze `sečtiDo(n) = n +sečtiDo(n-1)`pro `n > 1`.
3.Pomocí vzorce pro [aritmetickou posloupnost](https://cs.wikipedia.org/wiki/Aritmetická_posloupnost).

An example of the result:
Příklad výsledku:

```js
functionsumTo(n) { /*...your code ... */ }
functionsečtiDo(n) { /*...váš kód ... */ }

alert(sumTo(100) ); // 5050
alert(sečtiDo(100) ); // 5050
```

P.S.Which solution variant is the fastest? The slowest? Why?
P.S.Která varianta řešení je nejrychlejší? A nejpomalejší? Proč?

P.P.S.Can we use recursion to count `sumTo(100000)`?
P.P.S.Můžeme použít rekurzi k výpočtu `sečtiDo(100000)`?
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -1,21 +1,21 @@
By definition, a factorial `n!`can be written as `n * (n-1)!`.
Podle definice můžeme faktoriál `n!`zapsat jako `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`.
Jinými slovy, výsledek funkce `faktoriál(n)`můžeme vypočítat jako`n`vynásobené výsledkem volání `faktoriál(n-1)`.A volání pro`n-1`může rekurzívně klesat níž a níž až k `1`.

```js run
functionfactorial(n) {
return (n != 1) ? n *factorial(n - 1) : 1;
functionfaktoriál(n) {
return (n != 1) ? n *faktoriál(n - 1) : 1;
}

alert(factorial(5) ); // 120
alert(faktoriál(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:
Základem rekurze je hodnota`1`.Zde můžeme jako základ vzít také`0`, na tom příliš nezáleží, ale to nám dá jeden rekurzívní krok navíc:

```js run
functionfactorial(n) {
return n ? n *factorial(n - 1) : 1;
functionfaktoriál(n) {
return n ? n *faktoriál(n - 1) : 1;
}

alert(factorial(5) ); // 120
alert(faktoriál(5) ); // 120
```
14 changes: 7 additions & 7 deletions1-js/06-advanced-functions/01-recursion/02-factorial/task.md
View file
Open in desktop
Original file line numberDiff line numberDiff line change
Expand Up@@ -2,17 +2,17 @@ importance: 4

---

#Calculate factorial
#Výpočet faktoriálu

The [factorial](https://en.wikipedia.org/wiki/Factorial) of a natural number is a number multiplied by `"numberminusone"`,then by `"numberminustwo"`, and so on till`1`.The factorial of`n`is denoted as`n!`
[Faktoriál](https://cs.wikipedia.org/wiki/Faktoriál) přirozeného čísla je toto číslo násobené `„sebou samýmminus1“`,pak `„sebou samýmminus2“` a tak dále, až do`1`.Faktoriál`n`se značí`n!`.

We can write a definition of factorial like this:
Můžeme napsat definici faktoriálu takto:

```js
n! = n * (n - 1) * (n - 2) * ...*1
```

Values of factorials for different `n`:
Hodnoty faktoriálů pro různá `n`:

```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.
Úkolem je napsat funkci `faktoriál(n)`, která vypočítá `n!`pomocí rekurzívních volání.

```js
alert(factorial(5) ); // 120
alert(faktoriál(5) ); // 120
```

P.S.Hint: `n!`can be written as`n * (n-1)!` For instance: `3! = 3*2! = 3*2*1! = 6`
P.S.Rada: `n!`lze zapsat jako`n * (n-1)!`. Například: `3! = 3*2! = 3*2*1! = 6`.
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,6 @@
The first solution we could try here is the recursive one.
První řešení, o které se pokusíme, bude rekurzívní.

Fibonacci numbers are recursive by definition:
Fibonacciho čísla jsou podle definice rekurzívní:

```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); //bude extrémně pomalé!
```

...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.
...Ale pro velké hodnoty`n`to bude velmi pomalé. Například`fib(77)`může na nějaký čas zablokovat motor, protože spotřebuje všechny zdroje CPU.

That's because the function makes too many subcalls. The same values are re-evaluated again and again.
Je to proto, že funkce učiní příliš mnoho vnořených volání. Stejné hodnoty se budou počítat znovu a znovu.

For instance, let's see a piece of calculations for `fib(5)`:
Podívejme se například na část výpočtu `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.
Zde vidíme, že hodnota`fib(3)`je zapotřebí pro`fib(5)`i pro`fib(4)`.Takže `fib(3)`bude volána a vyhodnocena dvakrát zcela nezávisle na sobě.

Here's the full recursion tree:
Zde je úplný rekurzívní strom:

![fibonacci recursion tree](fibonacci-recursion-tree.svg)
![rekurzívní strom Fibonacciho čísel](fibonacci-recursion-tree.svg)

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`.
Můžeme jasně vidět, že`fib(3)`se vypočítá dvakrát a`fib(2)`třikrát. Celkový počet výpočtů roste mnohem rychleji než`n`,takže už pro`n=77` bude obrovský.

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.
Můžeme to optimalizovat tak, že si budeme pamatovat již vypočtené hodnoty: jestliže se např. hodnota`fib(3)`vypočítá jednou, budeme ji pak moci využít k dalším výpočtům.

Another variant would be to give up recursion and use a totally different loop-based algorithm.
Další variantou by bylo vzdát se rekurze a použít úplně jiný algoritmus založený na cyklu.

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.
Místo abychom šli od `n`dolů k nižším hodnotám, můžeme vytvořit cyklus, který začne od`1`a `2`,pak vypočítá `fib(3)`jako jejich součet, pak `fib(4)`jako součet předchozích dvou hodnot, pak `fib(5)`a tak to jde výš a výš, až se dostaneme k požadované hodnotě. V každém kroku si musíme pamatovat jen dvě předchozí hodnoty.

Here are the steps of the new algorithm in details.
Zde jsou kroky nového algoritmu podrobně.

The start:
Začátek:

```js
// a = fib(1), b = fib(2),these values are by definition 1
// a = fib(1), b = fib(2),tyto hodnoty jsou podle definice 1
let a = 1, b = 1;

//get c = fib(3)as their sum
//získáme c = fib(3)jako jejich součet
let c = a + b;

/*we now have fib(1), fib(2), fib(3)
/*nyní máme fib(1), fib(2), fib(3)
a b c
1, 1, 2
*/
```

Now we want to get `fib(4) = fib(2) + fib(3)`.
Nyní chceme získat `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:
Posuneme proměnné: `a,b`budou představovat `fib(2),fib(3)` a `c`bude jejich součet:

```js no-beautify
a = b; //now a = fib(2)
b = c; //now b = fib(3)
a = b; //nyní a = fib(2)
b = c; //nyní b = fib(3)
c = a + b; // c = fib(4)

/*now we have the sequence:
/*nyní máme posloupnost:
a b c
1, 1, 2, 3
*/
```

The next step gives another sequence number:
Další krok nám dává další číslo v posloupnosti:

```js no-beautify
a = b; //now a = fib(3)
b = c; //now b = fib(4)
a = b; //nyní a = fib(3)
b = c; //nyní b = fib(4)
c = a + b; // c = fib(5)

/*now the sequence is (one more number):
/*posloupnost nyní je (jedno další číslo):
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.
...A tak dále, dokud nezískáme požadovanou hodnotu. Je to mnohem rychlejší než rekurze a neobsahuje žádné duplicitní výpočty.

The full code:
Úplný kód:

```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`.
Cyklus začíná od`i=3`,protože první a druhá hodnota posloupnosti jsou napevno zakódovány do proměnných `a=1`, `b=1`.

The approach is called [dynamic programming bottom-up](https://en.wikipedia.org/wiki/Dynamic_programming).
Tento přístup se nazývá [dynamické programování](https://cs.wikipedia.org/wiki/Dynamické_programování).
View file
Open in desktop
Original file line numberDiff line numberDiff line change
Expand Up@@ -2,24 +2,25 @@ importance: 5

---

#Fibonacci numbers
#Fibonacciho čísla

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.
Posloupnost [Fibonacciho čísel](https://cs.wikipedia.org/wiki/Fibonacciho_posloupnost) je dána vzorcem <code>F<sub>n</sub> = F<sub>n-1</sub> + F<sub>n-2</sub></code>.Jinými slovy, každé další číslo je součtem dvou předcházejících.

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...`.
První dvě čísla jsou `1`,pak `2(1+1)`,pak `3(1+2)`, `5(2+3)`a tak dále: `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.
Fibonacciho čísla mají vztah ke [zlatému řezu](https://cs.wikipedia.org/wiki/Zlatý_řez) a mnoha přírodním jevům okolo nás.

Write a function`fib(n)` that returns the`n-th` Fibonacci number.
Napište funkci`fib(n)`, která vrátí`n-té` Fibonacciho číslo.

An example of work:
Příklad funkčnosti:

```js
function fib(n) { /*your code */ }
function fib(n) { /*váš kód */ }

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. Tato funkce by měla být rychlá. Volání `fib(77)` by nemělo trvat déle než zlomek sekundy.

Loading
[8]ページ先頭
©2009-2025 Movatter.jp