Есть такая популярная поговорка; «Чтобы понять рекурсию [метод программирования], нужно сначала понять рекурсию [общее слово]». Давайте разберемся с этим, сначала разобравшись со словом «рекурсия».

Согласно Википедии, Рекурсия (прилагательное: рекурсивный) происходит, когда вещь определяется в терминах самого себя или своего типа.

Часть определения [метод]

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

Затем мы говорим, что определили метод сложения двух (2) чисел.

Рекурсивная часть

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

Два случая

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

Здесь вы можете спросить; не попадем ли мы в бесконечный цикл (он же бесконечный цикл)? Правда в том, что будем, если бы не базовый вариант.

Чтобы понять рекурсию, нужно сначала понять рекурсию.

Когда можно использовать рекурсию?

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

Примеры проблем, которые мы можем решить с помощью рекурсии:

Мы собираемся решить все три проблемы в этой статье с помощью рекурсии.

Правильный подход к рекурсивным решениям

Сначала мы должны сделать вывод;

  • легкая часть (и),
  • базовый (-ые) вариант (-и) и
  • рекурсивный случай (ы)

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

Следующий вопрос: как базовый случай и рекурсивный случай соотносятся друг с другом? Так мы собираемся в конце перестроить решения в одно целое.

Представьте, что вы первый человек в длинной очереди в Starbucks, кассир хочет подсчитать всех в очереди. Дежурный не должен покидать свое место, и никто не желает покидать свое место.

Мы можем решить эту проблему с помощью рекурсии, но что сначала будет проще?

Предположим на мгновение, что в очереди только один человек; это ты. Когда вы оглянетесь и больше никого не увидите, ваш ответ будет 1 (вы + никто другой). Это наш базовый вариант. Легкая часть - это когда каждый знает, что он всего лишь один человек.

Итак, находясь впереди; Я спрошу человека позади меня: «Сколько человек в очереди?» Это наш рекурсивный случай. Человек позади меня применяет ту же технику, пока вопрос не задают последнему человеку.

Наконец, какова связь между легкой частью и рекурсивным случаем? Я знаю, что количество людей в очереди - 1 (я) + x (число, которое вернется назад человек позади меня).

Так что отношение + (плюс). Наконец, я добавлю полученное мной число к 1 и верну его дежурному.

Давайте применим эту технику к перечисленным выше проблемам.

Легкая часть; базовый случай и рекурсивный случай.

Факториальная проблема.

Факториал целого числа - это произведение всех положительных ненулевых целых чисел, меньших или равных этому числу.

Для целого числа n напишите метод, возвращающий факториал числа n.

Пример: факториал (5) = 5 * 4 * 3 * 2 * 1 = 120

Рекурсивное факториальное решение

Какой базовый вариант?

Из определения факториала он говорит: «все положительные ненулевые целые числа, меньшие или равные n». Какое наименьшее целое число, отличное от нуля? Верно !, 1.

Что самое легкое?

В примере заметьте, что 5! = 5 * 4 !. Итак, если мы можем отложить 5 (n) в сторону и попросить факториал 4 (n - 1). Это довольно легко сделать, поэтому мы называем это легкой частью.

Как только вы выясните легкую часть, выясняется и рекурсивная часть. В этом случае вы можете видеть, что 4! На вид и ощущения на 5!

Наконец, какова связь между простой и рекурсивной частью? Вы угадали, умножение.

Теперь напишем код.

Проблема палиндрома

Палиндром - это слово, число, фраза или другая последовательность символов, которая читается так же, как вперед и назад, например «мадам» или «гоночная машина».

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

Решение для рекурсивного палиндрома

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

Так, например, дана строка «мадам»; мы можем удалить первый и последний символы, проверить, совпадают ли они; если да, продолжаем проверку оставшейся части (в данном случае «ada»). Мы делаем это до тех пор, пока у нас не будет одного только одного персонажа или ни одного персонажа. Но если в какой-то момент первый и последний символы не совпадают, то это слово не является палиндромом.

Таким образом, наш базовый случай - когда остается 0 или 1 символ.

Теперь напишем код.

Проблема Ханойской башни

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

Задача головоломки - переместить всю стопку на другой стержень, соблюдая следующие простые правила:

  • Одновременно можно перемещать только один диск.
  • Каждый ход состоит в том, чтобы взять верхний диск из одной стопки и положить его поверх другой стопки или на пустой стержень.
  • Диск большего размера нельзя ставить поверх диска меньшего размера.

Учитывая количество дисков и три (3) полюса (исходный, вспомогательный и целевой), напишите метод для печати всех необходимых ходов для решения головоломки за минимальное количество ходов. Подсказка - для n дисков минимальное количество ходов для решения головоломки будет 2 ^ n - 1.

Рекурсивное решение Ханойской башни

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

Предположим, у нас всего 2 диска. Последовательность игры будет показана ниже:

Сначала перемещаем верхний диск с полюса A (источник) на полюс B (вспомогательный); Рисунок 1). Это оставляет полюс A с 1 диском, который мы можем легко переместить из A (источник) в C (пункт назначения). Затем возвращаемся и перемещаем диск с полюса B (вспомогательный) на полюс C (пункт назначения).

Также подумайте, когда мы имеем дело с 3 дисками, как показано ниже:

Внимательно следите за рисунком (3). Выглядит знакомо? Опять же, если мы сможем переместить n - 1 диск к вспомогательному полюсу, мы сможем проделать простую часть перемещения оставшегося диска к месту назначения. Здесь снова тот же образец; базовый случай - когда каждый диск перемещается на полюс назначения.

Итак, давайте напишем код.

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

Может показаться, что мы обманули, но помните, что каждое «массовое перемещение» n-1 - это уменьшенная версия проблемы (рекурсивная часть).

Заключение

Легкая часть | Базовый случай | Рекурсивный случай

Столкнувшись с проблемой рекурсии, всегда отвечайте на эти 3 вопроса, прежде чем писать какой-либо отдельный код.

  • Что самое легкое?
  • Какой базовый вариант?
  • Что такое рекурсивный случай?

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

Я оставлю вам это видео. Я рекомендую вам закончить все 3 класса на рекурсии.