Информатика_ЗФ / 2013_Информатика УМО_легпром

Рекурсивные алгоритмы *

Рекурсия– это одна из фундаментальных концепций в математике и программировании. Это одна из форм мышления, это мощное средство, позволяющее строить элегантные и выразительные алгоритмы. Объект называется рекурсивным, если он содержит сам себя или определен с помощью самого себя.

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

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

Рекуррентность– это рекурсивное определение функции. Классический пример такого рода функций – факториал. Напомним, факториал нуля равен 1, а факториал натурального числа N определяется как произведение натуральных чисел от единицы до N, что выражается рекуррентной формулой: N!=N (N-1)!, для N>=1 и 0! = 1. То есть для определения факториала одного числа требуется знать или вычислить факториал другого, уменьшенного на единицу. А это, в свою очередь, может потребовать определения факториала ещё меньшего числа. И так далее, до единицы. Этому напрямую соответствует нижеследующая рекурсивная функция:

Function factorial(N As Integer) As Long

If N=0 Then factorial=1 Else factorial=N*factorial(N-1)

End Function

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

Стоит также отметить, что не все языки допускают использование рекурсий. В таких случаях можно обойтись использованием обычных циклов. Например, ту же функцию факториал реализовать без использования рекурсии:

Function factorial(N As Integer) As Long

factorial=1

For Счётчик=1 To N

factorial=factorial*Счётчик

Next

End Function

Содержание