T.M. SoftStudio

feci quod potui, faciant meliora potentes

Купить полную версию курса "Введение в вычисления с Java" (русскоязычная версия, лекции, тесты, лабораторные работы)

Введение в вычисления с Java. Рекурсия

Неделя 9

Лекция 35

Проблема рукопожатий

Я буду обсуждать на этой неделе новую тему, которая называется рекурсия.

Когда мы решаем проблемы, мы часто пытаемся разложить проблему на подзадачи.

В объектно-ориентированном программировании, мы стараемся реализовать эти подзадачи, как методы в классах.

Такой подход часто называют «разделяй и властвуй».

Такого рода стратегии решения проблем довольно широко используются в решении повседневных жизненных проблем.

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

Спрашивая помощь у других, вы можете сделать решение задачи легче.

В программировании, подход вызова другой функции или метода следует подобной идеи.

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

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

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

Метод, вызывающий себя, является основной идеей рекурсии.

Чтобы проиллюстрировать идею рекурсии, давайте взглянем на пример.

Это называется проблемой рукопожатия.

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

Скажем, есть какое-то количество людей в комнате, и предполагается, что их число n.

Если каждый человек пожмет руку один раз и только один раз каждому другому человеку в комнате, вопрос в том, какое будет общее число рукопожатий, которые будут сделаны, когда есть n человек?

Давайте использовать обозначение h(n) для представления общего количества рукопожатий для любого числа n.

Подумайте об этом, как бы вы решите эту проблему.

Когда есть только один человек, там не будет рукопожатия.

В простейшем случае, когда у вас есть только два человека в комнате, то есть, число рукопожатий h(n) с n, равным 2.

Понятно, что там может быть только одно рукопожатие, когда есть только два человека, таким образом, h(2) равно 1.

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

Так что h(3) будет h(2) плюс 2.

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

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

Таким образом, общее число рукопожатий для 4-х человек, или h(4) будет h(3) плюс 3, новые рукопожатия для четвертого человека.

Надеюсь, вы уже видите шаблон здесь.

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

Так что, общий вид решения является h(n) = h(n-1) + n – 1.

Функция факториала

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

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

В таких задачах, мы можем сформулировать решение задачи, просто следуя путем, как задача определена.

Давайте рассмотрим другой пример, который мы видели раньше.

Мы ввели функцию факториала, когда мы обсуждали циклы.

Напомним, что факториал целого числа n представляет собой последовательное умножение чисел от n до 1.

Например, при вычислении 6!, результат будет умножение 6, 5, 4, 3, 2, 1, который даст 720.

Также легко видеть, что 6! можно переписать в виде 6 умножить на 5!

где 5! равен оставшейся части умножений, следующих за 6.

Так что мы выражаем 6! как 5!, который является упрощенной задачей, чем 6!.

Таким образом, в целом, мы можем выразить функцию факториала как n! = n * (n-1)!.

Здесь n! может быть получен путем вычисления n-1 факториал.

Вы решили проблему полностью? Ну, почти.

У нас еще есть вычисление n-1!. Как мы вычисляем n-1!?

Мы можем получить n-1!, вычисляя n-2!.

Но это, кажется никогда не заканчивающейся последовательностью, если нет какого-то завершающего состояния.

В случае факториала, мы знаем, что он определяется только для неотрицательных чисел.

И мы также знаем, что 1! или 0! дает значение 1.

Давайте игнорировать 0! в нашей дискуссии, и n-1! продолжает уменьшаться до тех пор, пока n-1 не станет равен 1, и мы можем остановить повторный вызов функции факториала.

Это часто называют базовым состоянием.

Чтобы написать это в явном виде, когда n равно 1, мы должны получить n! равен 1, в противном случае, n! равно n * n-1!.

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

В Java можно определить рекурсивную функцию.

Обратите внимание, что не все языки программирования позволяют рекурсию.

Когда у нас есть функция или метод, который вызывает себя, мы обращаемся к такой функции, как рекурсивной функции или методу.

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

В 70-х годах, термин фрактал был введен Mendelbrot для визуализации самоподобных шаблонов, используя компьютерное моделирование.

Мы обсудим некоторые из них позже в этой лекции.

Давайте теперь постараемся реализовать вычисление n! рекурсивным образом.

Здесь мы объявляем метод с именем fact, который возвращает целое значение.

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

Метод возьмет целый параметр n, для которого мы вычислим факториал.

Остальная часть определения будет просто следовать рекурсивному определению, как мы только что описали.

То есть, n! равен 1, если n меньше или равно 1, при условии, что n является неотрицательным.

В противном случае, то есть, когда n больше, чем 1, n! будет n * n-1!.

Обратите внимание, что мы вызываем метод внутри определения метода, и это то, что мы раньше не видели.

Рекурсивный вызов методов

Давайте более внимательно посмотрим на то, как рекурсивный вызов метода фактически работает в Java.

Возьмем простой случай, когда n равно 3.

Это функция факториала, что мы только что определили.

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

То есть, будет вычисляться fact(3), который равен 3 умножить на fact (n-1), с n равным 3, то есть, метод будет вызываться с параметром 2 или 3-1.

В этом месте мы не знаем результат для fact(2) пока.

Поэтому, прежде чем мы можем перемножить fact(2) на 3, мы должны сначала выяснить значение fact(2).

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

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

Каждый раз, когда n упоминается внутри метода, локальная копия n используется, которая замещает предыдущую копию параметра, которая несет такое ​​же имя n.

Так что n в fact(2) будет иметь значение 2 и условие n меньше чем или равно 1 снова дает ложь.

Так что else часть будет выполнена.

То есть, два умножить на fact(n-1) или 1 при n, равным 2.

В этот момент, значение для fact(1) до сих пор не определено.

Далее, рекурсивный вызов метода с 1 в качестве параметра производится.

В этом случае, с n, равным 1, if часть условия становится верным, и 1 будет возвращена в качестве результата для fact(1).

После того, как значение для fact(1) определяется, мы можем вернуться к вычислению fact(2) путем умножения 2 на fact(1), который только что получили как возвращенное значение 1.

Так fact(2) может быть вычислен путем умножения 2 на 1 и получим 2 как возвращенный результат для fact(2).

Используя значение для fact(2), мы можем снова вернуться к вычислению fact(3) путем умножения 3 на fact(2) или 2 и получить значение 6.

Таким образом, мы имеем возвращаемое значение для fact(3), который является конечным результатом, что мы хотим получить для 3!.

Мы видим на примере, что метод вызывается несколько раз.

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

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

Помните, что, когда мы обсуждали структуру цикла, используя факториал как пример, мы реализовали факториал с использованием различных видов циклов, а именно, while, do-while и for цикла.

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

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

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

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

На левой стороне, это реализация с использованием while цикла, и метод на правой стороне является рекурсивным решением, которое мы только что видели.

Вы можете посмотреть на инициализацию t как базовое решение, и в то время как цикл будет соответствовать рекурсивному вызову метода, если сравнить итерационное решение с рекурсивной реализацией.

Давайте вернемся к проблеме рукопожатия.

Напомним, что общее количество рукопожатий для лиц n является h(n) = h(n-1) + (n-1).

То есть, h(n) вычисляется с помощью h(n-1).

Поскольку h определен в терминах h меньшего n, это может быть реализовано с использованием рекурсивного метода.

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

Предполагая n положительным, здесь мы также заботимся о том случае, когда n равно 1 и будет n-1 или ноль рукопожатий.

else часть рекурсивного вызова заботится о случаях для n больше, чем 2.

Альтернативно, это также может быть реализовано с помощью цикла.

На самом деле, есть даже близкая форма решения для суммы целых чисел от 1 до n-1 = n(n-1) / 2.

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

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

Так вот, мы реализовали программу рукопожатий, как описано выше.

Когда мы компилируем программу, нет никакой ошибки.

Скажем, если мы попытаемся запустить программу, вводя различные значения n.

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

Давайте снова запустим программу, введя 4 в качестве значения n, и тогда вы обнаружите, что 6 это возвращаемый результат.

Давайте сделаем еще один запуск, введя 5.

Так у вас есть 5 человек в комнате.

И вы можете видеть, что возвращаемый результат 10 здесь равен 6 плюс 5 минус 1, что есть 4.

Так у вас есть 6 плюс 4 равно 10.

Числа Фибоначчи

При работе с циклами итерации, нужно быть очень осторожным, чтобы не попасть в бесконечный цикл.

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

Вот несколько примеров, которые могут вовлечь вас в неприятности.

Взгляните на этот первый пример и подумайте о том, где может быть проблема.

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

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

Что об этом втором примере?

Это выглядит очень похоже на то, что мы видели в вычислении n факториала.

Проблема в том, что n+ 1 используется здесь по ошибке.

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

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

Последовательность Фибоначчи впервые появилась в 13 веке.

Когда рост популяции кроликов наблюдался, было установлено, что рост следует образцу, как указано в этих допущениях:

- Каждая пара зрелых кроликов, один мужчина и одна женщина, производит новую пару крольчат каждый месяц;

- Каждая новая пара становится плодородной через один месяц после рождения и женщина будет производить еще одну пару кроликов через месяц;

- И далее, что ни один из кроликов не умрет в этом году.

Вопрос в том, сколько пар кроликов будет через год.

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

В ходе 2-го месяца, из двух пар кроликов, зрелая пара будет продолжать производить потомство в 2-м месяце, в то время как пара новорожденных должна просто повзрослеть, но не иметь детей еще.

Так что будет 3 пары кроликов в конце 2-го месяца.

В конце 3-го месяца, две пары взрослых кроликов каждая родит пару новорожденных, то есть будет 2 дополнительные пары или 5 пар вместе.

И пара, родившаяся во 2-й месяц, теперь стала плодородной.

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

Числа Фибоначчи, как полагают, моделируют природу определенным образом, и есть другие природные феномены, которые напоминают последовательность Фибоначчи, например, наблюдение Кеплера листьев и цветов в 17 веке.

Вот некоторые из первых чисел Фибоначчи.

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

Например, 2 получается путем сложения 1 и 1, 3 получают путем сложения 1 и 2, 5 получают путем сложения 2 и 3, 8, добавив 3 к 5, и так далее.

В общем, энное число Фибоначчи можно определить рекурсивно, путем суммирования (n -1) и (n - 2) чисел Фибоначчи.

И базовый случай определен для n = 0 и n = 1 со значениями, равными 0 и 1 соответственно.

Вот реализация Java для числа Фибоначчи.

Фактический метод вычисления числа Фибоначчи является методом, который принимает один параметр n и возвращает целое число, представляющее число Фибоначчи.

Метод main ниже просто, чтобы позволить ввод различных значений n для проверки метода.

Обратите внимание, что метод объявлен статическим, так что нам не нужно создавать объект, прежде чем использовать этот метод.

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

График здесь показывает последовательность шагов в рекурсивных вызовах метода.

Хотя FIB(4) будет вызывать как FIB(3) так и FIB(2), так как каждый из них должен быть выполнен последовательно, FIB (3) должен быть вычислен в первую очередь.

FIB(2) будет затем вызвать FIB(1) и FIB(0), и так как оба представляют собой базовые случаи, целочисленные результаты будут возвращены.

Затем вычисление возвратится к FIB(3), который требует вычисления FIB(1), и так как это снова базовый вариант, значение для FIB(3) может быть определено.

Затем будет попытка завершить расчет для FIB(4) путем вычисления FIB(2).

Процесс будет продолжаться до тех пор, пока значения для FIB(3) и FIB(2) не будут получены для определения конечного значения для FIB(4).

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

Например, FIB(1) вновь вычисляется 3 раза, FIB(2) повторно вычисляется 2 раза и так далее.

Подобно проблемы рукопожатия, есть также другая форма решения для вычисления чисел Фибоначчи.

Хотя это намного сложнее.

Мы можем, конечно, реализовать ряд Фибоначчи, используя итеративный подход, но реализация не будет такая простая, как рекурсивное решение.

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

Так вот реализация ряда Фибоначчи, что мы только что видели.

Давайте скомпилируем программу.

Там нет ошибок.

При попытке запустить программу, используя небольшое значение n = 4, вы сможете обнаружить, что четвертый номер Фибоначчи это 3.

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

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

Если вы посмотрите на результаты, можно увидеть, что число Фибоначчи для 42 это сумма числа Фибоначчи для 40, что составляет около 100 млн., и число Фибоначчи для 41, что будет примерно 165 млн.

Если сложить их, вы получите около 267 млн​​.

Когда вы захотите вычислить число Фибоначчи для n, равным 45, вы найдете, что это займет много времени, прежде чем результат может быть возвращен.