Рекурсия

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

И мы видели циклы for и while, которые выполняют повторные вычисления.

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

Ранее мы определили метод square, который, принимая целое число, возвращает квадрат числа.

Теперь мы хотели бы определить метод, который возводит в степень.

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

Поэтому, если y равно 2, мы вычисляем квадрат числа, как и раньше.

Вы видите, что в этом методе мы имеем два аргумента, целые числа x и y.

Давайте сначала попытаемся определить этот метод.

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

Если y равно 0, то результат x равен степени 0, т. е. 1.

Если y равно 1, результат будет сразу x.

Если y равно 2, результатом является квадрат x.

Мы можем вызвать метод square, который мы определили ранее.

Если y равно 3, мы имеем x в кубе, предполагая, что у нас есть метод, называемый cube, определенный заранее.

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

Теперь мы можем заменить вызовы методов square, cube, и т. д. следующим кодом.

Таким образом, мы будем иметь x умножить на x, x умножить на x умножить на x и т. д.

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

Но мы все же кое-чему научились.

Чтобы вычислить x в степени y, мы должны умножить x y раз.

Но мы должны учитывать, является ли эта процедура применима для всех целых чисел y?

Нет.

Только для y больше или равно 0.

Для отрицательного y нам понадобится другой способ умножения.

Если у нас есть повторное умножение, мы можем использовать цикл.

Вот пример того, как мы можем это сделать.

Мы инициализируем целочисленную переменную z в 1, а затем вводим цикл.

Счетчик i инициализируется 1 и увеличивается на 1 при каждом прогоне цикла.

Этот счетчик отслеживает, сколько х мы умножаем и накапливаем с помощью z.

И мы должны выполнять тело цикла ровно y раз, пока i не станет равен y.

Затем мы выходим и возвращаем накопленное значение в z.

Давайте проанализируем это снова.

x в степени y равно 1, если y равно 0.

А если y строго больше 0, то x в степени y равно x умножить на x в степени y минус 1.

Это то, что в математике называется рекуррентным уравнением.

И мы можем написать это на Java в виде вызова функции power.

Если y равно 0, возвращаем 1.

Иначе, возвращаем x умножить на вызов этой же функции с x и y минус 1.

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

Оба эти способа эквивалентны.

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

Рекурсию можно сравнить с матрешкой.

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

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

Начнем с x в 3 степени.

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

Таким образом, мы пишем весь код метода, подставляя вместо y 3.

И в этой последовательности выражений мы переходим от вызова метода с параметрами (x, 3) к вызову метода с параметрами (x, 2).

Пишем весь код метода, подставляя вместо y 2.

И в этой последовательности выражений, мы перешли от вызова метода с параметрами (x, 2) к вызову метода с параметрами (x, 1).

И переходим к вызову метода с параметрами (x, 0).

x в степени 0 равно 1.

Теперь нам нужно собрать все вместе.

power (x, 3) равно x умножить на power (x, 2).

А power (x, 2) равно x умножить на power (x, 1).

А power (x, 1) равна x умножить на power (x, 0), что равно 1.

Таким образом, мы получаем x умножить на x умножить на x умножить на 1.

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

Это изображение коробки с медсестрой, держащей меньшую коробку с тем же изображением.

Так что в теории, могут быть бесконечные медсестры и бесконечные коробки.

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

Таким образом, существует конечное число коробок.

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

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

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

И давайте вызовем power (x, -2) для некоторого заданного x.

Для этого мы можем заменить вызов метода кодом.

В результате мы перейдем к вызову метода power (x, -3).

В методе power (x, -3) мы перейдем к вызову метода power (x, -4).

И так далее. Без конца.

Мы получим бесконечные вычисления в теории.

На практике мы получим переполнение в какой-то момент и ошибку.

Что же мы сделали не так?

В этом случае мы не соблюдали комментарий, что y должно быть больше или равно 0.

Поэтому мы должны учитывать две важные вещи.

Во-первых, рекурсия хороша, но мы можем перейти к бесконечным вычислениям.

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

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

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

Существует два способа чтения и понимания рекурсивных методов.

Один из них – это тот способ, который мы видели.

Другой, математический или нотационный способ, которые мы рассмотрим.

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

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

В общем случае факториал натурального числа n вычисляется умножением всех натуральных чисел, начиная с 1 до n.

Чтобы решить эту задачу, мы будем использовать следующую стратегию.

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

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

Если бы у нас был факториал n минус 1, мы просто бы умножили это число на n, чтобы получить факториал n.

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

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

Так что это базовый случай.

Мы просто говорим, что факториал 0 равен 1.

Таким образом, факториал n равен 1, если n равно 0, и факториал n равен n умножить на факториал n минус 1, если n больше 0.

Теперь у нас есть основа для записи рекурсивного метода.

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

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

Базовый случай получается из пограничного случая.

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

Инкапсуляция. Объекты и классы

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

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

Запомнить значения можно с помощью переменных.

И затем мы можем вычислять новые значения с помощью методов.

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

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

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

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

И набор методов будет определять поведение калькулятора.

Наша модель будет меняться от одного состояния в другое со временем.

При этом состояние будет определяться значениями переменных.

А методы будут отвечать за изменение состояния.

На самом деле, определение переменных и методов – это общий способ моделирования объектов.

Эти объекты могут соответствовать физическим объектам, например, калькулятору.

Или эти объекты могут быть концептуальными, когда ваш код должен моделировать что-то новое.

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

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

Состоянием этого объекта может быть местоположение, цвет, включены ли фары или нет.

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

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

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

Эта концепция инкапсуляции является одной из ключевых концепций в так называемой объектно-ориентированной парадигме программирования.

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

И поведение, то, что может делать наш объект, представлено методами.

Эти два компонента: состояние и поведение, не разбросаны по программе, а собраны и инкапсулированы в объекты.

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

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

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

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

Все эти объекты принадлежат классу автомобилей Car, который имеет ряд атрибутов или переменных, или полей и ряд методов.

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

Здесь вы можете увидеть определение класса Car.

Вы можете увидеть зарезервированное ключевое слово class.

Затем имя, которое мы хотим дать классу.

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

Затем мы указываем переменные с соответствующим типом.

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

Но как только мы определили класс, как сконструировать объект для этого класса?

Для этого у нас есть конструкторы.

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

И они имеют имя класса.

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

Используя конструкторы, мы можем создавать разные объекты класса.

Заметьте, что может быть не один, а несколько конструкторов.

Эти конструкторы отличаются списком параметров.

Здесь вы можете увидеть несколько возможных конструкторов для класса Car.

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

Здесь мы видим несколько вызовов конструкторов, определенных ранее.

Посмотрите на объявление.

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

Сначала мы указываем Car, чтобы указать, что объект имеет тип или класс Car.

Затем знак равенства, зарезервированное ключевое слово new и вызов конструктора.

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

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

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

Классы и типы

Классы – это шаблоны, из которых мы строим объекты.

И все объекты имеют одинаковую структуру, определенную классом.

Давайте сравним класс, который мы определили, со встроенным Java типом.

Так, например, с одной стороны, у нас есть класс «Car», который мы определили с такими методами, как «двигаться вперед» или «включать фары» и поля, такие как «свет» и «местоположение».

И, с другой стороны, у нас есть целые числа типа «int».

И для этих целых чисел у нас есть ряд определенных операций или методов, таких как «сложение» или «умножение».

Давайте сосредоточимся на методах.

В обоих случаях методы связаны с объектами в классе или значениями данного типа.

Таким образом, классы похожи на типы, и объекты похожи на сложные значения.

Фактически, вы можете рассматривать классы как типы.

Типы, которые не являются встроенными Java типами, а типы, которые вы определили для решения какой-либо конкретной задачи.

При определении методов и конструкторов классы принимают роль типов.

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

И String- это класс, а «int» – это примитивный тип данных.

Здесь мы видим объявление переменной целого числа и переменной строки.

Иногда мы говорим о «ссылках», в случае объектов.

В нижней части мы видим объявление метода со String и «int» в качестве параметров.

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

На самом деле для каждого примитивного типа существует соответствующий класс, называемый «классом-оболочкой».

Например, у нас есть тип «int» и класс «Integer».

И этот класс Integer является классом-оболочкой.

Объект класса «Integer» содержит поле с числом «int» и метод, который возвращает число «int», сохраненное в этом объекте.

Кроме того, там есть другие поля и методы, которые используются для разных целей.

Как вы можете видеть, для преобразования числа «int» в объект «Integer», мы можем использовать конструктор «Integer».

И для преобразования объекта Integer в значение «int», мы используем метод «intValue» класса «Integer».

Представление просто «int» в компьютере намного эффективнее, чем соответствующего объекта, так как существует много вещей, которые нужно хранить в объекте.

Класс – это не просто тип.

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

Это можно понимать, как составное значение – значение с несколькими компонентами – например, тремя целыми числами.

Поэтому, классы – это хороший способ собрать несколько значений вместе в полях объекта.

И эти компоненты могут быть нескольких типов или классов.

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

Представьте, что вы определили класс «Двигатель» с набором полей, которые определяют состояние двигателя и набором методов, которые определяют то, что вы можете делать с двигателем.

У нас может быть объект класса «Двигатель» как атрибут или поле класса «Автомобиль».

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

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

Но концепция объекта класса еще богаче.

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