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

Рекурсия происходит, если функция или подпрограмма вызывает сама себя. Прямая рекурсия (direct recursion) выглядит примерно так:

Function Factorial(num As Long) As Long

Factorial = num * Factorial(num - 1)

End Function

В случае косвенной рекурсии (indirect recursion) рекурсивная процедура вызывает другую процедуру, которая, в свою очередь, вызывает первую:

Private Sub Ping(num As Integer)

Pong(num - 1)

End Sub

Private Sub Pong(num As Integer)

Ping(num / 2)

End Sub

===========81

Рекурсия полезна при решении задач, которые естественным образом разбиваются на несколько подзадач, каждая из которых является более простым случаем исходной задачи. Можно представить дерево на рис. 5.1 в виде «ствола», на котором находятся два дерева меньших размеров. Тогда можно написать рекурсивную процедуру для рисования деревьев:

Private Sub DrawTree()

Нарисовать "ствол"

Нарисовать дерево меньшего размера, повернутое на -45 градусов

Нарисовать дерево меньшего размера, повернутое на 45 градусов

End Sub

Хотя рекурсия и может упростить понимание некоторых проблем, люди обычно не мыслят рекурсивно. Они обычно стремятся разбить сложные задачи на задачи меньшего объема, которые могут быть выполнены последовательно одна за другой до полного завершения. Например, чтобы покрасить изгородь, можно начать с ее левого края и продолжать двигаться вправо до завершения. Вероятно, во время выполнения подобной задачи вы не думаете о возможности рекурсивной окраски — вначале левой половины изгороди, а затем рекурсивно — правой.

Для того чтобы думать рекурсивно, нужно разбить задачу на подзадачи, которые затем можно разбить на подзадачи меньшего размера. В какой‑то момент подзадачи становятся настолько простыми, что могут быть выполнены непосредственно. Когда завершится выполнение подзадач, большие подзадачи, которые из них составлены, также будут выполнены. Исходная задача окажется выполнена, когда будут все выполнены образующие ее подзадачи.

Рекурсивное вычисление факториалов

Факториал числа N записывается как N! (произносится «эн факториал»). По определению, 0! равно 1. Остальные значения определяются формулой:

N! = N * (N - 1) * (N - 2) * ... * 2 * 1

Как уже упоминалось в 1 главе, эта функция чрезвычайно быстро растет с увеличением N. В табл. 5.1 приведены 10 первых значений функции факториала.

Можно также определить функцию факториала рекурсивно:

0! = 1

N! = N * (N - 1)! для N > 0.

@Рис. 5.1. Дерево, составленное из двух деревьев меньшего размера

===========82

@Таблица 5.1. Значения функции факториала

Легко написать на основе этого определения рекурсивную функцию:

Public Function Factorial(num As Integer) As Integer

If num <= 0 Then

Factorial = 1

Else

Factorial = num * Factorial(num - 1)

End If

End Function

Вначале эта функция проверяет, что число меньше или равно 0. Факториал для чисел меньше нуля не определен, но это условие проверяется для подстраховки. Если бы функция проверяла только условие равенства числа нулю, то для отрицательных чисел рекурсия была бы бесконечной.

Если входное значение меньше или равно 0, функция возвращает значение 1. В остальных случаях, значение функции равно произведению входного значения на факториал от входного значения, уменьшенного на единицу.

То, что эта рекурсивная функция в конце концов остановится, гарантируется двумя фактами. Во‑первых, при каждом последующем вызове, значение параметра num уменьшается на единицу. Во‑вторых, значение num ограничено снизу нулем. Когда num становится равным 0, функция останавливает рекурсию. Условие, например, в данном случае условие num<=0, называется или условием остановки рекурсии (base case или stopping case).

При каждом вызове подпрограммы, система сохраняет ряд параметров в системном стеке, как описывалось в 3 главе. Так как этот стек играет важную роль, иногда его называют просто стеком. Если рекурсивная функция вызовет себя слишком много раз, она может исчерпать стековое пространство и аварийно завершить работу с ошибкой «Out of stack space».

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