Рекурсия

Рекурсивные определения

Факториал

Факториал натурального числа $n$ есть произведение натуральных чисел от 1 до $n$: $n! = 1 \cdot 2 \cdots n$, с соглашением $0! = 1$. Многоточие в этой формуле скрывает цикл, и урок Циклы научил его писать. Однако то же определение допускает и другую форму, в которой нет никакого цикла: факториал числа $n$ равен $n$, умноженному на факториал числа $n - 1$, а факториал нуля равен 1.

Это рекурсивное определение: оно определяет факториал числа $n$ через факториал меньшего числа. Оно не порочный круг, потому что каждое применение второго правила спускается на одну ступень, а лестница кончается первым правилом: $3! = 3 \cdot 2! = 3 \cdot 2 \cdot 1! = 3 \cdot 2 \cdot 1 \cdot 0! = 6$. У обоих правил есть имена. Первое называется базовым случаем: оно даёт результат, ни на что больше не ссылаясь; второе называется рекурсивным случаем: оно сводит задачу к меньшему экземпляру той же задачи.

C++ позволяет функции вызывать саму себя, и благодаря этому определение переводится почти слово в слово.

#include <print>​// Факториал n.// Предусловие: 0 <= n <= 12 (граница обосновывается ниже).// Постусловие: возвращает n! = 1 · 2 · ... · n, причём 0! = 1.int factorial(int n){    if (n == 0) {        return 1;                   // базовый случай    }    return n * factorial(n - 1);    // рекурсивный случай}​int main(){    for (int n{0}; n <= 6; ++n) {        std::println("{}! = {}", n, factorial(n));    }}

0! = 11! = 12! = 23! = 64! = 245! = 1206! = 720

Контракт не декоративен: при $n = -1$ рекурсивный случай вызвал бы функцию с $-2$, затем с $-3$ и никогда не дошёл бы до 0; а $13!$ не помещается в int. Многие вводные тексты пишут этот факториал с базовым случаем if (n == 0 || n == 1), избыточным, но безвредным, и ничего не говорят ни об отрицательных числах, ни о размере результата: их код не завершается при $n < 0$ и даёт бессмысленный результат начиная с $13!$. Оба дефекта будут рассмотрены в своём параграфе.

Базовый случай и рекурсивный случай

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

Степень $x^n$, где $n$ натуральное, определяется равенствами $x^0 = 1$ и $x^n = x \cdot x^{n - 1}$: размер здесь есть показатель степени. Сумма цифр натурального числа $n$ (для 2026 она равна $2 + 0 + 2 + 6 = 10$) определяется так: если $n < 10$, сумма равна $n$, потому что у числа одна цифра; иначе она есть сумма цифр числа $\lfloor n / 10 \rfloor$, то есть числа $n$ без последней цифры, плюс эта последняя цифра, $n \bmod 10$. Здесь размер есть количество цифр.

#include <print>​// x в степени n.// Предусловие: n >= 0.// Постусловие: возвращает x^n, причём x^0 = 1.double power(double x, int n){    if (n == 0) {        return 1.0;    }    return x * power(x, n - 1);}​// Сумма десятичных цифр n.// Предусловие: n >= 0.// Постусловие: возвращает сумму цифр n.int digitSum(int n){    if (n < 10) {        return n;    }    return digitSum(n / 10) + n % 10;}​int main(){    std::println("2^10 = {}", power(2.0, 10));    std::println("1.5^3 = {}", power(1.5, 3));    std::println("сумма цифр числа 2026: {}", digitSum(2026));}

2^10 = 10241.5^3 = 3.375сумма цифр числа 2026: 10

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