Отдельно рассмотрим рекурсивные функции. Главное отличие рекурсивных функций от обычных состоит в том, что они рекурсивная функция может вызывать саму себя.
Например, рассмотрим функцию, определяющую факториал числа:
1 2 3 4 5 6 7 8 |
static int factorial(int x){ if (x == 1){ return 1; } else{ return x * factorial(x - 1); } } |
Вначале проверяется условие: если вводимое число не равно 1, то мы умножаем данное число на результат этой же функции, в которую в качестве параметра передается число x-1. То есть происходит рекурсивный спуск. И так дальше, пока не дойдем того момента, когда значение параметра не будет равно единице.
Хотя в данном случае нужно отметить, что для определения факториала есть более оптимальные решения на основе циклов:
1 2 3 4 5 6 7 8 |
static int factorial(int x){ int result=1; for (int i = 1; i <= x; i++) { result *= i; } return result; } |
Еще одним распространенным примером рекурсивной функции служит функция, вычисляющая числа Фибоначчи. В теории n-й член последовательности Фибоначчи определяется по формуле: f(n)=f(n-1) + f(n-2), причем f(0)=0, а f(1)=1
1 2 3 4 5 6 7 8 9 10 11 |
static int fibonachi(int n){ if (n == 0){ return 0; } if (n == 1){ return 1; } else{ return fibonachi(n - 1) + fibonachi(n - 2); } } |