Java тіліндегі рекурсия

Рекурсияның не екенін түсіну үшін рекурсияның не екенін түсіну керек. Шын мәнінде, мұндай функцияларды түсінуде қиын ештеңе жоқ, оны тек бір рет жақсы түсіну керек. Ал бағдарламалауға келгенде тәжірибе жасаңыз. Java тіліндегі рекурсия – 1

Рекурсия тек бағдарламалауда ғана емес, өмірде де кездеседі. Қолыңызға айна алып, басқа айнаның алдында тұрыңыз. Рефлексияның көрінісі рефлексияда және т.б. Сіз шексіздікке түсетін шағылысулардың шексіз санын көресіз. «Нақты» рекурсия туралы толығырақ « Groundhog Day күніне арналған... » мақаласынан таба аласыз, нақты әлемнен бағдарламашының күнделікті өміріне оралайық. Қарапайым анықтама: java-дағы рекурсивті функциялар - өздерін шақыратын функциялар. Сізге өте қарапайым және өте зиянды мысал келтірейін:

public void recursionFucn() {
    System.out.println("Привет, JavaRush!");
    recursionFucn();
}

Неліктен зиянды? Мен оны өзіңіз тексеруге ұсынамын! Егер сіз осы шытырман оқиғаға баруды шешсеңіз (және сіз жасайсыз, бағдарламашы!), JVM қандай қате жіберетінін түсініктемелерде жазыңыз =) Бұл және басқа да мысалдар Java-да рекурсияны қолдануды қалай қарастыру керектігін көрсетеді. сақтық. Мәселені шешуге мұндай көзқарас қай жерде, қашан және неге негізделгенін түсінуіңіз керек және сіздің функцияңыз бағдарламаның орындалуын «Groundhog Day» күніне айналдырмайтынына көз жеткізіңіз. Рекурсияны түсіну үшін тағы екі маңызды анықтама бар:

Рекурсиялық базис – рекурсивті шақырулар блогынан шығу шарты – рекурсияны шақырудың қажеті жоқ жағдайларда есептің негізгі шешімі.
Рекурсия қадамы - бұл функция параметрлерді өзгерту кезінде өзін шақыратын кезде.

Рекурсивті функцияны пайдаланудың классикалық мысалы санның факториалын есептеу болып табылады. Егер сіз ұмытып қалсаңыз, еске сала кетейін: натурал санның факториалы N(N деп белгіленеді!) -ден алынған сандардың көбейтіндісі 1 до N: N! = 1 * 2 * 3 * … (N - 1) * N. Айтпақшы, нөлдің факториалы анықтамасы бойынша 1-ге тең. Сонымен факториалды кез келген оң бүтін және нөл үшін табуға болады (математика тілінде – теріс емес бүтін сандар жиыны үшін немесе натурал сандар жиыны үшін және нөл). Менің ойымша, сіз циклдар арқылы факториалды бағдарламалай алатыныңызды түсінесіз. Шын мәнінде, бұл мәселені шешудің рекурсивті емес әдісі:

private int fact(int n) {
    int result = 1;
    for (int i = 1; i <= n; i++) {
        result = result * i;
    }
    return result;
}

Санның оң және бүтін екенін тексеруді және нөлге бөлек тексеруді қосамыз.

private int fact(int n) {
    if (n < 0) {
        System.out.println("Зачем тебе факториал из отрицательного числа?");
         return null;
    }
    int result = 1;
    if (n == 0) {
        return result;
    }
    for (int i = 1; i <= n; i++) {
        result = result * i;
    }
    return result;
}

Енді мен бұл мәселені рекурсивті шешуге арналған әдіс codeын беремін:

private int factorial(int n) {
    int result = 1;
    if (n == 1 || n == 0) {
        return result;
    }
    result = n * factorial(n-1);
    return result;
}

Қоңыраулар үшін нәтижелерді қарастырайық:

System.out.println(factorial(0));
System.out.println(factorial(1));
System.out.println(factorial(2));
System.out.println(factorial(3));
System.out.println(factorial(4));
System.out.println(factorial(5));
System.out.println(factorial(6));

Біз күтілетін мәндерді аламыз:

Жақсы нәтиже қосып, үлкенірек сан үшін факториалды есептейік:

private int factorial(int n) {
    int result = 1;

    if (n == 0) {
        System.out.print(" = ");
        return result;
    }
    if (n == 1) {
        System.out.print(" * 1 = ");
        return result;
    }

    System.out.print(n);
    if (n != 2) {
        System.out.print(" * ");
    }

    result = n * factorial(n-1);
    return result;
}


System.out.println(factorial(15) + "!");

Біз аламыз: 15 * 14 * 13 * 12 * 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 1 307 674 368 000! Бұл жағдайда рекурсивті функцияны пайдалану негізделген және қауіпсіз. Біз рекурсивті блоктан шығу шартын нақты анықтадық және оған қол жеткізуге болатынына сенімдіміз: теріс емес бүтін санды енгіземіз, егер сан нөлге немесе біреуге тең болса, нәтижені қайтарамыз, егер сан үлкен болса , нәтижені санның функциясына көбейтеміз n-1. Мысал ретінде үш факториалды қолдану:

factorial(3) внутри себя выполнит следующее:
	result = 3 * factorial(2); (рекурсивный вызов)

	factorial(2) внутри себя выполнит следующее:
		result = 2 * factorial(1); (рекурсивный вызов)

		factorial(1) вернет 1 (базис рекурсии)

	factorial(2) вернет 2 * 1

factorial(3) вернет 3 * 2 * 1

Пайдаланудағы сақтыққа қатысты: бұл функцияның осалдығы қандай? Егер әдіске параметр ретінде теріс сан берсеңіз, онда тексеру

if (n == 1 || n == 0) {
    return result;
}

мағынасы жоқ және біз өзімізді шақырудың шексіз цикліне тап боламыз. Теріс емес тексеруді қосқан жөн:

if (n < 0) {
	System.out.println(«Зачем тебе факториал отрицательного числа?»);
	return null;
}

Және бәрі жақсы болады.

Бір әдістің екіншісінен артықшылығы неде? Бұл үлкен айырмашылық жоқ сияқты, бірақ іс жүзінде көптеген рекурсивті қоңыраулар өнімділік пен жадты тұтынуға теріс әсер етеді: қоңыраулар стегі дерлік басқарылмайтын ресурс болып табылады және бірдей рекурсивті функцияны шақыру үшін әртүрлі жағдайларда, біз осы ресурспен байланысты мәселелерге тап болуымыз немесе болмауымыз мүмкін. Итерациялар арқылы шешілетін барлық дерлік есептерді (мысалы, циклдар for-each) рекурсивті түрде шешуге болады. Рекурсияның артықшылығы - оқылу және жазудың қарапайымдылығы, біз жоғарыда кемшіліктер туралы айттық: «аяққа ату» мүмкіндігі иллюзия емес. «Күрделі рекурсия» деп аталатынды пайдаланған кезде одан да мұқият болу керек: Функция функцияны шақыратын A()функцияны шақырады.Мұндай есептерді шешу рекурсияның қалай жұмыс істейтінін толық түсінуді талап етеді. Мұндай тапсырманың мысалы: мәнін есептеу . Факториал, жоғарыда қарастырғанымыздай, теріс емес бүтін сандар жиынында анықталады. Соңында мен шешім codeын беремін. Күрделі рекурсия екі әдістен тұрады: B()A()x^n/(n!)

private double calculate(int x, int n) {
    return power(x, n) / n;
}
private double power(int x, int n) {
    if (n == 1) return x;
    return x * calculate(x, n - 1);
}

calculateРекурсияны енгізу үшін әдісті шақыратын әдіс пайдаланылады , powerол әдісті шақырады calculate. Қуат әдісінде рекурсия негізін анықтадық:

if (n == 1) return x;

Рекурсия қадамы да сонда анықталады:

return x * calculate(x, n - 1);

Енгізілген деректердің дұрыстығын тексеруді қосу қалады:

Нөлден басқа кез келген сан нөлдің дәрежесіне тең 1. Егер n = 0, онда n! = 1. Қайтару керек 1.
Кез келген дәрежедегі нөл нөлге тең.
Біз түрдегі белгісіздікті қарастырмаймыз 0^0және мұндай кіріс деректерін жарамсыз деп қабылдаймыз.

Барлық тексерулермен әдістер келесідей болады:

private double calculate(int x, int n) throws ArithmeticException {
    if (x == 0 && n == 0) {
        throw new ArithmeticException("Невалидные входные данные: Неопределенность типа 0^0");
    }

    if (n < 0) {
        throw new ArithmeticException("Невалидные входные данные: Факториал из отрицательного числа!");
    }

    if (n == 0) {
        return 1;
    }

    if (x == 0) {
        return 0;
    }

    if (x == 0) {
        return 0;
    }
    return power(x, n) / n;
}

private double power(int x, int n) {
    if (n == 1) return x;
    return x * calculate(x, n - 1);
}

Функцияны шақырған кезде қатені ұстауды есте сақтау керек:

try {
    System.out.println(calculate(x, n));
} catch (ArithmeticException e) {
    System.out.println(e.getMessage());
}

Пікірлер

TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION