Рекурсия

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

Рассмотрим пример — вычисление факториала. Для того чтобы вычислить n!, достаточно знать и перемножить между собой (n-1)! и n.

Создадим метод, реализующий описанный способ.

static int fact (int n) {   if (n==1) {     return 1;   } else if (n==2) {     return 2;   } else {     return fact(n-1) * n;   } }

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

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

Напомним, как выглядят первые элементы этого ряда: 1 1 2 3 5 8 13 …

static int fib (int n) {   if (n==1 || n == 2) {     return 1;   }   return fib (n-2) + fib (n-1); }

Обратите внимание, что в этом методе второй return не помещён в блок else для первого условного оператора. Это допустимо, ведь если выполнится условие и сработает первый return, то произойдёт выход из метода, до второго return исполнение программы дойдёт только в случае невыполнения условия.

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

Задачи

1. Выясните экспериментальном путём, начиная с какого элемента последовательности Фибоначчи, вычисление с использованием рекурсии становится неприемлемым (занимает более минуты по времени).

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

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

Стек вызовов

В общем случае в текущий момент времени может исполняться только один единственный метод из всей программы. Это значит, что, если метод а устроен таким образом, что в своём теле он вызывает метод b, а сам а вызывается в main, то при запуске программы управление сначала будет передано методу main, затем методу а, затем методу b. Метод b вернёт результат и управление в а, а вернет результат управления в main, и только потом будут выполняться основные команды, указанные в методеmain на остальных строках после вызова a.

Вся иерархия (кто кого вызывал) хранится в специальной области памяти, называемой стеком вызовов. Элементы в этот фрагмент памяти добавляются по следующему принципу: последний добавленный элемент должен быть извлечён первым. Когда работает метод b, получается, что под ним в стеке оказываются метод a и метод main.

В связи с этим в процессе рекурсии существует опасность переполнения стека вызовов.

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

Создание класса: свойства и методы

Рассмотрим пример создания простейшего класса. Давайте с его помощью смоделируем окружности на координатной плоскости.

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

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

// описываем отдельный новый класс class Circle {     // свойства класса     public double x; // абсцисса центра     public double y; // ордината центра     public double r; // радиус     // методы класса     // выводит на экран параметры окружности     public void printCircle() {         System.out.println("Окружность с центром ("+x+";"+y+") и радиусом "+r);     }         // перемещает центр, движение окружности     public void moveCircle(double a, double b) {         x = x + a;         y = y + b;     }     // масштабируем, выполняем преобразование подобия с коэффициентом k     public void zoomCircle(double k) {         r = r * k;     }     } // описываем основной класс, содержащий метод main public class Main {     public static void main(String[] args) {         // Создаём объект (окружность класса Circle), у неё будет нулевой         // радиус и центр в (0.0;0.0), поскольку все свойства получат         // значения по умолчанию         Circle o1 = new Circle();         // выводим на экран параметры окружности         o1.printCircle();         // Меняем абсциссу центра, обращааясь к свойству x         o1.x = 3;         // Меняем радиус, обращааясь к свойству r         o1.r = 12.3;         // выводим на экран обновлённые параметры окружности         o1.printCircle();         // Создаём другой объект того же класса         Circle o2 = new Circle();         o2.r = 3.14;         o2.zoomCircle(1.66);         o2.printCircle(); // Окружность с центром (0.0;0.0) и радиусом 5.2124     } }