Рекурсивная (recursive) функция или процедура – это функция или процедура, которая вызывает сама себя. Почти во всех случаях, рекурсия является ошибкой программирования и приводит к полному сбою программы. Наиболее общим симптомом возникновения этой проблемы является ошибка из-за нехватки памяти или ошибка из-за нехватки памяти в стеке.

Примеры рекурсивных функций

Самый простой пример, который может продемонстрировать рекурсивную функцию, это – пример функции возведения числа в степень. Алгоритм рункции Rekurs основан на том факте, что число, возведенное в степень n, равно этому же числу, умноженному само на себя в степени n-1. Например, 2³ равно 2х2^3-1 или 2х2².

Пример 6 содержит код функции Rekurs, возвращающей степень числа. В качестве аргументов функция принимает число и степень, в которую нужно возвести это число.

Пример 6.

Function Rekurs(num As Double, pwr As Integer) As Double
'рекурсивное возведение в степень
If pwr = 0 Then
    Rekurs = 1 'окончание рекурсии
Else
    Rekurs = num * Rekurs(num, pwr - 1) 'рекурсия
End If
End Function

Sub Test_Rekurs()
MsgBox Rekurs(2, 3)
End Sub

Пример 7. Чему равно F(23)&

Function F(x As Integer) As Integer
If x <= 1 Then
    F = x
ElseIf x Mod 2 <> 0 Then
    F = F(5 * x + 1) + 1
Else
    F = F(x \ 6) + 1
End If
End Function

Х = 23       F(23) = F(5 * 23 + 1) + 1 = F(116) + 1 = 5 + 1 = 6
X = 116      F(116) = F(116 \ 6) + 1 = F(19) + 1 = 4 + 1 = 5
X = 19       F(19) = F(5 * 19 + 1) + 1 = F(96) + 1 = 3 + 1 = 4
X = 96       F(96) = F(96 \ 6) + 1 = F(16) + 1 = 2 + 1 = 3
X = 16       F(16) = F(16 \ 6) + 1 = F(2) + 1 = 1 + 1 = 2
X = 2        F(2) = F(2 \ 6) + 1 = F(0) + 1 = 0 + 1 = 1
X = 0        F(0) = X = 0

Ответ: 6.