Урок 15. Рекурсия – Devcolibri

Урок 15. Рекурсия

После просмотра видеоверсии урока обязательно изучите текстовый материал. Он дополняет видеоматериал и позволит вам полностью понять тему урока.

Наглядный пример рекурсии

Мы рассмотрим на примере задачу распознавания палиндромов. Палиндром – число, буквосочетание, слово или текст, одинаково читающееся в обоих направлениях. Например, число 101; слова «топот», «шалаш» в русском языке. Давайте разберём пример работы программы на слове “топот”. Алгоритм работы:

  1. Сравнение первой и последней буквы в слове (с помощью метода charAt()).
  2. Если они равны, то мы будем обрезать первый и последний символ в строке и делать всё тоже самое для строки без тех символов, которые мы уже сравнили.
  3. Возвращаемся к шагу 1.

Условия для выхода из рекурсии:

  • Если осталась одна буква в слове или букв не осталось совсем.
  • Если первый и последний символ строки не равны (означает, что слово – не палиндром).

Давайте разберём алгоритм на примере слова “топот”:

  • Вызываем функцию, передавая строку топот (первый вызов).
  • т == тtrue. Вызываем функцию, передавая строку опо (второй вызов).
  • o == otrue. Вызываем функцию, передавая строку п (третий вызов).
  • Длина строки п == 1, завершаем рекурсию, возвращая значение true.
  • Результат приходит в функцию, которую вызывали второй.
  • Результат приходит в функцию, которую вызвали первой.
public class Main {

    public static void main(String[] args) {
        System.out.println(isPalindrome("топот"));
        System.out.println(isPalindrome("шорох"));
    }

    public static boolean isPalindrome(String str) {
        if(str.length() == 1 || str.length() == 0) {
            return true;
        }

        char firstChar = str.charAt(0);
        char lastChar = str.charAt(str.length()-1);
        if(firstChar != lastChar){
            return false;
        }

        String cutString = str.substring(1, str.length() - 1);
        return isPalindrome(cutString);
    }
}

Результат:

true
false

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

Возникли проблемы при прохождении? Напишите нам в чат поддержки Вконтакте или Facebook. Мы поможем вам решить проблему и вы сможете продолжить обучение.
УВИДЕТЬ ВСЕ Добавить заметку
ВЫ
Добавить ваш комментарий