Рекурсивним називається метод, який викликає сам себе. Така рекурсія називається прямою. Існує ще непряма рекурсія, коли два або більш за метод викликають один одного. Якщо метод викликає себе, в стеку створюється копія значень його параметрів, як і при виклику звичайного методу, після чого управління передається першому виконуваному операторові методу. При повторному виклику цей процес повторюється.
Ясно, що для завершення обчислень кожен рекурсивний метод повинен містити хоч би одну нерекурсивну гілку алгоритму, що закінчується оператором повернення. При завершенні методу відповідна частина стека звільняється і управління передається методу, виконання якого продовжується з точки, наступної за рекурсивним викликом.
Класичним прикладом рекурсивної функції є функція обчислення факторіалу (це не означає, що факторіал слід обчислювати саме так). Для того, щоб набути значення факторіалу числа n, потрібно помножити на n факторіал числа (n - 1). Відомо також, що 0 != 1 і 1 != 1:
long fact (long n )
{
if ( n = = 0 || n = = 1 ) return 1; // нерекурсивна гілка
return (n* fact(n -1)); // рекурсивна гілка
}
Tе ж саме можна записати коротше:
long fact (long n )
{
return ( n >1 ) ? n * fact(n -1):1;
}
Рекурсивні методи найчастіше застосовують для компактної реалізації рекурсивних алгоритмів. Будь-який рекурсивний метод можна реалізувати без застосування рекурсії, для цього програміст повинен забезпечити зберігання всіх необхідних даних самостійно. До переваг рекурсії можна віднести компактність запису, до недоліків - витрата часу і пам'яті на повторні виклики методу і передачу йому копій параметрів. Головний недолік - переповнення стека.
