Computer Science на языке Java 2022 Дэвид Копец Классические задачи Computer Science на языке Java 2022 ббк

1.1.1. Первый вариант рекурсии
Приведенная.формула.для.определения.числа.в.последовательности.Фибоначчи.
(рис..1.1).представляет.собой.псевдокод,.который.можно.легко.перевести.в.
ре-
курсивный
.метод.Java..(Рекурсивным.называется.метод,.который.вызывает.сам.
себя.).Такой.механический.перевод.станет.нашей.первой.попыткой.написать.

---

26
Глава 1.
Простые задачи
метод,.возвращающий.заданное.значение.последовательности.Фибоначчи.
(листинг.1.1).
Листинг 1.1. 
Fib1.java
package 
chapter1;
public class 
Fib1 {
// Этот метод вызывает ошибку java.lang.StackOverflowError
private static int 
fib1(
int
n) {
return
fib1
(n — 1) + 
fib1
(n — 2);
}
Рис. 1.1.
Рост каждого человечка равен сумме роста двух предыдущих
Попробуем.запустить.этот.метод,.вызвав.его.и.передав.ему.значение.(листинг.1.2).
Листинг 1.2. 
Fib1.java (продолжение)
public static void 
main(String[] args) {
// Не запускайте это!
System.
out
.println(
fib1
(5));
}
}

---

1.1. Ряд Фибоначчи
27
Ой-ой-ой!.При.попытке.запустить.
fib1.java
.получаем.ошибку.превышения.
максимальной.глубины.рекурсии:
Exception in thread "main" java.lang.StackOverflowError
Проблема.в.том,.что.функция.
fib1()
.будет.работать.вечно,.не.возвращая.оконча-
тельный.результат..Каждый.вызов.
fib1()
.приводит.к.двум.другим.вызовам.
fib1()
,.
и.так.без.конца..Такую.ситуацию.называют.
бесконечной рекурсией
.(рис..1.2),.она.
подобна.
бесконечному циклу
.
. .
Рис. 1.2.
Рекурсивная функция fib(n) 
вызывает сама себя с аргументами 
n
– 1 
и 
n
– 2