Инструменты пользователя
basics_of_algorithms:recursion
Различия
Здесь показаны различия между двумя версиями данной страницы.
| Следующая версия | Предыдущая версия | ||
|
basics_of_algorithms:recursion [2023/10/03 22:08] werwolf создано |
basics_of_algorithms:recursion [2023/10/04 21:22] (текущий) werwolf [Достоинства и недостатки рекурсии] |
||
|---|---|---|---|
| Строка 9: | Строка 9: | ||
| Рекурсия — это вызов функции из этой же самой функции. Такое определение может показаться и простым, и непонятным одновременно. Чтобы стало понятнее, посмотрим на такую, самую простую рекурсивную функцию: | Рекурсия — это вызов функции из этой же самой функции. Такое определение может показаться и простым, и непонятным одновременно. Чтобы стало понятнее, посмотрим на такую, самую простую рекурсивную функцию: | ||
| - | <code> | + | <code javascript> |
| const f = () => { | const f = () => { | ||
| f(); | f(); | ||
| Строка 15: | Строка 15: | ||
| </code> | </code> | ||
| - | Python | + | <details> |
| + | <summary>Python</summary> | ||
| - | <code> | + | <code python> |
| def function(): | def function(): | ||
| function() | function() | ||
| </code> | </code> | ||
| + | </details> | ||
| - | PHP | + | <details> |
| + | <summary>PHP</summary> | ||
| - | <code> | + | <code php> |
| <?php | <?php | ||
| Строка 32: | Строка 35: | ||
| } | } | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Java | ||
| - | <code> | + | <details> |
| + | <summary>Java</summary> | ||
| + | |||
| + | <code java> | ||
| class App { | class App { | ||
| public static void f() { | public static void f() { | ||
| Строка 42: | Строка 48: | ||
| } | } | ||
| </code> | </code> | ||
| + | </details> | ||
| Этот вызов будет выполняться бесконечно. Кажется, что в этом нет никакого смысла, но это не так — мы докажем это на примере. Попробуем решить такую задачу: посчитать сумму чисел от 1 до 100. | Этот вызов будет выполняться бесконечно. Кажется, что в этом нет никакого смысла, но это не так — мы докажем это на примере. Попробуем решить такую задачу: посчитать сумму чисел от 1 до 100. | ||
| Строка 47: | Строка 54: | ||
| Представим, что мы уже знаем сумму чисел от 1 до 99. Тогда надо просто прибавить к ней 100: | Представим, что мы уже знаем сумму чисел от 1 до 99. Тогда надо просто прибавить к ней 100: | ||
| - | <code> | + | <code javascript> |
| sum(100) = 100 + sum(99) | sum(100) = 100 + sum(99) | ||
| </code> | </code> | ||
| Строка 53: | Строка 60: | ||
| А если мы не знаем сумму чисел от 1 до 99? Тогда нужно вычислить ее, сложив 99 и сумму чисел от 1 до 98: | А если мы не знаем сумму чисел от 1 до 99? Тогда нужно вычислить ее, сложив 99 и сумму чисел от 1 до 98: | ||
| - | <code> | + | <code javascript> |
| sum(99) = 99 + sum(98) | sum(99) = 99 + sum(98) | ||
| </code> | </code> | ||
| Строка 59: | Строка 66: | ||
| По такой же логике мы будем продвигаться еще много раз. В итоге мы увидим, что программу можно свести к решению такой же задачи, но с меньшим параметром: | По такой же логике мы будем продвигаться еще много раз. В итоге мы увидим, что программу можно свести к решению такой же задачи, но с меньшим параметром: | ||
| - | <code> | + | <code javascript> |
| const sum = (n) => { | const sum = (n) => { | ||
| return n + sum(n - 1); | return n + sum(n - 1); | ||
| Строка 65: | Строка 72: | ||
| </code> | </code> | ||
| - | Python | + | <details> |
| + | <summary>Python</summary> | ||
| - | <code> | + | <code python> |
| def sum(n): | def sum(n): | ||
| return n + sum(n - 1) | return n + sum(n - 1) | ||
| </code> | </code> | ||
| + | </details> | ||
| - | PHP | + | <details> |
| + | <summary>PHP</summary> | ||
| - | <code> | + | <code php> |
| <?php | <?php | ||
| Строка 82: | Строка 92: | ||
| } | } | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Java | + | <details> |
| + | <summary>Java</summary> | ||
| - | <code> | + | <code java> |
| class App { | class App { | ||
| public static int sum(int n) { | public static int sum(int n) { | ||
| Строка 92: | Строка 104: | ||
| } | } | ||
| </code> | </code> | ||
| + | </details> | ||
| У нас получилась рекурсивная функция. В таком виде она будет работать бесконечно: сначала параметр n уменьшается до 0, потом становится равным -1, -2 и так далее. | У нас получилась рекурсивная функция. В таком виде она будет работать бесконечно: сначала параметр n уменьшается до 0, потом становится равным -1, -2 и так далее. | ||
| Строка 97: | Строка 110: | ||
| Нужно придумать, как остановить бесконечный вызов. Напишем код, который остановит функцию тогда, когда она дойдет до единицы. Это кажется логичным несмотря на то, что мы не можем подсчитать сумму чисел от 1 до 1. Мы берем число 1, и ни с чем его не складываем: | Нужно придумать, как остановить бесконечный вызов. Напишем код, который остановит функцию тогда, когда она дойдет до единицы. Это кажется логичным несмотря на то, что мы не можем подсчитать сумму чисел от 1 до 1. Мы берем число 1, и ни с чем его не складываем: | ||
| - | <code> | + | <code javascript> |
| sum(1) = 1 | sum(1) = 1 | ||
| </code> | </code> | ||
| Строка 103: | Строка 116: | ||
| У нас получается рекурсивная функция ''sum'': | У нас получается рекурсивная функция ''sum'': | ||
| - | <code> | + | <code javascript> |
| const sum = (n) => { | const sum = (n) => { | ||
| if (n === 1) { | if (n === 1) { | ||
| Строка 115: | Строка 128: | ||
| </code> | </code> | ||
| - | Python | ||
| - | <code> | + | <details> |
| + | <summary>Python</summary> | ||
| + | |||
| + | <code python> | ||
| def sum(n): | def sum(n): | ||
| if n == 1: | if n == 1: | ||
| Строка 126: | Строка 141: | ||
| sum(100) # <= 5050 | sum(100) # <= 5050 | ||
| </code> | </code> | ||
| + | </details> | ||
| - | PHP | + | <details> |
| + | <summary>PHP</summary> | ||
| - | <code> | + | <code php> |
| <?php | <?php | ||
| Строка 143: | Строка 160: | ||
| sum(100) // <= 5050 | sum(100) // <= 5050 | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Java | + | <details> |
| + | <summary>Java</summary> | ||
| - | <code> | + | <code java> |
| class App { | class App { | ||
| public static int sum(int n) { | public static int sum(int n) { | ||
| Строка 159: | Строка 178: | ||
| App.sum(100); // 5050 | App.sum(100); // 5050 | ||
| </code> | </code> | ||
| + | </details> | ||
| Теперь рекурсивная функция остановится после ста вызовов и вычислит сумму чисел от 1 до 100. | Теперь рекурсивная функция остановится после ста вызовов и вычислит сумму чисел от 1 до 100. | ||
| Строка 168: | Строка 188: | ||
| Один из распространенных алгоритмов в программировании — это **бинарный поиск**, который мы уже изучали в этом курсе. Мы уже рассмотрели его реализацию через циклы: | Один из распространенных алгоритмов в программировании — это **бинарный поиск**, который мы уже изучали в этом курсе. Мы уже рассмотрели его реализацию через циклы: | ||
| - | <code> | + | <code javascript> |
| const binarySearch = (items, value) => { | const binarySearch = (items, value) => { | ||
| let left = 0; | let left = 0; | ||
| Строка 196: | Строка 216: | ||
| </code> | </code> | ||
| - | Python | ||
| - | <code> | + | <details> |
| + | <summary>Python</summary> | ||
| + | |||
| + | <code python> | ||
| def binary_search(items, value): | def binary_search(items, value): | ||
| left = 0 | left = 0 | ||
| Строка 222: | Строка 244: | ||
| print(binary_search(items, 7)) # => 5 | print(binary_search(items, 7)) # => 5 | ||
| </code> | </code> | ||
| + | </details> | ||
| - | PHP | + | <details> |
| + | <summary>PHP</summary> | ||
| - | <code> | + | <code php> |
| <?php | <?php | ||
| Строка 255: | Строка 279: | ||
| print_r(binarySearch($items, 7)); // => 5 | print_r(binarySearch($items, 7)); // => 5 | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Java | + | <details> |
| + | <summary>Java</summary> | ||
| - | <code> | + | <code java> |
| class App { | class App { | ||
| public static int binarySearch(List<Integer> items, int value) { | public static int binarySearch(List<Integer> items, int value) { | ||
| Строка 287: | Строка 313: | ||
| App.binarySearch(items, 7); // 5 | App.binarySearch(items, 7); // 5 | ||
| </code> | </code> | ||
| + | </details> | ||
| Тогда мы описывали алгоритм через циклы, поэтому объяснение было подробным и сложным. Алгоритм бинарного поиска можно описать намного проще, если опираться на знания о рекурсии: | Тогда мы описывали алгоритм через циклы, поэтому объяснение было подробным и сложным. Алгоритм бинарного поиска можно описать намного проще, если опираться на знания о рекурсии: | ||
| Строка 297: | Строка 324: | ||
| И это все: мы свели задачу поиска к самой себе. Сначала зона поиска — это весь массив, но на каждом шаге она сужается в два раза. Если нужного элемента в массиве не окажется, зона поиска сузится до пустого массива, и поиск завершится неудачно: | И это все: мы свели задачу поиска к самой себе. Сначала зона поиска — это весь массив, но на каждом шаге она сужается в два раза. Если нужного элемента в массиве не окажется, зона поиска сузится до пустого массива, и поиск завершится неудачно: | ||
| - | <code> | + | <code javascript> |
| const binarySearch = (items, value, left, right) => { | const binarySearch = (items, value, left, right) => { | ||
| if (left > right) { | if (left > right) { | ||
| Строка 321: | Строка 348: | ||
| </code> | </code> | ||
| - | Python | + | <details> |
| + | <summary>Python</summary> | ||
| - | <code> | + | <code python> |
| def binary_search(items, value, left, right): | def binary_search(items, value, left, right): | ||
| if left > right: | if left > right: | ||
| Строка 344: | Строка 372: | ||
| print(binary_search(items, 7, 0, len(items) - 1)) # => 5 | print(binary_search(items, 7, 0, len(items) - 1)) # => 5 | ||
| </code> | </code> | ||
| + | </details> | ||
| - | PHP | + | <details> |
| + | <summary>PHP</summary> | ||
| - | <code> | + | <code php> |
| <?php | <?php | ||
| Строка 373: | Строка 403: | ||
| print_r(binarySearch(items, 7, 0, items.length - 1)); // => 5 | print_r(binarySearch(items, 7, 0, items.length - 1)); // => 5 | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Java | + | <details> |
| + | <summary>Java</summary> | ||
| - | <code> | + | <code java> |
| class App { | class App { | ||
| public static int binarySearch(List<Integer> items, int value, int left, int right) { | public static int binarySearch(List<Integer> items, int value, int left, int right) { | ||
| Строка 402: | Строка 434: | ||
| App.binarySearch(items, 7, 0, items.size() - 1); // 5 | App.binarySearch(items, 7, 0, items.size() - 1); // 5 | ||
| </code> | </code> | ||
| + | </details> | ||
| https://replit.com/@hexlet/algorithms-recursion | https://replit.com/@hexlet/algorithms-recursion | ||
| Строка 411: | Строка 444: | ||
| ===== Рекурсивный алгоритм для Ханойской башни ===== | ===== Рекурсивный алгоритм для Ханойской башни ===== | ||
| - | {{https://cdn2.hexlet.io/derivations/image/original/eyJpZCI6IjY1NDQ2Mzg5NDE3MzE5NjQ4OTFmMWM5ZGRjMTViZjdhLmpwZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=5cd19f7555be298f6279b9f25069feea31d7d5b535e44c77358cf4730ecca7b6|eyJpZCI6IjY1NDQ2Mzg5NDE3MzE5NjQ4OTFmMWM5ZGRjMTViZjdhLmpwZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=5cd19f7555be298f6279b9f25069feea31d7d5b535e44c77358cf4730ecca7b6}}Ханойская башня — это знаменитая древняя головоломка. Она состоит из трех стержней, на один из которых надеты кольца разного размера. | + | {{ :basics_of_algorithms:image_processing20231003-23-yrsg1a.jpg |}} |
| + | |||
| + | Ханойская башня — это знаменитая древняя головоломка. Она состоит из трех стержней, на один из которых надеты кольца разного размера. | ||
| Надо перенести все кольца на другой стержень, при этом кольца можно переносить только по одному. Главное правило: никогда нельзя класть кольцо большего размера на кольцо меньшего. | Надо перенести все кольца на другой стержень, при этом кольца можно переносить только по одному. Главное правило: никогда нельзя класть кольцо большего размера на кольцо меньшего. | ||
| Строка 439: | Строка 474: | ||
| Только мы знаем, что рекурсия должна где-то останавливаться. В нашем случае минимальная задача, которую мы можем решить — перенос башни из одного кольца. Она решается тривиально: одно кольцо мы можем перенести безо всяких условий, поэтому нам достаточно просто вывести номера стержней «откуда» и «куда»: | Только мы знаем, что рекурсия должна где-то останавливаться. В нашем случае минимальная задача, которую мы можем решить — перенос башни из одного кольца. Она решается тривиально: одно кольцо мы можем перенести безо всяких условий, поэтому нам достаточно просто вывести номера стержней «откуда» и «куда»: | ||
| - | <code> | + | <code javascript> |
| const hanoi = (height, from, to) => { | const hanoi = (height, from, to) => { | ||
| if (height === 1) { | if (height === 1) { | ||
| Строка 470: | Строка 505: | ||
| </code> | </code> | ||
| - | Python | ||
| - | <code> | + | <details> |
| + | <summary>Python</summary> | ||
| + | |||
| + | <code python> | ||
| def hanoi(height, start, to): | def hanoi(height, start, to): | ||
| if height == 1: | if height == 1: | ||
| Строка 500: | Строка 537: | ||
| # => с 3 на 2 | # => с 3 на 2 | ||
| </code> | </code> | ||
| + | </details> | ||
| - | PHP | + | <details> |
| + | <summary>PHP</summary> | ||
| - | <code> | + | <code php> |
| <?php | <?php | ||
| Строка 536: | Строка 575: | ||
| // => с 3 на 2 | // => с 3 на 2 | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Java | + | <details> |
| + | <summary>Java</summary> | ||
| - | <code> | + | <code java> |
| class App { | class App { | ||
| public static void hanoi(int height, int from, int to) { | public static void hanoi(int height, int from, int to) { | ||
| Строка 571: | Строка 612: | ||
| // => с 3 на 2 | // => с 3 на 2 | ||
| </code> | </code> | ||
| + | </details> | ||
| https://replit.com/@hexlet/hanoi | https://replit.com/@hexlet/hanoi | ||
| Строка 580: | Строка 622: | ||
| Чтобы определить номер вспомогательного стержня, надо написать сложное условие: | Чтобы определить номер вспомогательного стержня, надо написать сложное условие: | ||
| - | <code> | + | <code javascript> |
| if (from === 1 && to === 2 || from === 2 && to === 1) { | if (from === 1 && to === 2 || from === 2 && to === 1) { | ||
| temporary = 3; | temporary = 3; | ||
| Строка 590: | Строка 632: | ||
| </code> | </code> | ||
| - | Python | + | <details> |
| + | <summary>Python</summary> | ||
| - | <code> | + | <code python> |
| if (start == 1 and to == 2) or (start == 2 and to == 1): | if (start == 1 and to == 2) or (start == 2 and to == 1): | ||
| temporary = 3 | temporary = 3 | ||
| Строка 601: | Строка 644: | ||
| </code> | </code> | ||
| - | PHP | + | </details> |
| + | |||
| + | <details> | ||
| + | <summary>PHP</summary> | ||
| - | <code> | + | <code php> |
| <?php | <?php | ||
| Строка 614: | Строка 660: | ||
| } | } | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Java | + | <details> |
| + | <summary>Java</summary> | ||
| - | <code> | + | <code java> |
| if (from == 1 && to == 2 || from == 2 && to == 1) { | if (from == 1 && to == 2 || from == 2 && to == 1) { | ||
| temporary = 3; | temporary = 3; | ||
| Строка 626: | Строка 674: | ||
| } | } | ||
| </code> | </code> | ||
| + | </details> | ||
| Несмотря на то, что логика этого кода понятна, само условие выглядит громоздким. Разберем по шагам, как оно работает. В коде используют три константы: | Несмотря на то, что логика этого кода понятна, само условие выглядит громоздким. Разберем по шагам, как оно работает. В коде используют три константы: | ||
| Строка 637: | Строка 686: | ||
| Обратите внимание, что сумма ''from'', ''to'' и ''temporary'' всегда равна 6. Можно взять число 6 и вычесть из него номера стержней ''from'' и ''to'', и тогда мы узнаем номер вспомогательного стержня: | Обратите внимание, что сумма ''from'', ''to'' и ''temporary'' всегда равна 6. Можно взять число 6 и вычесть из него номера стержней ''from'' и ''to'', и тогда мы узнаем номер вспомогательного стержня: | ||
| - | <code> | + | <code javascript> |
| const temporary = 6 - from - to; | const temporary = 6 - from - to; | ||
| </code> | </code> | ||
| - | Python | + | <details> |
| + | <summary>Python</summary> | ||
| - | <code> | + | <code python> |
| temporary = 6 - start - to | temporary = 6 - start - to | ||
| </code> | </code> | ||
| + | </details> | ||
| - | PHP | + | <details> |
| + | <summary>PHP</summary> | ||
| - | <code> | + | <code php> |
| <?php | <?php | ||
| $temporary = 6 - $start - $to; | $temporary = 6 - $start - $to; | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Java | + | <details> |
| + | <summary>Java</summary> | ||
| - | <code> | + | <code java> |
| var temporary = 6 - from - to; | var temporary = 6 - from - to; | ||
| </code> | </code> | ||
| + | </details> | ||
| Этот код гораздо проще, но требует разъяснений. В начале каждой рекурсивной функции мы должны проверить **граничное условие** — оно помогает не войти в бесконечный вызов. В задаче о ханойской башне граничное условие — это башня из одного кольца. | Этот код гораздо проще, но требует разъяснений. В начале каждой рекурсивной функции мы должны проверить **граничное условие** — оно помогает не войти в бесконечный вызов. В задаче о ханойской башне граничное условие — это башня из одного кольца. | ||
| Строка 665: | Строка 720: | ||
| Если встретилась такая башня, надо перенести кольцо и завершить работу: | Если встретилась такая башня, надо перенести кольцо и завершить работу: | ||
| - | <code> | + | <code javascript> |
| if (height === 1) { | if (height === 1) { | ||
| console.log("с %d на %d", from, to); | console.log("с %d на %d", from, to); | ||
| Строка 672: | Строка 727: | ||
| </code> | </code> | ||
| - | Python | + | <details> |
| + | <summary>Python</summary> | ||
| - | <code> | + | <code python> |
| if height == 1: | if height == 1: | ||
| print(f'с {start} на {to}') | print(f'с {start} на {to}') | ||
| return | return | ||
| </code> | </code> | ||
| + | </details> | ||
| - | PHP | + | <details> |
| + | <summary>PHP</summary> | ||
| - | <code> | + | <code php> |
| <?php | <?php | ||
| Строка 690: | Строка 748: | ||
| } | } | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Java | + | <details> |
| + | <summary>Java</summary> | ||
| - | <code> | + | <code java> |
| if (height == 1) { | if (height == 1) { | ||
| System.out.println(String.format("с %d на %d", from, to)); | System.out.println(String.format("с %d на %d", from, to)); | ||
| Строка 699: | Строка 759: | ||
| } | } | ||
| </code> | </code> | ||
| + | </details> | ||
| Если высота башни ''height'' больше единицы, мы упрощаем задачу и сводим ее к самой себе. В случае ханойской башни такая задача — перенести башни высотой ''height - 1'' на вспомогательный стержень. После этого можно перенести самое большое кольцо на стержень «куда», а потом — переместить на него маленькую башню со вспомогательного стержня: | Если высота башни ''height'' больше единицы, мы упрощаем задачу и сводим ее к самой себе. В случае ханойской башни такая задача — перенести башни высотой ''height - 1'' на вспомогательный стержень. После этого можно перенести самое большое кольцо на стержень «куда», а потом — переместить на него маленькую башню со вспомогательного стержня: | ||
| - | <code> | + | <code javascript> |
| hanoi(height - 1, from, temporary); | hanoi(height - 1, from, temporary); | ||
| console.log("с %d на %d", from, to); | console.log("с %d на %d", from, to); | ||
| Строка 708: | Строка 769: | ||
| </code> | </code> | ||
| - | Python | + | <details> |
| + | <summary>Python</summary> | ||
| - | <code> | + | <code python> |
| hanoi(height - 1, start, temporary) | hanoi(height - 1, start, temporary) | ||
| print(f'с {start} на {to}'); | print(f'с {start} на {to}'); | ||
| hanoi(height - 1, temporary, to) | hanoi(height - 1, temporary, to) | ||
| </code> | </code> | ||
| + | </details> | ||
| - | PHP | + | <details> |
| + | <summary>PHP</summary> | ||
| - | <code> | + | <code php> |
| <?php | <?php | ||
| Строка 725: | Строка 789: | ||
| hanoi($height - 1, $temporary, $to); | hanoi($height - 1, $temporary, $to); | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Java | + | <details> |
| + | <summary>Java</summary> | ||
| - | <code> | + | <code java> |
| hanoi(height - 1, from, temporary); | hanoi(height - 1, from, temporary); | ||
| System.out.println(String.format("с %d на %d", from, to)); | System.out.println(String.format("с %d на %d", from, to)); | ||
| hanoi(height - 1, temporary, to); | hanoi(height - 1, temporary, to); | ||
| </code> | </code> | ||
| + | </details> | ||
| ===== Достоинства и недостатки рекурсии ===== | ===== Достоинства и недостатки рекурсии ===== | ||
| Строка 740: | Строка 807: | ||
| Еще один плюс — знания о рекурсии открывают программисту новые возможности. Многие задачи можно решить и с помощью циклов, но есть и те, в которых не обойтись без рекурсии. Например, синтаксический разбор арифметических выражений можно сделать только рекурсивно. Вот так выглядит сложное арифметическое выражение, если решать его через рекурсивный алгоритм: | Еще один плюс — знания о рекурсии открывают программисту новые возможности. Многие задачи можно решить и с помощью циклов, но есть и те, в которых не обойтись без рекурсии. Например, синтаксический разбор арифметических выражений можно сделать только рекурсивно. Вот так выглядит сложное арифметическое выражение, если решать его через рекурсивный алгоритм: | ||
| - | <code> | + | <code javascript> |
| sin(a) + (3 + 2 * b ** 7 - cos (a / b)) | sin(a) + (3 + 2 * b ** 7 - cos (a / b)) | ||
| </code> | </code> | ||
basics_of_algorithms/recursion.1696360087.txt.gz · Последние изменения: 2023/10/03 22:08 — werwolf
Инструменты страницы
Если не указано иное, содержимое этой вики предоставляется на условиях следующей лицензии: CC Attribution-Share Alike 4.0 International
