chapter03.adoc

3. Рекурсии и циклы

Почти все реальные задачи требуют для своего решения не только ветвлений, но и многократного повторения однотипных действий. Простым примером такой задачи является вычисление факториала factorial(n) = n!. Напомним, что факториал натурального числа n равен произведению всех чисел от 1 до n. По принятому соглашению, 0! = 1 и 1! = 1, факториал от отрицательного числа не определён.

Рекурсивная функция

Наиболее простым для построения программной реализации является индуктивное определение факториала, согласно которому n! = n(n-1)!. Базой индуктивного определения служат соглашения о значении 0! и 1!. На Котлине подобное определение реализуется следующим образом:

fun factorial(n: Int): Double = if (n < 2) 1.0 else n * factorial(n - 1)

Здесь мы использовали приём программирования под названием рекурсия. Для вычисления результата функции factorial происходит вызов этой же функции, но с меньшим значением аргумента. Рано или поздно условие if (n < 2) окажется выполненным, и значение функции будет вычислено. Обратите внимание, что тип результата функции указан как Double. Попробуйте понять, что произойдёт, если Double заменить на Int, а литерал 1.0 на 1.

Цикл for, мутирующие переменные, интервалы и прогрессии

Возможна также реализация итеративного определения, а именно n! = 1 * 2 * …​ * (n-1) * n. Для этого необходимо использовать циклы; наиболее распространённым в Котлине является цикл for, который подходит и для этой задачи. Реализация будет выглядеть так:

fun factorial(n: Int): Double {
    // Мутирующая переменная (var)
    var result = 1.0
    for (i in 1..n) {
        result = result * i
    }
    return result
}

Конструкция for (i in 1..n) { …​ } читается как "Для всех i в интервале от 1 до n (выполнить) …​". В данной конструкции объявляется параметр цикла for, которому даётся имя i. Внутри фигурных скобок находится тело цикла for. Тело цикла в данном случае будет выполнено n раз, то есть произойдёт n итераций. На каждой итерации параметр i будет иметь различные значения — от 1 до n.

Строчкой выше объявлена так называемая мутирующая переменная result. Для её объявления мы использовали ключевое слово var (variable) — в отличие от val (value) для обычных переменных. Мутирующая переменная получает значение 1.0 при её объявлении, но в процессе выполнения функции она может изменять своё значение.

Оператор result = result * i выполняет так называемое присваивание мутирующей переменной другого значения. При этом вначале берётся её прежнее значение (например, 2.0 на 3-й итерации цикла), оно умножается на значение параметра i (3 на 3-й итерации цикла) и результат (6.0) присваивается переменной result. Если бы мы объявили переменную result как val result = 1.0, то в этой строчке функции мы получили бы ошибку:

Val cannot be reassigned

В последнем операторе return result определяется окончательный результат вычисления факториала.

Оператор for может использоваться не только для перебора чисел в интервале (от меньшего к большему с шагом 1), но и для перебора чисел в заданной прогрессии. Интервал, как мы уже видели, создаётся оператором вида min..max. Типичные примеры создания прогрессии выглядят так:

• 10 downTo 1 — прогрессия от большего числа к меньшему, с шагом 1 (10, 9, 8, …​, 1);

• 1..99 step 2 — прогрессия от меньшего числа к большему, но с шагом 2 (в данном случае, перебор всех нечётных чисел по возрастанию);

• 100 downTo 2 step 2 — прогрессия от большего числа к меньшему, с шагом 2 (перебор всех чётных чисел по убыванию).

Модифицирующие операторы

Откройте теперь файл srс/lesson3/task1/Loop.kt в проекте KotlinAsFirst в IDE и внимательно посмотрите на определение функции factorial вверху файла. Внимательные читатели обнаружат, что оператор result = result * i подчёркнут серой волнистой чертой. Если навести на него указатель мыши, мы увидим сообщение "Replace with *= operator", то есть "Заменить оператором *=". Нажмите Alt+Enter, вы увидите контекстное меню с символом лампочки и командой "Replace with *= operator". Нажмите Enter, и IDE выполнит замену, которую предлагает. Мы получим следующий текст функции:

fun factorial(n: Int): Double {
    // Мутирующая переменная (var)
    var result = 1.0
    for (i in 1..n) {
        result *= i
    }
    return result
}

Оператор *= относится к большой группе модифицирующих операторов и выполняет домножение текущего значения переменной result на значение параметра i. Аналогично ему работают операторы +=, -=, /=, %= и некоторые другие.

Последовательная проверка условий

Рассмотрим теперь несколько более сложный пример. Пусть нам требуется написать функцию, проверяющую натуральное число на простоту. Напомним, что число называется простым (prime), если оно делится нацело только на единицу и на себя, и составным, если у него есть и другие делители (единица обычно не считается ни простым, ни составным числом).

Прямолинейная проверка предполагает деление заданного числа n последовательно на числа в интервале от 2 до n-1. Чтобы проверить, делится ли число n нацело на другое число m, достаточно сравнить остаток от деления n % m с нулём. Если хотя бы раз мы успешно поделили нацело — исходное число n не является простым.

fun isPrime(n: Int): Boolean {
    if (n < 2) return false // Необходимо, так как 1 -- не простое число
    for (m in 2..n - 1) {
        if (n % m == 0) return false
    }
    return true
}

Обратите внимание, что, найдя делитель, мы сразу сообщаем о том, что результат — false — при этом прерывается как выполнение цикла, так и выполнение функции, поскольку результат уже определён. Чтобы доказать, что число является составным, нам достаточно найти хотя бы ОДИН делитель от 2 до n-1. Однако о результате true мы можем сообщить только после окончания цикла, проверив ВСЕ делители: чтобы доказать простоту числа, надо убедиться, что НИ ОДНО число от 2 до n-1 не является делителем. Начинающие часто делают вот такую ошибку:

    for (m in 2..n - 1) {
        if (n % m == 0) return false
        else return true
    }

что, конечно, неверно. Такой цикл будет выполнен только один раз, результат будет true для нечётных и false для чётных чисел.

В тестовой функции мы можем проверить, что числа 2, 5 и 11 являются простыми, а числа 1, 4, 9 и 15 — составными. Мы можем также написать более сложную проверку, использовав тот факт, что первые 1000 простых чисел лежат в интервале от 2 до 7919 — см. https://en.wikipedia.org/wiki/List_of_prime_numbers.

    @Test
    fun isPrime() {
        var count = 0
        for (n in 2..7919) {
            if (isPrime(n)) {
                count++
            }
        }
        assertEquals(1000, count)
    }

Мы в цикле проверяем числа от 2 до 7919 на простоту. Каждый раз, когда число оказывается простым, мы выполняем оператор count++ — сокращённая форма записи count = count + 1 или count += 1, так называемый оператор инкремента (существует также оператор --, или оператор декремента).

Попробуем теперь с помощью isPrime узнать, сколько существует простых чисел, меньших десяти миллионов (для этого достаточно заменить в приведённом участке кода 7919 на 10000000). Если запустить такую функцию на выполнение, оно займёт довольно много времени. Всё дело в том, что наша функция isPrime(n: Int) выполняет лишние проверки. В частности, достаточно проверить делимость числа n на все числа в интервале от 2 до n/2, так как на большие числа n всё равно делится не будет. Более того, достаточно ограничится интервалом от 2 до √n — если n и делится на какое-то большее √n число (например, 50 делится на 10), то оно будет делится и на какое-то меньшее число (в данном случае, 50 делится на 5=50/10).

fun isPrime(n: Int): Boolean {
    if (n < 2) return false // Необходимо, так как 1 -- не простое число
    for (m in 2..sqrt(n.toDouble()).toInt()) {
        if (n % m == 0) return false
    }
    return true
}

Обратите внимание, что перед вычислением квадратного корня мы были вынуждены воспользоваться функцией n.toDouble() для получения вещественного числа из целого, а после вычисления — функцией .toInt() для получения целого числа из вещественного. Обе эти встроенные в Котлин функции имеют необычную для начинающих форму записи, которая читается как "n преобразовать к Double", "…​ преобразовать к Int". Вместо того, чтобы записать аргумент внутри круглых скобок toDouble(n), мы записываем его перед именем функции, отделяя его от имени символом точки. Подобный аргумент функции называется её получателем (receiver), в будущем мы ещё неоднократно столкнёмся с подобной формой записи.

Прерывание и продолжение цикла

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

Продемонстрируем их на примере. Совершенным числом называется такое натуральное число, которое равно сумме всех своих делителей, кроме себя самого. В частности, 6 = 1 + 2 + 3 и 28 = 1 + 2 + 4 + 7 + 14 — совершенные числа. Напишем функцию, определяющую, является ли заданное число n совершенным.

fun isPerfect(n: Int): Boolean {
    var sum = 1
    for (m in 2..n/2) {
        if (n % m == 0) {
            sum += m
            if (sum > n) break
        }
    }
    return sum == n
}

Данная функция перебирает все возможные делители числа n от 2 до n/2 (единицу перебирать бессмысленно, поскольку на неё делится любое число — поэтому мутирующая переменная sum изначально равна 1, а не 0). Каждый найденный делитель прибавляется к сумме. Если в какой-то момент набранная сумма оказалась больше n — цикл можно прервать с помощью break, так как последующие делители могут только увеличить её ещё больше. После прерывания цикла выполняется следующий за ним оператор, в данном случае return.

Другой вариант записи той же самой функции использует оператор продолжения continue:

fun isPerfect(n: Int): Boolean {
    var sum = 1
    for (m in 2..n/2) {
        if (n % m > 0) continue
        sum += m
        if (sum > n) break
    }
    return sum == n
}

Здесь вместо того, чтобы проверить, что n делится на m, мы проверяем обратное условие — что n НЕ ДЕЛИТСЯ на m. Если оно верно, выполняется оператор continue, при этом остаток данной итерации цикла пропускается, происходит увеличение значения m на 1 и переход к следующей итерации. Обе реализации isPerfect равнозначны, применение той или другой из них — дело вкуса.

Циклы 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 на ваш выбор. Убедитесь в том, что можете решать такие задачи уверенно и без посторонней помощи. Попробуйте придумать рекурсивное решение хотя бы одной задачи. После этого вы можете перейти к следующему разделу.