Как ускорить рекурсию питон

Мне нужно ускорить рекурсию

Мне задали решить задачу. Я написал код, но он работает медленно. Мне нужно ускорить рекурсию. Если n будет равен даже 70 расчеты займет очень много времени. Помогите мне улучшить мой код. Максимальное n может быть 500!

def a(n): if n == 1: return 1 if n == 2: return 2 return 1 + a(n - a(a(n - 1))) 

Отслеживать
задан 29 окт 2020 в 19:01
130 15 15 бронзовых знаков
вы бы еще сказали что эта рекурсия делает, может можно было бы обойтись и без рекурсии
29 окт 2020 в 19:05

2 ответа 2

Сортировка: Сброс на вариант по умолчанию

дело в том, что функция a(n) вызывается многократно, а значит рекурсий больше, чем нужно

можно вычислить a(n) однократно и дальше только использовать уже вычисленные значения

res = [0 for _ in range(1000)] def a(n): if res[n] == 0: if n > 2: res[n] = 1 + a(n - a(a(n - 1))) elif n == 1: res[n] = 1 elif n == 2: res[n] = 2 return res[n] print(a(900)) 

a(900) работает мгновенно, так что можно считать это оптимизацией 🙂

только учтите одну важную вещь, я не знаю как у питона, но при рекурсии у того же c++ вызовы запихиваются в стек и стек может просто переполниться

в моем примере при n = 1000 питон уже ругается

RecursionError: maximum recursion depth exceeded in comparison 

P.S.

в коде много if, поэтому лучше сделать ее покороче

res = [0, 1, 2] + [0 for _ in range(10)] def a(n): if res[n] == 0: res[n] = 1 + a(n - a(a(n - 1))) return res[n] print(a(10)) 

да и вообще зачем нам эти if?

res = [0, 1, 2] + [0 for _ in range(20)] def a(n): res[n] = res[n] or (1 + a(n - a(a(n - 1)))) return res[n] print(res) 

Продвинутый взгляд на рекурсию

Рекурсия является одним из наиболее мощных подходов в программировании. С ее помощью можно решать чрезвычайно сложные задачи, печатая при этом невероятно малый объем кода. Тем не менее понимание данного принципа нередко вызывает сложности, поскольку для этого требуется нестандартный взгляд на процесс выполнения команд.

Сложность примеров, описанных в данной статье, будет возрастать постепенно, начиная от самых простых и заканчивая достаточно трудными. При этом каждый из них будет сопровождаться подробной диаграммой:

• Рекурсивный способ мышления.
• Рекуррентные соотношения.
• Мемоизация.
• Стратегия “разделяй и властвуй”.

Рекурсия используется для решения задач, в которых функция вызывает сама себя в рамках собственного определения. В каждой реализации рекурсии должно присутствовать два элемента:

• Заключительный базовый кейс или кейсы, в которых рекурсивный поиск ответа более не производится.
• Набор правил (рекуррентных соотношений), который инициирует очередные циклы рекурсии, сводя таким образом общие кейсы к базовому.

В качестве примера давайте рассмотрим задачу по выводу развернутого варианта строки. В этом случае на выходе из вводного слова ‘hello’ должно получиться ‘olleh’. Итеративный метод решения этой задачи — применение цикла for и вывод каждого знака, начиная с последнего и заканчивая первым.

В рекурсивном же подходе мы сначала создаем функцию reverseString , получающую интересующую нас строку в качестве параметра. Если длина ввода не равна 0, то такой кейс является базовым или заключительным, и мы выводим последнюю букву, а затем инициируем еще один экземпляр reverseString для той же строки, исключив последнюю букву, поскольку ее мы уже вывели.

Обратите внимание: поскольку функция вызывается изнутри себя, она сама создает цикл for . Кроме того, наличие инструкции if перед вызовом другого экземпляра функции обязательно, в противном случае будет выброшена ошибка RecursionError или RuntimeError , поскольку скрипт не увидит конца бесконечного цикла. Данная ситуация аналогична бесконечному циклу While True .

Давайте посмотрим, как эта рекурсивная функция работает с ‘hello’:

Рекуррентность в более сложных задачах может вызвать трудности при определении двух ее компонентов — рекуррентного соотношения, т.е. соотношения между результатом задачи и результатом ее подзадач и базовым кейсом, представляющим кейс, который можно вычислить напрямую без дополнительных рекурсивных вызовов. Иногда базовые кейсы называются “нижними кейсами”, потому что они являются кейсами, в которых задача уменьшена до наименьшего масштаба.

Рассмотрите в качестве примера треугольник Паскаля, в котором каждое число является суммой двух, находящихся над ним, и который имеет по сторонам единицы. Как можно использовать рекурсию для нахождения значения любого значения в точке (i, j)? Каково будет рекуррентное соотношение и базовый/заключительный кейс?

Рекуррентное соотношение можно выразить следующим уравнением:

Это очевидно, когда смотришь на график треугольника. Еще более примечательно в этой формуле то, что если мы продолжим с ее помощью разбивать любую точку (i, j) на сумму двух других точек, то в итоге неизбежно получим базовый кейс — 1. Треугольник Паскаля начинается с единиц, и из их сумм строится весь сложный паттерн.

Как же нам это реализовать?

Для начала давайте найдем набор правил, чтобы определять, когда выполняется базовый кейс, при котором значение ячейки равняется 1. Обратите внимание, что 1-цы появляются при выполнении одного из двух условий: когда располагаются либо в первом столбце (j=0), либо по диагонали (i=j).

Теперь выполнить реализацию просто. Если условия для базового кейса выполнены, мы возвращаем базовое значение (1). В противном случае мы продолжаем уменьшать задачу до тех пор, пока не достигнем базового кейса, до которого, как мы определили, будет неизбежно разбит любой ввод.

Теперь рекурсия раскрылась для вас во всей красе. Здесь, с помощью всего пяти строк кода, мы, по сути, создаем саморазвивающееся дерево. При желании число строк кода можно даже уменьшить до трех. Вызывая функцию pascal дважды, мы инициируем две ветви поиска, каждая из которых также инициирует еще две, предполагая, что базовый кейс достигнут не был.

Такая эффективность рекурсии может показаться магической и даже может запутать. Давайте рассмотрим работу ее алгоритма на примере.

В соответствии с нашим рекуррентным соотношением (4, 2) разбивается на (3, 1) и (3, 2), которые являются двумя числами, стоящими над ней. Обратите внимание, что алгоритм на деле не знает, что значения этих ячеек представлены 3. Он просто учитывает их местоположение. Мы не знаем или даже не интересуемся никакими значениями, пока выполняются базовые условия. На основе базовых кейсов (1) мы можем вычислить другие не базовые точки, но для начала должны быть найдены все базовые.

Согласно нашему рекуррентному соотношению, кейсы итеративно разбиваются до тех пор, пока не достигается базовый (j = 0 или i = j). Поскольку нам известны значения этих базовых кейсов (1), мы можем заполнить и другие значения, зависимые от базового кейса.

Это, конечно же, очень, а возможно и чересчур подробное представление принципа работы рекурсивного алгоритма. В действительности ни один из этих трех шагов не нужно программировать, так как они выполняются скриптом автоматически. Все, что вам нужно, — это вызвать функцию внутри ее самой и обеспечить ее завершение в некоторых точках при достижении базового случая.

При вызове return pascal(i-1, j) + pascal(i-1, j-1) мы рассматриваем возврат не как процесс, а как число. Поскольку pascal(i-1, j) инициирует собственные процессы ветвления, а в итоге возвращает другое число (например, 3), будет правильным воспринимать его именно как число, а не как процесс, что может вызвать ненужную сложность и затруднение в понимании.

С некоторой точки зрения этот рекурсивный алгоритм можно назвать неэффективным. В конце концов ‘6′ разбивается на ‘3′, которое, с позиции значения, имеет идентичные разбивки, но при этом зачем-то вычисляется второй раз. Это стандартный случай в рекурсии, когда базовые кейсы одного кейса, будучи вычисленными ранее, вычисляются повторно. Для устранения этой проблемы мы используем мемоизацию.

Возьмите в качестве примера последовательность Фибоначчи, в которой первые два числа представлены 0 и 1, а последующие числа являются суммой двух, им предшествующих. На основе уже сформированного знания мы понимаем, что базовыми кейсами здесь будут 0 и 1, а рекуррентное соотношение будет выглядеть как v(i) = v(i-2) + v(i-1). В таком случае мы можем построить простую рекурсивную функцию для нахождения значения последовательности Фибоначчи в любом индексе, начиная с 0.

Обратите внимание, что хоть это и грамотное применение рекурсии, оно весьма неэффективно. 8 разбивается на 3 и 5, а 5, в свою очередь, разбивается на 3 и 2. Мы вычисляем все с самого начала и строим завершенное дерево поиска со множеством повторений.

С помощью мемоизации мы можем решить эту проблему, создав кэш. Это можно реализовать, используя словарь и сохраняя значения, заданные ранее. Например, когда индекс 6 (значение 8) разбивается на индекс 4 и индекс 5 (значения 3 и 5), мы можем сохранить значение индекса 4 в кэше. При вычислении индекса 5 как индекса 3 плюс индекс 4 мы можем извлечь индекс 4 из кэша вместо того, чтобы повторно вычислять его, создавая еще одно обширное дерево, ведущее к базовым кейсам.

Чтобы включить в нашу функцию мемоизацию, мы добавим две функциональности: во-первых, если текущий индекс был сохранен в кэше, мы будем просто возвращать его сохраненное значение; во-вторых, прежде чем продолжать уменьшать значение, мы будем добавлять это значение к кэшу,чтобы ускорить дальнейшие операции. Обратите внимание, что кэш должен быть либо глобальной переменной, либо такой, которую можно извлечь и изменить независимо от области вызова команды.

После добавления мемоизации наша рекурсивная функция стала намного быстрее и мощнее.

Рекурсия занимает центральное место среди многих наибыстрейших алгоритмов сортировки. Цель этих алгоритмов — получить список чисел и вернуть их в порядке от меньшего к большему. Поскольку очень много приложений опираются на быструю сортировку, весьма важно найти такой, который сможет сортировать списки максимально быстро. При этом некоторые из самых быстрых алгоритмов используют рекурсивный подход, называемый “разделяй и властвуй”.

В стратегии “разделяй и властвуй” изначальная задача рекурсивно разбивается на несколько подзадач. После того, как каждая подзадача достигает размера единицы (аналог базового кейса), выявляются их подрешения, которые вновь рекурсивно совмещаются для формирования окончательного решения.

Рассмотрите, к примеру, QuickSort — один из наиболее быстрых алгоритмов сортировки, который при грамотной реализации может выполняться в 2–3 раза быстрее своих соперников и предшественников.

QuickSort начинает выполнение с выбора “опоры”. В простейших реализациях и для наших целей такую опору можно выбрать произвольно. Однако в более специализированных реализациях к ее выбору уже стоит подходить осторожно.

Все элементы со значениями меньше опоры переносятся левее нее, а все, чьи значения больше — правее. Выполнить это можно, пройдя по каждому элементу и переместив те, что меньше опоры, в один список, а те, что больше нее — в другой. Заметьте, что эта операция справляется с задачей только частично.

Процесс сортировки списка на основе его опорной точки называется разделением, так как опора разделяет этот список на два раздела, иначе говоря, на две стороны. Каждый их этих разделов вызывает очередную итерацию разделения сам на себя и так продолжается до тех пор, пока раздел не достигнет базового кейса (1 единицы, просто одного числа)

После достаточного числа рекурсивных вызовов исходный список будет разделен до точки, когда эти вызовы продолжить уже невозможно. В этой точке композиция подрешений выполняется простым составлением их в горизонтальном порядке. Результат такой композиции — отсортированный список.

Обратите внимание, что QuickSort следует многим из перечисленных основ рекурсии, рассмотренных нами ранее, только на более высоком уровне. Рекуррентное соотношение является разделением компонента, а базовый кейс — это разделение размера 1. Начиная с оригинального списка, те же процессы (выбор опоры и разделение) вызываются рекурсивно до тех пор, пока результат не будет состоять только из базовых кейсов.

Ключевые моменты

• Рекурсия — это подход программирования, в котором функция вызывает сама себя, допуская использование циклов и автоматическое построение дерева при минимальном количестве кода.
• При построении рекурсивной функции нужно четко понимать два ее основных элемента: рекуррентное соотношение и базовый кейс.
• Мемоизация — это метод, используемый для предотвращения повторения операций, работающий посредством сохранения информации в кэше с последующим ее извлечением при необходимости.
• Стратегия “разделяй и властвуй” — это одно из многих применений рекурсии, в котором задача рекурсивно разбивается на несколько подзадач (базовых кейсов), из которых можно с легкостью извлечь подрешения и агрегировать их в полноценное решение.

• Почему в базе данных происходит взаимоблокировка?
• Слабо контролируемое обнаружение объектов — сквозной цикл обучения
• Выбор оптимального алгоритма поиска в Python

Максимальная глубина рекурсии в Python и как её увеличить

Рекурсия — это техника в программировании, при которой функция вызывает саму себя напрямую или косвенно. Она может быть очень полезной для решения определенных задач, но имеет свои ограничения. Одно из них — максимальная глубина рекурсии.

В Python предусмотрено ограничение на максимальную глубину рекурсии, чтобы предотвратить переполнение стека и последующий сбой программы. Это ограничение обычно установлено на достаточно высоком уровне (обычно порядка 1000), но иногда, для решения определенных задач, может потребоваться увеличить этот лимит.

def factorial(n): if n == 1: return 1 else: return n * factorial(n-1) print(factorial(2000))

В этом коде функция factorial рекурсивно вызывает сама себя для вычисления факториала числа. Но при попытке вычислить факториал числа больше 1000, получаем ошибку RecursionError: maximum recursion depth exceeded in comparison .

Чтобы увеличить максимальную глубину рекурсии, можно использовать функцию sys.setrecursionlimit(limit) . Эта функция устанавливает максимальную глубину рекурсии на указанное значение. Но стоит быть осторожным, увеличивая этот лимит, так как это может привести к переполнению стека и сбою программы.

import sys sys.setrecursionlimit(3000) print(factorial(2000)) # Теперь это работает

Таким образом, хотя увеличение максимальной глубины рекурсии может быть полезным, с ним следует обращаться с осторожностью. Более того, часто большие глубины рекурсии указывают на то, что задача, возможно, может быть решена более эффективным способом, не используя рекурсию.

Рекурсия — Основы алгоритмов и структур данных

В сообществе программистов рекурсия считается не самой простой, но важной темой. Несмотря на сложность, мы решили включить ее в курс по алгоритмам для начинающих.

В этом уроке мы изучим рекурсию, потому что эти знания помогут быстрее и глубже понять алгоритмы. Более того, некоторые важные алгоритмы вообще не получится реализовать без рекурсии.

Что такое рекурсия

Рекурсия — это вызов функции из этой же самой функции. Такое определение может показаться и простым, и непонятным одновременно. Чтобы стало понятнее, посмотрим на такую, самую простую рекурсивную функцию:

const f = () =>  f(); >;

def function(): function()

php function f()  f(); >

class App  public static void f()  f(); > >

Этот вызов будет выполняться бесконечно. Кажется, что в этом нет никакого смысла, но это не так — мы докажем это на примере. Попробуем решить такую задачу: посчитать сумму чисел от 1 до 100.

Представим, что мы уже знаем сумму чисел от 1 до 99. Тогда надо просто прибавить к ней 100:

sum(100) = 100 + sum(99)

А если мы не знаем сумму чисел от 1 до 99? Тогда нужно вычислить ее, сложив 99 и сумму чисел от 1 до 98:

sum(99) = 99 + sum(98)

По такой же логике мы будем продвигаться еще много раз. В итоге мы увидим, что программу можно свести к решению такой же задачи, но с меньшим параметром:

const sum = (n) =>  return n + sum(n - 1); >;

def sum(n): return n + sum(n - 1)

php function sum($n)  return $n + sum($n - 1) >

class App  public static int sum(int n)  return n + sum(n - 1); > >

У нас получилась рекурсивная функция. В таком виде она будет работать бесконечно: сначала параметр n уменьшается до 0, потом становится равным -1, -2 и так далее.

Нужно придумать, как остановить бесконечный вызов. Напишем код, который остановит функцию тогда, когда она дойдет до единицы. Это кажется логичным несмотря на то, что мы не можем подсчитать сумму чисел от 1 до 1. Мы берем число 1, и ни с чем его не складываем:

sum(1) = 1

У нас получается рекурсивная функция sum :

const sum = (n) =>  if (n === 1)  return 1; > return n + sum(n - 1); >; sum(100) // 

def sum(n): if n == 1: return 1 return n + sum(n - 1) sum(100) # 

php function sum($n)  if ($n === 1)  return 1; > return $n + sum($n - 1); >; sum(100) // 

class App  public static int sum(int n)  if (n == 1)  return 1; > return n + sum(n - 1); > > App.sum(100); // 5050

Теперь рекурсивная функция остановится после ста вызовов и вычислит сумму чисел от 1 до 100.

Мы видим, что рекурсивные функции выглядят достаточно просто и делают то, что нам надо. Но пример выше не раскрыл весь потенциал рекурсии, а ведь она полезна для множества других задач. Изучим еще несколько примеров и посмотрим, где еще пригождаются знания о рекурсии.

Рекурсия вместо цикла

Один из распространенных алгоритмов в программировании — это бинарный поиск, который мы уже изучали в этом курсе. Мы уже рассмотрели его реализацию через циклы:

const binarySearch = (items, value) =>  let left = 0; let right = items.length - 1; while (left  right)  const middle = Math.floor((left + right) / 2); if (value == items[middle])  return middle; > if (value  items[middle])  right = middle - 1; > else  left = middle + 1; > > return -1; >; const items = [-3, -1, 1, 3, 5, 7, 9, 11]; console.log(binarySearch(items, 100)); // => -1 console.log(binarySearch(items, -1)); // => 1 console.log(binarySearch(items, 7)); // => 5

def binary_search(items, value): left = 0 right = len(items) - 1 while (left  right): middle = (left + right) // 2 if value == items[middle]: return middle if value  items[middle]: right = middle - 1 else: left = middle + 1 return -1 items = [-3, -1, 1, 3, 5, 7, 9, 11] print(binary_search(items, 100)) # => -1 print(binary_search(items, -1)) # => 1 print(binary_search(items, 7)) # => 5

php function binarySearch($items, $value)  $left = 0; $right = count($items) - 1; while ($left  $right)  $middle = round(($left + $right) / 2); if ($value === $items[$middle])  return $middle; > if ($value  $items[$middle])  $right = $middle - 1; > else  $left = $middle + 1; > > $return -1; > $items = [-3, -1, 1, 3, 5, 7, 9, 11]; print_r(binarySearch($items, 100)); // => -1 print_r(binarySearch($items, -1)); // => 1 print_r(binarySearch($items, 7)); // => 5

class App  public static int binarySearch(ListInteger> items, int value)  var left = 0; var right = items.size() - 1; while (left  right)  var middle = (left + right) / 2; if (value == items.get(middle))  return middle; > if (value  items.get(middle))  right = middle - 1; > else  left = middle + 1; > > return -1; > > ListInteger> items = List.of(-3, -1, 1, 3, 5, 7, 9, 11); App.binarySearch(items, 100); // -1 App.binarySearch(items, -1); // 1 App.binarySearch(items, 7); // 5

Тогда мы описывали алгоритм через циклы, поэтому объяснение было подробным и сложным. Алгоритм бинарного поиска можно описать намного проще, если опираться на знания о рекурсии:

1. Если массив пустой, то поиск завершается неудачно
2. Если массив не пустой, сравниваем наш элемент со средним элементом массива. Если они равны, поиск завершается удачно
3. Если средний элемент больше нужного, повторяем поиск в левой половине массива
4. Если средний элемент меньше нужного, повторяем поиск в правой половине массива

И это все: мы свели задачу поиска к самой себе. Сначала зона поиска — это весь массив, но на каждом шаге она сужается в два раза. Если нужного элемента в массиве не окажется, зона поиска сузится до пустого массива, и поиск завершится неудачно:

const binarySearch = (items, value, left, right) =>  if (left > right)  return -1; > const middle = Math.floor((left + right) / 2); if (value == items[middle])  return middle; > if (value  items[middle])  return binarySearch(items, value, left, middle - 1); > return binarySearch(items, value, middle + 1, right); >; const items = [-3, -1, 1, 3, 5, 7, 9, 11]; console.log(binarySearch(items, 100, 0, items.length - 1)); // => -1 console.log(binarySearch(items, -1, 0, items.length - 1)); // => 1 console.log(binarySearch(items, 7, 0, items.length - 1)); // => 5

def binary_search(items, value, left, right): if left > right: return -1 middle = (left + right) // 2 if value == items[middle]: return middle if value  items[middle]: return binary_search(items, value, left, middle - 1) return binary_search(items, value, middle + 1, right) items = [-3, -1, 1, 3, 5, 7, 9, 11] print(binary_search(items, 100, 0, len(items) - 1)) # => -1 print(binary_search(items, -1, 0, len(items) - 1)) # => 1 print(binary_search(items, 7, 0, len(items) - 1)) # => 5

php function binarySearch($items, $value, $left, $right)  if ($left > $right)  return -1; > $middle = round(($left + $right) / 2); if ($value === $items[$middle])  return $middle; > if ($value  $items[$middle])  return binarySearch($items, $value, $left, $middle - 1); > return binarySearch($items, $value, $middle + 1, $right); > $items = [-3, -1, 1, 3, 5, 7, 9, 11]; print_r(binarySearch(items, 100, 0, items.length - 1)); // => -1 print_r(binarySearch(items, -1, 0, items.length - 1)); // => 1 print_r(binarySearch(items, 7, 0, items.length - 1)); // => 5

class App  public static int binarySearch(ListInteger> items, int value, int left, int right)  if (left > right)  return -1; > var middle = (left + right) / 2; if (value == items.get(middle))  return middle; > if (value  items.get(middle))  return binarySearch(items, value, left, middle - 1); > return binarySearch(items, value, middle + 1, right); > > ListInteger> items = List.of(-3, -1, 1, 3, 5, 7, 9, 11); App.binarySearch(items, 100, 0, items.size() - 1); // -1 App.binarySearch(items, -1, 0, items.size() - 1); // 1 App.binarySearch(items, 7, 0, items.size() - 1); // 5

Как видно на примере выше, рекурсивный алгоритм очень похож на итерационный — то есть сделанный с помощью цикла. Но его гораздо проще объяснять не через циклы, а через рекурсию.

Продолжим изучать рекурсию на еще одном примере.

Рекурсивный алгоритм для Ханойской башни

Ханойская башня — это знаменитая древняя головоломка. Она состоит из трех стержней, на один из которых надеты кольца разного размера.

Надо перенести все кольца на другой стержень, при этом кольца можно переносить только по одному. Главное правило: никогда нельзя класть кольцо большего размера на кольцо меньшего.

Попробуем спроектировать алгоритм, который решит эту головоломку. Для начала формализуем задачу:

• Обозначим стержни числами 1, 2 и 3
• Определимся, что нам нужен универсальный алгоритм, который решает головоломку при любой высоте башен
• Назовем функцию hanoi и зададим ей три параметра:

1. Количество колец (высота башни, которую мы хотим перенести)
2. Номер стержня, откуда мы будем переносить башню
3. Номер стержня, куда мы будем переносить башню

Таким образом, вызов hanoi(10, 1, 3) будет означать: «Перенести башню из десяти колец с первого стержня на третий».

Функция должна печатать последовательность переносов: взять верхнее кольцо со стержня №1 и перенести его на стержень №2. Мы не можем взять второе сверху кольцо или пятое сверху — только самое верхнее. Поэтому нам достаточно просто выводить номера обоих стержней: откуда снимать кольцо и куда переносить.

Если оставить все как есть, мы столкнемся с такой проблемой: можно перенести первые два кольца, но третье кольцо переместить не получится, потому что оно больше обоих колец на соседних стержнях. Как быть?

Здесь на помощь приходит рекурсия. Попробуем упростить задачу и свести ее к самой себе:

• Предположим, что мы уже умеем переносить башню из четырех колец
• Дальше нам надо перенести башню из пяти с первого стержня на второй
• Воспользуемся третьим стержнем и перенесем на него четыре верхних кольца
• Теперь можем взять самое большое кольцо с первого стержня и перенести его на пустой второй
• Осталось снять башню из четырех колец со вспомогательного третьего стержня и перенести ее на второй стержень, на котором уже лежит большое пятое кольцо второго стержня — это мы уже умеем

Можно ли будет класть какие-то кольца поверх самого большого пятого? Да, потому что правила запрещают только класть большие кольца на меньше, а наоборот — нет. Оказывается, что этих рассуждений достаточно, чтобы написать рекурсивную функцию.

Только мы знаем, что рекурсия должна где-то останавливаться. В нашем случае минимальная задача, которую мы можем решить — перенос башни из одного кольца. Она решается тривиально: одно кольцо мы можем перенести безо всяких условий, поэтому нам достаточно просто вывести номера стержней «откуда» и «куда»:

const hanoi = (height, from, to) =>  if (height === 1)  console.log("с %d на %d", from, to); return; > const temporary = 6 - from - to; hanoi(height - 1, from, temporary); console.log("с %d на %d", from, to); hanoi(height - 1, temporary, to); >; hanoi(4, 1, 2); // => с 1 на 3 // => с 1 на 2 // => с 3 на 2 // => с 1 на 3 // => с 2 на 1 // => с 2 на 3 // => с 1 на 3 // => с 1 на 2 // => с 3 на 2 // => с 3 на 1 // => с 2 на 1 // => с 3 на 2 // => с 1 на 3 // => с 1 на 2 // => с 3 на 2

def hanoi(height, start, to): if height == 1: print(f'с start> на to>') return temporary = 6 - start - to hanoi(height - 1, start, temporary) print(f'с start> на to>') hanoi(height - 1, temporary, to) hanoi(4, 1, 2) # => с 1 на 3 # => с 1 на 2 # => с 3 на 2 # => с 1 на 3 # => с 2 на 1 # => с 2 на 3 # => с 1 на 3 # => с 1 на 2 # => с 3 на 2 # => с 3 на 1 # => с 2 на 1 # => с 3 на 2 # => с 1 на 3 # => с 1 на 2 # => с 3 на 2

php function hanoi($height, $from, $to)  if ($height === 1)  print_r("с $from> на $to>"); return; > $temporary = 6 - $from - $to; hanoi($height - 1, $from, $temporary); print_r("с $from> на $to>"); hanoi($height - 1, $temporary, $to); > hanoi(4, 1, 2); // => с 1 на 3 // => с 1 на 2 // => с 3 на 2 // => с 1 на 3 // => с 2 на 1 // => с 2 на 3 // => с 1 на 3 // => с 1 на 2 // => с 3 на 2 // => с 3 на 1 // => с 2 на 1 // => с 3 на 2 // => с 1 на 3 // => с 1 на 2 // => с 3 на 2

class App  public static void hanoi(int height, int from, int to)  if (height == 1)  System.out.println(String.format("с %d на %d", from, to)); return; > var temporary = 6 - from - to; hanoi(height - 1, from, temporary); System.out.println(String.format("с %d на %d", from, to)); hanoi(height - 1, temporary, to); > > App.hanoi(4, 1, 2); // => с 1 на 3 // => с 1 на 2 // => с 3 на 2 // => с 1 на 3 // => с 2 на 1 // => с 2 на 3 // => с 1 на 3 // => с 1 на 2 // => с 3 на 2 // => с 3 на 1 // => с 2 на 1 // => с 3 на 2 // => с 1 на 3 // => с 1 на 2 // => с 3 на 2

Удивительно, что этот алгоритм казался сложным на словах, но в коде получился таким простым. Здесь мы применили один трюк, который помогает упростить код. Разберем его подробнее.

Во время работы алгоритма стержни постоянно меняются ролями. Например, если мы хотим перенести башню с первого стержня на третий, то второй стержень выступает как вспомогательный — туда мы перенесем все кольца, кроме нижнего. А если мы переносим маленькую башню с первого стержня на второй, то роль вспомогательного переходит третьему стержню.

Чтобы определить номер вспомогательного стержня, надо написать сложное условие:

if (from === 1 && to === 2 || from === 2 && to === 1)  temporary = 3; > else if (from === 2 && to === 3 || from === 3 && to === 2)  temporary = 1; > else if (from === 1 && to === 3 || from === 3 && to === 1)  temporary = 2; >

if (start == 1 and to == 2) or (start == 2 and to == 1): temporary = 3 elif (start == 2 and to == 3) or (start == 3 and to == 2): temporary = 1 elif (start == 1 and to == 3) or (start == 3 and to == 1): temporary = 2

php if ($from === 1 && $to === 2 || $from === 2 && $to === 1)  $temporary = 3; > else if ($from === 2 && $to === 3 || $from === 3 && $to === 2)  $temporary = 1; > else if ($from === 1 && $to === 3 || $from === 3 && $to === 1)  $temporary = 2; >

if (from == 1 && to == 2 || from == 2 && to == 1)  temporary = 3; > else if (from == 2 && to == 3 || from == 3 && to == 2)  temporary = 1; > else if (from == 1 && to == 3 || from == 3 && to == 1)  temporary = 2; >

Несмотря на то, что логика этого кода понятна, само условие выглядит громоздким. Разберем по шагам, как оно работает. В коде используют три константы:

• from — номер стержня, с которого мы перемещаем кольца
• to — номер стержня, на который мы хотим переместить наши кольца
• temporary — номер стержня, который мы используем для временного хранения первых n-1 дисков

Еще в вызове указано количество колец — высота башни, которую мы хотим перенести. Таким образом, вызов hanoi(n, 1, 3) будет означать: «Перенести башню из n колец с первого стержня на третий».

Обратите внимание, что сумма from , to и temporary всегда равна 6. Можно взять число 6 и вычесть из него номера стержней from и to , и тогда мы узнаем номер вспомогательного стержня:

const temporary = 6 - from - to;

temporary = 6 - start - to