скачать книгу бесплатно
Так работает рекурсия – сначала мы спускаемся как по лестнице вниз, а затем поднимаемся опять наверх.
Это изображение коробки с медсестрой, держащей меньшую коробку с тем же изображением.
Так что в теории, могут быть бесконечные медсестры и бесконечные коробки.
Но на практике нет бесконечных коробок, потому что изображение имеет некоторое разрешение, и мы не можем опуститься ниже 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 и вызов конструктора.
Таким образом, в итоге, чтобы определить объект, мы должны сначала определить класс, предоставляя набор полей и набор методов.
После определения класса мы можем создать объект как экземпляр класса, используя конструктор, предоставляемый классом.
Мы можем создать много объектов одного класса, каждый из которых будет со своим собственным состоянием.
Классы и типы
Классы – это шаблоны, из которых мы строим объекты.
