/* Моя кошка замечательно разбирается в программировании. Стоит мне объяснить проблему ей - и все становится ясно. */
John Robbins, Debugging Applications, Microsoft Press, 2000
Язык Java поддерживает рекурсию. Рекурсия в программировании - это когда метод вызывает сам себя. В таком случае метод называют рекурсивным.
Классический пример использования рекурсии, который показывают во всех учебниках по программированию - вычисление факториала числа. Факториал числа N - это произведение всех целых чисел от 1 до N. Например, возьмём число 3 и вычислим его факториал. У нас получится 1 * 2 * 3 = 6. Теперь напишем метод на Java в отдельном классе:
class Factorial {
// рекурсивный метод
int fact(int n) {
int result;
if (n == 1)
return 1;
result = fact(n - 1) * n;
return result;
}
}
Вызовем рекурсивный метод:
Factorial f = new Factorial();
// получим число, введенное пользователем
int usernumber = Integer.valueOf(editResult.getText().toString());
// вычисляем факториал и выводим результат в текстовой метке
textViewInfo.setText("Факториал " + usernumber + " равен "
+ f.fact(usernumber));
Теперь, если вводить числа в текстовом поле, то получим следующие результаты:
Факториал 3 равен 6 Факториал 4 равен 24 Факториал 5 равен 120 и т.д.
Понять, как работает метод, довольно трудно, можно всю голову сломать. Однако попробуем. При вызове метода fact() с аргументом, равным 1, вернётся 1. Тут пока понятно. При других числах возвращается fact(n - 1) * n. Получается, что нужно ещё раз вызвать метод fact(). И так происходит до тех пор, пока не дойдёт до единицы. При этом промежуточные значения умножаются.
Когда метод вызывает сам себя, новым локальным переменным и параметром выделяется место в стеке и код метода выполняется с этими новыми начальными значениями. При каждом возврате из рекурсивного вызова старые локальные переменные и параметры удаляются из стека, и выполнение продолжается с момента вызова внутри метода.
Следует помнить, что рекурсивные методы требуют больше ресурсов для выполнения и даже может вызвать переполнение памяти при слишком больших значениях.
Рекурсивные методы часто используют в сортировке, а также в алгоритмах, связанных с искусственным интеллектом. В обычной практике рекурсия используется редко.
При использовании рекурсивных методов нужно смотреть, чтобы в программе был оператор if для выхода из рекурсивного метода без выполнения рекурсивного вызова. Иначе метод никогда не выполнит возврат.
Рассмотрим ещё один пример вывода первых элементов массива. Создадим отдельный класс с рекурсивным методом:
class Recursion {
int aValues[];
StringBuilder sb = new StringBuilder();
// Конструктор
Recursion(int i) {
aValues = new int[i];
}
// Рекурсивное отображение элементов массива
String printArray(int i) {
if (i == 0)
return ""; // не забываем про выход из метода
else
printArray(i - 1);
String output = "[" + (i - 1) + "] " + aValues[i - 1] + "\n";
sb.append(output);
return sb.toString();
}
}
public void onClick(View v) {
Recursion recursion = new Recursion(5);
int i;
for (i = 0; i < 5; i++)
recursion.aValues[i] = i;
textInfo.append(recursion.printArray(5));
}
Запустив код мы увидим:
[0] 0 [1] 1 [2] 2 [3] 3 [4] 4