Рекурсивним називають метод, якщо він викликає сам себе в якості допоміжного. В основі рекурсивного методу лежить так зване "рекурсивне визначення" будь-якого поняття. Класичним прикладом рекурсивного методу є метод, що обчислює факторіал.
З курсу математики відомо, що 0! = 1! = 1, n! = 1 * 2 * 3 ... * n. З іншого боку n! = (N-1)! * N. Таким чином, відомі два окремих випадки параметра n. а саме n = 0 і n = 1. при яких ми без будь-яких додаткових обчислень можемо визначити значення факторіала. У всіх інших випадках, тобто для n> 1. значення факторіала може бути обчислено через значення факторіала для параметра n-1. Таким чином, рекурсивний метод буде мати вигляд:
Розглянемо роботу описаного вище рекурсивного методу для n = 3.
Перший виклик методу здійснюється з методу Main. в нашому випадку командою f = F (3). Етап входження в рекурсію позначимо жирними стрілками. Він триває до тих пір, поки значення змінної n не стає рівною 1. Після цього починається вихід з рекурсії (тонкі стрілки). В результаті обчислень виходить, що F (3) = 3 * 2 * 1.
Розглянутий вид рекурсії називають прямою. Метод з прямою рекурсією зазвичай містить наступну структуру:
В якості <условия> зазвичай записуються деякі граничні випадки параметрів, переданих рекурсивному методу, при яких результат його роботи заздалегідь відомий, тому далі йде простий оператор або блок, а в галузі else відбувається рекурсивний виклик даного методу з іншими параметрами.
Слід розуміти, що будь-який рекурсивний метод можна перетворити в звичайний метод. І практично будь-який метод можна перетворити в рекурсивний, якщо виявити рекурентне співвідношення між обчислюються в методі значеннями.
Далі для порівняння кожну задачу будемо вирішувати з використанням звичайного і рекурсивного методів:
Приклад 1: Знайти суму цифр числа А.
Відомо, що будь-яке натуральне число A = an an-1. a1 a0. де an an-1. a1 a0 - цифри числа, можна представити таким чином: