ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ

Рекурсия (самоповторение) – это действие, возвращающееся к “самому себе”. Существует два вида рекурсии:

1. прямая рекурсия (процедура или функция вызывает саму себя);

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

Рекурсию следует использовать только тогда, когда задача легко поддается рекурсивному решению. Важно отметить, что любая задача, которая решена рекурсивно, может быть решена и без рекурсии.

С понятием "рекурсия" тесно связано понятие "рекуррентная последовательность”, вычисление n-го члена которой производится с помощью рекурсии. Определим это понятие.

Числовая последовательность {х_k} называется рекуррентной последовательностью, если

где k=p, p=1, …

ДЕМОНСТРАЦИОННЫЕ ПРИМЕРЫ

Пример 1

'Имя файла Factorial.vbs

'Задача: вычислить значение факториала введённого натурального числа n

'--------------------------------------

FUNCTION RecFact(n)

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

If n=0 Then

RecFact=1

Else

RecFact=n*RecFact(n-1)

End If

End FUNCTION

'---------------------------------------

FUNCTION NonRecFact(n)

'Вычисление факториала при помощи цикла

dim P

P=1

While (n>1)

P=n*P

n=n-1

WEnd

NonRecFact=P

End FUNCTION

'---------------------------------------

Dim n

n=CInt(InputBox("Введите натуральное число",_

"Вычисление факториала натурального n:","0"))

number=n

MsgBox "Рекурсивно вычисленный факториал: "&RecFact(n)&_

VbCrLf&_

"Нерекурсивно вычисленный факториал: "&NonRecFact(n)_

,vbInformation,"Результат вычисления факториала числа "&number&":"

Пример 2

'Имя файла Nod.vbs

'Задача: найти наибольший общий делитель (НОД) двух целых чисел

'--------------------------------------

FUNCTION RecNod(n,m)

'Рекурсивное вычисление НОД

If n=m Then

RecNod=n

ElseIf n>m Then

RecNod=RecNod(n-m, m)

Else

RecNod=RecNod(n, m-n)

End If

End FUNCTION

'---------------------------------------

FUNCTION NonRecNod(n,m)

'Вычисление НОД с помощью цикла

While (n<>m)

If n>m Then

n=n-m

Else

m=m-n

End If

WEnd

NonRecNod=n

End FUNCTION

'---------------------------------------

Dim n, m

n=CLng(InputBox("Введите натуральное число n", "Вычисление НОД: ","25"))

m=CLng(InputBox("Введите натуральное число m", "Вычисление НОД: ","50"))

MsgBox "Рекурсивно вычисленный НОД: "&CStr(RecNod(abs(n),abs(m)))&_

VbCrLf&_

"Нерекурсивно вычисленный НОД: "&CStr(NonRecNod(abs(n),abs(m)))_

,vbInformation,"Результат вычисления НОД:"

Пример 3

'Имя файла: Fib.vbs

'Задача: При помощи рекурсивной функции найти и вывести на экран

' к-й элемент последовательности Фибоначчи. Последовательность Фибоначчи:

' 1, 1, 2, 3, 5, 8, 13, ... Нумерация данных чисел начинается с 0.

'-----------------------------------------

FUNCTION Fib(k)

If k=0 or k=1 Then

Fib=1

Else

Fib=fib(k-1)+Fib(k-2)

End If End FUNCTION

'-----------------------------------------

dim k

k=Cint(InputBox("Введите k: ", "Вычисление к-го элемента посл-ти Фибоначчи: "))

MsgBox k&"-й"&" элемент последовательности фибоначчи: "&_

vbCrlf& Fib(k), vbInformation, "Результат: "

Пример 4

'Имя файла Koren.vbs

'Задача:'Вычислить, используя рекурсию: 'sqr(1+(n+1)*sgr(1+(n+2)*sqr(1+(n+3)*sqr(1+...

' где n - натуральное число,

' k - количество корней

'--------------------------------------

FUNCTION Kor(i, n)

If i=k Then

Kor=sqr(1+(n+k))

Else

Kor=sqr(1+(n+i)*Kor(i+1,n))

End If

End FUNCTION

'---------------------------------------

Dim n,k,i

n=CInt(InputBox("Введите натуральное число n: ", "Ввод параметров:","1"))

k=CInt(InputBox("Введите количество корней k: ", "Ввод параметров:","1"))

i=1

MsgBox "Значение вычисленного корня: "&CStr(Kor(i,n)), vbInformation, "Результат: "