Рекурсия

В VB .NET, как и в любом сколько-нибудь серьезном языке программирования, поддерживается рекурсия — решение задач посредством сведения их к более простым задачам того же типа. Одним из стандартных примеров рекурсивного решения является перебор дерева каталогов на диске (см. главу 9).

На концептуальном уровне рекурсивное решение выглядит следующим образом:

Решение задачи с применением рекурсии

If задача тривиальна

Решить Else

Упростить задачу, сводя ее к однотипной, но более простой задаче

Решить более простую задачу с применением рекурсии

End If

(Возможно) Объединить решение простой задачи (или задач)

с решением исходной задачи.

Рекурсивная функция или процедура постоянно вызывает сама себя, непрерывно упрощая задачу до тех пор, пока ее решение не станет тривиальным; в этот момент задача решается, и происходит возврат к предыдущему уровню. Применение рекурсии нередко связано с принципиальным изменением подхода к некоторым задачам, порождающим особенно элегантные решения и столь же элегантные программы (кстати, многие алгоритмы сортировки — такие, как встроенный метод Sort класса .NET Array, — основаны на принципе рекурсии).

В качестве примера мы рассмотрим программу поиска наибольшего общего делителя двух целых чисел (то есть наибольшего целого числа, на которое они оба делятся без остатка). Пример:

НОД(4,6) = 2 (наибольшее число, на которое 4 и 6 делятся без остатка).

НОД(12,7) - 1 (числа 12 и 7 не делятся ни на одно целое число, большее 1).

Около 2000 лет назад Евклид предложил следующий алгоритм вычисления НОД двух целых чисел а и b:

Если а делится на b, НОД= b. В противном случае НОД (а, b) = НОД (b, a Mod b)

Вспомним, что функция Mod возвращает остаток от целочисленного деления, а выражение a Mod b,равно 0 лишь в том случае, если а кратно b. Пример:

НОД(126.12)=НОД (12. 126 Mod 12)=НОД (12,6) - 6

Ниже приведен пример рекурсивной функции для вычисления НОД. В строке, выделенной жирным шрифтом, функция GCD вызывает сама себя для более простого случая:

Option Strict On Module Modulel

Function GCD(ByVal p As Long, ByVal q As Long) As Long

If Q Mod P = 0 Then

Return P Else

Return GCD(Q, P Mod Q)

End If

End Function Public Sub Main()

Console.WriteLine("The GCD of 36 and 99 is " & GCD(36. 99))

Console. ReadLine()

End Sub

End Module

Сначала обрабатывается тривиальный случай Q Mod P = 0. Если это условие не выполняется, функция GCD снова вызывает себя для более простого случая, поскольку в результате применения Mod мы переходим к меньшим числам. В приведенном примере объединять результаты не нужно (как, например, в функции сортировки).

Содержание раздела