Просмотр содержимого документа
«Рекурсивные функции»
Отдельно остановимся на рекурсивных функциях. Рекурсивная функция представляет такую конструкцию, при которой функция вызывает саму себя.
Возьмем, к примеру, вычисление факториала, которое использует формулу n! = 1 * 2 * … * n. Например, факториал числа 5 равен 120 = 1 * 2 * 3 * 4 * 5.
Определим метод для нахождения факториала:
| 1 2 3 4 5 6 7 8 9 10 11 | static int Factorial(int x) { if (x == 0) { return 1; } else { return x * Factorial(x - 1); } } |
Итак, здесь у нас задается условие, что если вводимое число не равно 0, то мы умножаем данное число на результат этой же функции, в которую в качестве параметра передается число x-1. То есть происходит рекурсивный спуск. И так, пока не дойдем того момента, когда значение параметра не будет равно единице.
При создании рекурсивной функции в ней обязательно должен быть некоторый базовый вариант, который использует оператор return и помещается в начале функции. В случае с факториалом это if (x == 0) return 1;.
И, кроме того, все рекурсивные вызовы должны обращаться к подфункциям, которые в конце концов сходятся к базовому варианту. Так, при передаче в функцию положительного числа при дальнейших рекурсивных вызовах подфункций в них будет передаваться каждый раз число, меньшее на единицу. И в конце концов мы дойдем до ситуации, когда число будет равно 0, и будет использован базовый вариант.
Другим распространенным показательным примером рекурсивной функции служит функция, вычисляющая числа Фиббоначчи. n-й член последовательности Фибоначчи определяется по формуле: f(n)=f(n-1) + f(n-2), причем f(0)=0, а f(1)=1. То есть последовательность Фибоначчи будет выглядеть так 0 (0-й член), 1 (1-й член), 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, .... Для определения чисел этой последовательности определим следующий метод:
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | static int Fibonachi(int n) { if (n == 0) { return 0; } else if (n == 1) { return 1; } else { return Fibonachi(n - 1) + Fibonachi(n - 2); } } |
Либо, если сократить первые две условные конструкции, так:
| 1 2 3 4 5 6 7 8 9 10 11 | static int Fibonachi(int n) { if (n == 0 || n == 1) { return n; } else { return Fibonachi(n - 1) + Fibonachi(n - 2); } } |
Это простейшие пример рекурсивных функций, которые призваны дать понимание работы рекурсии. В то же время для обоих функций вместо рекурсий можно использовать циклические конструкции. И, как правило, альтернативы на основе циклов работают быстрее и более эффективны, чем рекурсия. Например, вычисление чисел Фибоначчи с помощью циклов:
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | static int Fibonacci(int n) { int a = 0; int b = 1; int tmp; for (int i = 0; i { tmp = a; a = b; b += tmp; } return a; } |
В то же время в некоторых ситуациях рекурсия предоставляет элегантное решение, например, при обходе различных древовидных представлений, к примеру, дерева каталогов и файлов.
2 288
30 649 
