Уроки 84 - 86
Рекурсия
§61. Рекурсия

Содержание урока

Что такое рекурсия?

Ханойские башни

Примеры

Как работает рекурсия

Вопросы и задания

Задачи

Примеры

Пример 1. Составим процедуру, которая переводит натуральное число в двоичную систему. Мы уже занимались вариантом этой задачи, где требовалось вывести 8-битную запись числа из диапазона 0..255, сохранив лидирующие нули. Теперь усложним задачу: лидирующие нули выводить не нужно, а натуральное число может быть любым (в пределах допустимого диапазона для выбранного типа данных).

Стандартный алгоритм перевода числа в двоичную систему можно записать, например, так:

Проблема в том, что двоичное число выводится «задом наперёд», т. е. первым будет выведен последний разряд. Как «перевернуть» число?

Есть разные способы решения этой задачи, которые сводятся к тому, чтобы запоминать остатки от деления (например, в символьной строке) и затем, когда результат будет полностью получен, вывести его на экран.

Однако можно применить красивый подход, использующий рекурсию. Идея такова: чтобы вывести двоичную запись числа n, нужно сначала вывести двоичную запись числа div(n, 2), а затем последнюю цифру — mod(n, 2). Если число-параметр равно нулю, нужно выйти из процедуры. Такой алгоритм очень просто программируется:

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

Пример 2. Составим функцию, которая вычисляет сумму цифр числа. Будем рассуждать так: сумма цифр числа п равна значению последней цифры плюс сумма цифр числа div(n, 10). Сумма цифр однозначного числа равна самому этому числу, это условие окончания рекурсии. Получаем следующую функцию:

Пример 3. Алгоритм Евклида, один из древнейших известных алгоритмов, предназначен для поиска наибольшего общего делителя (НОД) двух натуральных чисел. Формулируется он так.

Чтобы найти НОД двух натуральных чисел, нужно вычитать из большего числа меньшее до тех пор, пока меньшее не станет равно нулю. Тогда второе число и есть НОД исходных чисел.

Этот алгоритм может быть сформулирован в рекурсивном виде. Во-первых, в нём для перехода к следующему шагу используется равенство НОД(а, b) = НОД(а - b, b) при а ≥ b. Кроме того, задано условие останова: если одно из чисел равно нулю, то НОД совпадает со вторым числом. Поэтому можно написать такую рекурсивную функцию:

Заметим, что при равенстве одного из чисел нулю второе число совпадает с суммой двух чисел, поэтому в качестве результата функции принимается а + b.

Существует и более быстрый вариант алгоритма Евклида (модифицированный алгоритм), в котором большее число заменяется на остаток от деления большего числа на меньшее.

Следующая страница Как работает рекурсия

Cкачать материалы урока