3. Основы Kotlin. Рекурсии и циклы

Циклы while и do..while

Иногда случается также, что требуемый цикл не сводится к перебору какого-то заранее известного набора элементов. В этом случае в Котлине вместо цикла for применяются циклы while или do..while. В качестве примера рассмотрим следующую задачу: найти число вхождений цифры m (от 0 до 9) в десятичную запись неотрицательного числа n. Например, в число n=5373393 цифра m=3 входит четыре раза.

Для решения этой задачи нам необходимо в цикле перебрать все цифры числа n. Для получения младшей цифры числа достаточно взять остаток от его деления на 10, для отбрасывания младшей цифры следует разделить его на 10. С помощью цикла while это записывается следующим образом.

fun digitCountInNumber(n: Int, m: Int): Int {
    var count = 0
    var number = n
    while (number > 0) {
        if (m == number % 10) {
            count++
        }
        number /= 10
    }
    return count
}

В отличие от цикла for, цикл while потенциально может выполниться любое количество раз. Перед каждой новой итерацией цикла (в том числе перед первой), цикл while проверяет записанное в скобках условие. Если оно верно, итерация выполняется, если нет, цикл завершается. Для данного примера при n=5373393 выполнится семь итераций цикла — по числу цифр в числе.

Въедливый (в хорошем смысле!) читатель заметит, что данная реализация может быть опровергнута следующим тестовым примером:

    @Test
    fun digitCountInNumber() {
        assertEquals(1, digitCountInNumber(0, 0))
    }

В этом примере мы ожидаем, что цифра 0 входит в число 0 один раз. Однако, написанная выше функция даст ответ 0. Исправить функцию можно следующим образом:

fun digitCountInNumber(n: Int, m: Int): Int {
    var count = 0
    var number = n
    do {
        if (m == number % 10) {
            count++
        }
        number /= 10
    } while (number > 0)
    return count
}

В данном примере цикл while был заменён циклом do..while. Отличие его состоит в том, что условие после ключевого слова while проверяется не ПЕРЕД каждой итерацией, а ПОСЛЕ каждой итерации, из-за этого тело цикла do..whileвсегда выполняется хотя бы один раз. Поэтому данные циклы называются циклом с предусловием (while) или циклом с постусловием (do..while).

Конкретно для случая с n = 0 цикл while не будет выполнен ни разу, и результат останется равным 0. Цикл do..whileбудет выполнен один раз, в числе будет найдена цифра 0 и результат получится равным 1, то есть в данном конкретном случае цикл do..while лучше подходит для решения задачи. В общем случае, любая задача может быть решена с применением произвольного из этих двух циклов, вопрос лишь в том, какое решение будет выглядеть лучше. Цикл while на практике встречается существенно чаще.

Заметим, что у данной задачи возможно и рекурсивное решение. Как его можно придумать? Для этого вначале следует решить задачу в тривиальном случае — для n < 10. При этом результат будет равен 1, если m = n, и 0 в противном случае. После этого следует придумать переход от числа с большим количеством цифр к числу или числам, в которых цифр меньше. Например, число n можно разбить на два других: n % 10, содержащее только последнюю цифру, и n / 10, содержащее все остальные цифры:

fun digitCountInNumber(n: Int, m: Int): Int =
        when {
            n == m -> 1
            n < 10 -> 0
            else -> digitCountInNumber(n / 10, m) + digitCountInNumber(n % 10, m)
        }

Обратите внимание, что рекурсивное решение часто короче и изящнее итеративного.

Упражнения

Откройте файл srс/lesson3/task1/Loop.kt в проекте KotlinAsFirst.

Выберите любую из задач в нём. Придумайте её решение (итеративное или рекурсивное) и запишите его в теле соответствующей функции.

Откройте файл test/lesson3/task1/Tests.kt, найдите в нём тестовую функцию — её название должно совпадать с названием написанной вами функции. Запустите тестирование, в случае обнаружения ошибок исправьте их и добейтесь прохождения теста. Подумайте, все ли необходимые проверки включены в состав тестовой функции, добавьте в неё недостающие проверки.

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