В этой статье мы поговорим о методе рекурсии. Большинство программ используют методы, которые вызываются другие методы последовательно, но иногда для решения некоторых поставленных задач требуется методы, которые могут вызывать сами себя. Рекурсивный метод-это метод, который вызывает сам себя напрямую либо косвенно через другой метод. Для четкого понимания рекурсии, разберем такую задачу, вычислить факториал числа n! введенный пользователем. Для начала что такое факториал числа n!, факториал –это произведения всех чисел от одного до числа n!. Пример 6!=1*2*3*4*5*6=720 в нашем случаи факториал числа 6! равен 720.
Теперь напишем листинг 1.1 нахождения факториала итерационным методом.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
package factorial; /** * @author nookery.ru */ public class Factorial { public static void main(String[] args) { int n=6; int factorial=1; for (int i = n; i >=1; i--) { factorial*=i; } System.out.println("factorial="+factorial); } } |
листинг 1.1
Результатом работы такой программы будет factorial=720;
Теперь давайте попробуем вычислить факториал рекурсивным методом. Составим небольшую табличку позволяющую наглядно видеть что будет делать наш будущий метод вычисления факториала.
| !6 | = | !5 | * | 6 |
| !5 | = | !4 | * | 5 |
| !4 | = | !3 | * | 4 |
| !3 | = | !2 | * | 3 |
| !2 | = | !1 | * | 2 |
| !0 | = | 1 |
таблица 1.1
Как видно в таблице 1.1 факториал числа !6 равен факториалу числа !5 умноженного на 6. А факториал числа !5 равен факториалу !4 умноженного на 5 и так далее. Теперь мы имеем четкие представления о том как написать метод вычисления факториала, смотрим что у нас получилось листинг 1.2
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
package factorial; /** * @author nookery.ru */ public class Factorial { //создали метод факториала public int factorial(int n){ int itog;//переменная результата //если факториал числа 1 то и равен он будет 1 if(n==1)return 1; //тут мы делаем рекурсию метода factorial itog=factorial(n-1)*n; //возвращаем результат return itog; } public static void main(String[] args) { Factorial fact=new Factorial(); System.out.println(fact.factorial(6)); } } |
листинг 1.2
В комментариях листинга 1.2 я описал довольно все подробно, но давайся разберем все еще раз. В методе main мы создали экземпляр класса и вызывали его метод factorial() с параметром числа 6. Внутри метода происходит сравнение числа n c 1, потому что мы уже знаем из таблицы что если число факториала 1 равна 1. Если сравнение истина то соответственно возвращаемым числом будет 1. Но в нашем случаи это число 6, поэтому вызывается метод factorial(), внутри метода factorial(). В котором происходят вычисления, а точнее происходят все те операции что были в таблице 1.1. в методе происходит запуск под метода до тех пор, пока число факториал 6 не станет факториалом 1, будет происходить своего рода цикл, а вот благодаря строке if(n==1)return 1; происходит завершения метода, иначе было бы зацикливание программы. Рекурсивный метод используется для создания простых реализаций алгоритмов, к примеру в алгоритме быстрой сортировки.
Написал программу для вычисления факториала что бы вы могли проверить свои знания полученные из статьи. Особенностью программы является то что она вычисляет большие числа, по сравнению с онлайн калькуляторами. Единственный минус при вычислении больших чисел факториала программой, вычисление может занять длительное время, это зависит от вашего процессора.
Требования: OS Windows XP\Vista\7\8\; OS Mac; OS Linux;
Язык интерфейса: русский
Фаил: factorial.jar
рис. 1
Скачать: программа факториал.
Используется итеративное определение факториала. Циклическая часть практически идентична примеру числами Фибоначчи , тело отличается, но незначительно. Отметим использование для переменных факториала и числа префикса