Различия

Здесь показаны различия между двумя версиями данной страницы.

--- basics_of_algorithms:recursion [2023/10/04 21:08]
werwolf [Что такое рекурсия]
+++ basics_of_algorithms:recursion [2023/10/04 21:22] (текущий)
werwolf [Достоинства и недостатки рекурсии]
@@ Строка 188: / Строка 188: @@
 Один из распространенных алгоритмов в программировании — это **бинарный поиск**, который мы уже изучали в этом курсе. Мы уже рассмотрели его реализацию через циклы:
-<code>
+<code javascript>
 const binarySearch = (items, value) => {
   let left = 0;
@@ Строка 216: / Строка 216: @@
 </code>
-Python
-<code>
+<details>
+<summary>Python</summary>
+<code python>
 def binary_search(items, value):
     left = 0
@@ Строка 242: / Строка 244: @@
 print(binary_search(items, 7))  # => 5
 </code>
+</details>
-PHP
+<details>
+<summary>PHP</summary>
-<code>
+<code php>
 <?php
@@ Строка 275: / Строка 279: @@
 print_r(binarySearch($items, 7)); // => 5
 </code>
+</details>
-Java
+<details>
+<summary>Java</summary>
-<code>
+<code java>
 class App {
     public static int binarySearch(List<Integer> items, int value) {
@@ Строка 307: / Строка 313: @@
 App.binarySearch(items, 7); // 5
 </code>
+</details>
 Тогда мы описывали алгоритм через циклы, поэтому объяснение было подробным и сложным. Алгоритм бинарного поиска можно описать намного проще, если опираться на знания о рекурсии:
@@ Строка 317: / Строка 324: @@
 И это все: мы свели задачу поиска к самой себе. Сначала зона поиска — это весь массив, но на каждом шаге она сужается в два раза. Если нужного элемента в массиве не окажется, зона поиска сузится до пустого массива, и поиск завершится неудачно:
-<code>
+<code javascript>
 const binarySearch = (items, value, left, right) => {
   if (left > right) {
@@ Строка 341: / Строка 348: @@
 </code>
-Python
+<details>
+<summary>Python</summary>
-<code>
+<code python>
 def binary_search(items, value, left, right):
     if left > right:
@@ Строка 364: / Строка 372: @@
 print(binary_search(items, 7, 0, len(items) - 1))  # => 5
 </code>
+</details>
-PHP
+<details>
+<summary>PHP</summary>
-<code>
+<code php>
 <?php
@@ Строка 393: / Строка 403: @@
 print_r(binarySearch(items, 7, 0, items.length - 1)); // => 5
 </code>
+</details>
-Java
+<details>
+<summary>Java</summary>
-<code>
+<code java>
 class App {
     public static int binarySearch(List<Integer> items, int value, int left, int right) {
@@ Строка 422: / Строка 434: @@
 App.binarySearch(items, 7, 0, items.size() - 1); // 5
 </code>
+</details>
 https://replit.com/@hexlet/algorithms-recursion
@@ Строка 431: / Строка 444: @@
 ===== Рекурсивный алгоритм для Ханойской башни =====
-{{https://cdn2.hexlet.io/derivations/image/original/eyJpZCI6IjY1NDQ2Mzg5NDE3MzE5NjQ4OTFmMWM5ZGRjMTViZjdhLmpwZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=5cd19f7555be298f6279b9f25069feea31d7d5b535e44c77358cf4730ecca7b6|eyJpZCI6IjY1NDQ2Mzg5NDE3MzE5NjQ4OTFmMWM5ZGRjMTViZjdhLmpwZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=5cd19f7555be298f6279b9f25069feea31d7d5b535e44c77358cf4730ecca7b6}}Ханойская башня — это знаменитая древняя головоломка. Она состоит из трех стержней, на один из которых надеты кольца разного размера.
+{{ :basics_of_algorithms:image_processing20231003-23-yrsg1a.jpg |}}
+Ханойская башня — это знаменитая древняя головоломка. Она состоит из трех стержней, на один из которых надеты кольца разного размера.
 Надо перенести все кольца на другой стержень, при этом кольца можно переносить только по одному. Главное правило: никогда нельзя класть кольцо большего размера на кольцо меньшего.
@@ Строка 459: / Строка 474: @@
 Только мы знаем, что рекурсия должна где-то останавливаться. В нашем случае минимальная задача, которую мы можем решить — перенос башни из одного кольца. Она решается тривиально: одно кольцо мы можем перенести безо всяких условий, поэтому нам достаточно просто вывести номера стержней «откуда» и «куда»:
-<code>
+<code javascript>
 const hanoi = (height, from, to) => {
   if (height === 1) {
@@ Строка 490: / Строка 505: @@
 </code>
-Python
-<code>
+<details>
+<summary>Python</summary>
+<code python>
 def hanoi(height, start, to):
     if height == 1:
@@ Строка 520: / Строка 537: @@
 # => с 3 на 2
 </code>
+</details>
-PHP
+<details>
+<summary>PHP</summary>
-<code>
+<code php>
 <?php
@@ Строка 556: / Строка 575: @@
 // => с 3 на 2
 </code>
+</details>
-Java
+<details>
+<summary>Java</summary>
-<code>
+<code java>
 class App {
     public static void hanoi(int height, int from, int to) {
@@ Строка 591: / Строка 612: @@
 // => с 3 на 2
 </code>
+</details>
 https://replit.com/@hexlet/hanoi
@@ Строка 600: / Строка 622: @@
 Чтобы определить номер вспомогательного стержня, надо написать сложное условие:
-<code>
+<code javascript>
 if (from === 1 && to === 2 || from === 2 && to === 1) {
   temporary = 3;
@@ Строка 610: / Строка 632: @@
 </code>
-Python
+<details>
+<summary>Python</summary>
-<code>
+<code python>
 if (start == 1 and to == 2) or (start == 2 and to == 1):
     temporary = 3
@@ Строка 621: / Строка 644: @@
 </code>
-PHP
+</details>
+<details>
+<summary>PHP</summary>
-<code>
+<code php>
 <?php
@@ Строка 634: / Строка 660: @@
 }
 </code>
+</details>
-Java
+<details>
+<summary>Java</summary>
-<code>
+<code java>
 if (from == 1 && to == 2 || from == 2 && to == 1) {
     temporary = 3;
@@ Строка 646: / Строка 674: @@
 }
 </code>
+</details>
 Несмотря на то, что логика этого кода понятна, само условие выглядит громоздким. Разберем по шагам, как оно работает. В коде используют три константы:
@@ Строка 657: / Строка 686: @@
 Обратите внимание, что сумма ''from'', ''to'' и ''temporary'' всегда равна 6. Можно взять число 6 и вычесть из него номера стержней ''from'' и ''to'', и тогда мы узнаем номер вспомогательного стержня:
-<code>
+<code javascript>
 const temporary = 6 - from - to;
 </code>
-Python
+<details>
+<summary>Python</summary>
-<code>
+<code python>
 temporary = 6 - start - to
 </code>
+</details>
-PHP
+<details>
+<summary>PHP</summary>
-<code>
+<code php>
 <?php
 $temporary = 6 - $start - $to;
 </code>
+</details>
-Java
+<details>
+<summary>Java</summary>
-<code>
+<code java>
 var temporary = 6 - from - to;
 </code>
+</details>
 Этот код гораздо проще, но требует разъяснений. В начале каждой рекурсивной функции мы должны проверить **граничное условие** — оно помогает не войти в бесконечный вызов. В задаче о ханойской башне граничное условие — это башня из одного кольца.
@@ Строка 685: / Строка 720: @@
 Если встретилась такая башня, надо перенести кольцо и завершить работу:
-<code>
+<code javascript>
 if (height === 1) {
   console.log("с %d на %d", from, to);
@@ Строка 692: / Строка 727: @@
 </code>
-Python
+<details>
+<summary>Python</summary>
-<code>
+<code python>
 if height == 1:
     print(f'с {start} на {to}')
     return
 </code>
+</details>
-PHP
+<details>
+<summary>PHP</summary>
-<code>
+<code php>
 <?php
@@ Строка 710: / Строка 748: @@
 }
 </code>
+</details>
-Java
+<details>
+<summary>Java</summary>
-<code>
+<code java>
 if (height == 1) {
     System.out.println(String.format("с %d на %d", from, to));
@@ Строка 719: / Строка 759: @@
 }
 </code>
+</details>
 Если высота башни ''height'' больше единицы, мы упрощаем задачу и сводим ее к самой себе. В случае ханойской башни такая задача — перенести башни высотой ''height - 1'' на вспомогательный стержень. После этого можно перенести самое большое кольцо на стержень «куда», а потом — переместить на него маленькую башню со вспомогательного стержня:
-<code>
+<code javascript>
 hanoi(height - 1, from, temporary);
 console.log("с %d на %d", from, to);
@@ Строка 728: / Строка 769: @@
 </code>
-Python
+<details>
+<summary>Python</summary>
-<code>
+<code python>
 hanoi(height - 1, start, temporary)
 print(f'с {start} на {to}');
 hanoi(height - 1, temporary, to)
 </code>
+</details>
-PHP
+<details>
+<summary>PHP</summary>
-<code>
+<code php>
 <?php
@@ Строка 745: / Строка 789: @@
 hanoi($height - 1, $temporary, $to);
 </code>
+</details>
-Java
+<details>
+<summary>Java</summary>
-<code>
+<code java>
 hanoi(height - 1, from, temporary);
 System.out.println(String.format("с %d на %d", from, to));
 hanoi(height - 1, temporary, to);
 </code>
+</details>
 ===== Достоинства и недостатки рекурсии =====
@@ Строка 760: / Строка 807: @@
 Еще один плюс — знания о рекурсии открывают программисту новые возможности. Многие задачи можно решить и с помощью циклов, но есть и те, в которых не обойтись без рекурсии. Например, синтаксический разбор арифметических выражений можно сделать только рекурсивно. Вот так выглядит сложное арифметическое выражение, если решать его через рекурсивный алгоритм:
-<code>
+<code javascript>
 sin(a) + (3 + 2 * b ** 7 - cos (a / b))
 </code>

Инструменты пользователя

Инструменты сайта

Различия

Инструменты страницы