Сайт разработчика Александр Климова

/* Моя кошка замечательно разбирается в программировании. Стоит мне объяснить проблему ей - и все становится ясно. */
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
Реклама