Программирование рекурсивных вычислений

Понятие рекурсии считается одним из базовых понятий вычислительной математики и теории алгоритмов и одновременно является мощным инструментом программирования. Не вдаваясь в теоретические и реализационные аспекты рекурсивных вычислений, отметим, что идея рекурсии близка к идее математической индукции: если можно получить значение некоторой функции f(n+1) из f(n) и при этом задано значение f(0), то задана и вся функция f.

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

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

Во многих учебниках по программированию понятие рекурсивного определения демонстрируется на примере вычисления факториала (n!), и мы тоже не будем нарушать эту традицию. Напомним, что число n! определяется, как произведение всех целых чисел, не превышающих числа n (при этом определено, что 0! = 1). Очевидно, что n! = (n-1)! ´ n, (n-1)! = (n-2)! ´ (n-1)и так далее до единицы. Налицо рекурсивное определение функции вычисления факториала: чтобы вычислить n!нужно применить функцию факториала к числу (n-1), что потребует применения этой функции к числу (n-2)и так далее вплоть до достижения опорного условия рекурсии 1! = 1. Пример рекурсивного определения функции вычисления факториала приведен на рисунке 24, а). Сравните эту функцию с функцией, приведенной на рисунке 21, а).

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

Второй пример (рисунок 24 б) демонстрирует действительно полезное рекурсивное определение функции, предназначенной для вычисления суммы элементов массива. Аналогичные программы уже рассматривались при выполнении лабораторной работы №6, однако, в этих программах массив предполагался двумерным, что существенно упрощает задачу, так как позволяет обрабатывать массив двумя вложенными операторами цикла For. Если расширить постановку задачи и потребовать от программы возможности суммирования элементов такого массива, в котором некоторые элементы сами могут представлять массивы, и при этом не накладывать ограничений на глубину вложенности массивов, становится понятно, что оператор For здесь вряд ли поможет.

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

Рисунок 24 – Примеры рекурсивного определения подпрограмм