1. Рекурсивные функции, с точки зрения непрофессионала, означают, что функция сама вызывает себя...
Например: n!=n(n-1)!
Вы определяете функцию f(n)=nf(n-1)
И f(n-1) является функцией этого определения. . Это рекурсия
2. Зачем использовать рекурсию. Цель рекурсии — упростить разработку программы и облегчить ее чтение.
3. Недостатки рекурсии. Хотя нерекурсивные функции очень эффективны, их сложно программировать и они плохо читаются. Недостаток рекурсивных функций заключается в том, что они увеличивают нагрузку на систему. Другими словами, при каждой рекурсии стековая память занимает больше места.
4. Условия рекурсии: должен быть оператор для выполнения задачи, и должны быть соблюдены требования к рекурсии (уменьшать, а не расходиться).
5. Рекурсивное продвижение:
1. Используйте рекурсию для вычисления факториала n:
Анализ: n!=n*(n-1)*(n-2)...*1
public int dReturn (int n) { if (n == 1) { return 1 } else { return n*dReturn (n-1) };2. Используйте рекурсивную функцию для вычисления накопления от 1 до n: 1+2+3+4+..+n
public int dReturn (int n) { if (n == 1) { return 1 } else { return n+dReturn (n-1) }; 3. Требуется вывести последовательность: 1,1,2,3,5,8,11... (каждое число представляет собой сумму двух предыдущих чисел, и требуется рекурсивная функция)
Используйте рекурсию Java для представления функции: F(n)=F(n-1)+F(n-2);F(0)=1;F(1)=1;
Анализ: Х1=1; Х2=1; Х3=Х1+Х2;
public int F (int n) { if (n == 1) { return 1; } else if (n == 2) { return 1; } else { return F (n-1) + F (n-2); } }4. Java использует рекурсивный метод для обратной печати каждого элемента целочисленного массива.
public static void printAll(int index,int[] arr) { System.out.println(arr[index]); if(index > 0) { printAll(--index,arr } } public static void main(String); [] args) { int[] arr={1,2,3,4,5}; printAll(arr.lenth-1,arr);5. Программное решение: Если телка рожает корову каждый год, начиная с четвертого года после рождения, сколько коров будет на n-м году?
public static int скот(int n){ if(n<=0){ return 0; }else if(n<=3){ return 1; }else{ return скот(n-1)+cattle(n-3) ; } } public static void main(String[] args){ int n=10; System.out.println(n+"Всего будет "+крупный рогатый скот(n)+"коров" });Каковы понятия рекурсии, линейной рекурсии и хвостовой рекурсии?
Вызов рекурсивных функций в Java – поиск факториала числа
Переполнение не учитывается: обычно можно вычислить только факториал 69...
Примечание: факториал 0 равен 0! =1
Факториальное представление любого натурального числа n, большего 1:
n!=1×2×3×……×n
Или n!=n×(n-1)!
При поиске факториала 0 появится онлайн-калькулятор, что очень полезно! !
тест пакета; импорт java.util.Scanner; общедоступный класс DiGui {public static void main(String[] args) {// TODO Автоматически создаваемый метод stubSystem.out.println("Введите целое число:"); Scanner scan = new Scanner(System.in);int x = scan.nextInt();int result = digui(x);System.out.println(result);}//Рекурсивная функция public static int digui(int x){if(x) <=0){возврат 1;}else{возврат x*digui(x-1);}}}Рекурсия: процесс или функция имеет метод прямого или косвенного вызова самого себя в своем определении или описании. Обычно он преобразует большую и сложную проблему в меньшую проблему, аналогичную исходной задаче, которую нужно решить. Этот случай ясно иллюстрирует, как рекурсия может превратить сложную проблему в более мелкую, требующую решения. Ниже приведен небольшой пример, иллюстрирующий принцип рекурсии.
/*** @fileName Test.java* @description ??????????* @date 25.11.2012* @time 17:30* @author wst*/public class Test { static int Multiple( int n) { int Factorial; // ?? if ((n == 1) || (n == 0)) { Factorial = n; } else { Factorial = n * Multiple(n - 1); ; } public static void main(String[] args) { System.out.println(multiply(5)}); При вызове функции в стеке времени выполнения создается место для ее переменных. Переменные ранее вызванной функции остаются в стеке, но они скрыты переменными новой функции и поэтому недоступны.
Функция в программе имеет две переменные: параметр n и локальную переменную факториал. На следующих диаграммах показано состояние стека с доступными в данный момент переменными вверху. Все остальные вызываемые переменные затенены серым, чтобы указать, что к ним не может получить доступ выполняющаяся в данный момент функция.
Предположим, мы вызываем рекурсивную функцию со значением 5. Содержимое стека следующее: верхняя часть стека находится внизу:
n умножить(n) факториал 5 умножить(5) 5*умножить(4) //Первый вызов 4 умножить(4) 4*умножить(3) //Второй вызов 3 умножить(3) 3*умножить(2 ) // третий вызов 2 умножить(2) 2*умножить(1) //Четвертый вызов 1 умножить(1) 1 //Пятый вызов
Из приведенной выше информации легко увидеть, как рекурсия постепенно минимизирует проблему для ее решения. Начиная с вызова метода, результаты факториала будут помещаться в стек до тех пор, пока вызов метода не завершится, и, наконец, результаты возвращаются один за другим. с вершины стека. После замены поочередно результат следующий:
n=1 1 возвращает 1 вверх
n=2 2*multiply(1) возвращает 2*1=2 вверх
n=3 3*multiply(2) возвращает 3*(2*1)=6 вверх
n=4 4*multiply(3) возвращает 4*(3*(2*1))=24 вверх
n=5 5*multiply(4) возвращает вверх 5*(4*(3*(2*1)))=120
Примечание. Поскольку умножение(1) или умножение(0) возвращает значение 1.
Итак, есть 2*умножить(1)=2*1=2.
А поскольку умножение(2) соответствует условию рекурсии, после рекурсии его можно преобразовать в 2*умножить(1).
Итак, есть 3*умножить(2)=3*(2*умножить(1))=3*(2*1)=6.
Поскольку умножение(3) можно уменьшить до 3*умножить(2) после рекурсии.
Итак, умножить(4)=4*умножить(3)=4*(3*умножить(2))=4*(3*(2*1))=24
По аналогии, умножить(5)=5*умножить(4)
Его можно сократить до 5*(4*умножить(3))=5*(4*3*(умножить(2)))=5*(4*(3*(2*1)))=120
Давайте посмотрим на информацию о байт-коде:
public class Test расширяет java.lang.Object{ public Test(); Код: 0: aload_0 1: ignorespecial #1; //Метод java/lang/Object."<init>":()V 4: return static int умножить; (int); Код: 0: iload_0 1: iconst_1 // Помещаем константу типа int 1 в стек 2: if_icmpeq 9 // Сравниваем два значения типа int, если они равны, переходим на позицию 9, это || Короткое замыкание функция 5: iload_0 //Выполняется, когда первое условие не выполняется, загружая значение типа int из локальной переменной 0 (помещаем значение n в стек) 6: ifne 14 //Сравниваем, если нет Если равно 0 , переходим на позицию 14. Примечание. Поскольку сравнение по умолчанию здесь производится с 0, нет необходимости помещать константу 0 в стек 9: iload_0 //Если перехода в ifne нет, загрузите int из локальной переменной 0 Введите значение (помещаем значение n в стек) 10: istore_1 //Сохраняем значение типа int в локальную переменную 1 (значение, выскочившее из вершины стека, — это значение, помещенное в стек локальной переменной 0 и затем сохраненное в локальной переменной 1) 11: goto 23 //Безусловный переход на позицию 23 14: iload_0 //Сравнение в позиции 6, если она не равна 0, выполнить эту инструкцию, загрузить значение типа int из локальной переменной 0 (вставить значение n в стек) 15 : iload_0 //Загрузить значение типа int из локальной переменной 0 (поместить значение n в стек) 16: iconst_1 //Поместить константу типа int 1 в стек, константа 1 равна 1 из n -1 в коде 17: isub / /Выполняем операцию вычитания, n-1 18: ignorestatic #2; //Метод умножения:(I)I, вызываем метод умножения 21: imul //Выполняем операцию умножения, n * Multiple(n) - 1) 22: istore_1 //Будет ли значение типа int храниться в локальной переменной 1, Factorial=... 23: iload_1 //Загрузить значение типа int из локальной переменной 1 (поместить результат факториала в стек) 24 : ireturn //Метод возвращает public static void main( java.lang.String[]); Код: 0: getstatic #3; //Поле java/lang/System.out:Ljava/io/PrintStream 3: iconst_5 4; : ignorestatic #2; //Метод умножения:(I)I 7: ignorevirtual #4; //Метод java/io/PrintStream.println:(I)V 10: return }