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

Рекурсия эмне экенин түшүнүү үчүн, рекурсия эмне экенин түшүнүү керек. Чынында, мындай функцияларды түшүнүүдө эч кандай кыйынчылык жок, бир гана жолу жакшы түшүнүшүңүз керек. Ал эми программалоого келгенде машыгыңыз. Java тorндеги рекурсия - 1

Рекурсия программалоодо гана эмес, реалдуу жашоодо да кездешет. Колуңузга күзгү алып, башка күзгүнүн алдында туруңуз. Ойлонуунун чагылдырылышы ой ж.б.у.с.да чагылдырылат. Сиз чексиз сандагы ой жүгүртүүлөрдүн чексиздигин көрөсүз. “Чыныгы” рекурсия тууралуу кененирээк “ Groundhog күнүнө арналган... ” деген макаладан таба аласыз. Келгиле, реалдуу дүйнөдөн программисттин күнүмдүк жашоосуна кайрылып көрөлү. Жөнөкөй аныктама: Javaдагы рекурсивдүү функциялар өздөрүн чакырган функциялар. Мен сизге абдан жөнөкөй жана өтө зыяндуу бир мисал келтирейин:

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

Эмне үчүн зыяндуу? Мен аны өзүңүз текшерүүнү сунуштайм! Эгер сиз бул укмуштуу окуяга катышууну чечсеңиз (жана сиз, балким, сиз программист!), комментарийге JVM кандай ката кетирерин жазыңыз =) Бул жана башка көптөгөн мисалдар Java'да рекурсияны колдонууга туура мамиле кылуу керектигин көрсөтүп турат. сак. Маселени чечүүнүн мындай мамилеси кайда, качан жана эмне үчүн негиздүү экенин түшүнүп, сиздин функцияңыз программанын аткарылышын "Гаундхог күнүнө" айлантпай турганына ынанышыңыз керек. Рекурсияны түшүнүү үчүн дагы эки маанилүү аныктама бар:

Рекурсиялык негиз – рекурсивдүү чалуулар блогунан чыгуу шарты – рекурсияны чакыруунун зарылчылыгы жок шарттарда маселенин негизги чечими.
Рекурсия кадамы - бул функция параметрлерди өзгөртүүдө өзүн чакырганда.

Рекурсивдүү функцияны колдонуунун классикалык мисалы сандын факториалын эсептөө болуп саналат. Эгер унутуп калган болсоңуз, эсиңизге сала кетейин: оң бүтүн сандын факториалы N(N катары белгиленет!) -тен келген сандардын көбөйтүлүшү 1 до N: N! = 1 * 2 * 3 * … (N - 1) * N. Айтмакчы, аныктамасы боюнча нөлдүн факториалы 1ге барабар. Демек, факториалды каалаган оң бүтүн жана нөл үчүн табууга болот (математика тorнде – терс эмес бүтүн сандардын жыйындысы үчүн же натурал сандардын жана нөл). Менин оюмча, сиз циклдерди колдонуп фактордук программалоо мүмкүн экенин түшүнөсүз. Чынында, бул көйгөйдү чечүү үчүн рекурсивдүү эмес ыкмасы болуп саналат:

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) рекурсивдүү түрдө да чечorши мүмкүн. Рекурсиянын артыкчылыгы - окууга ыңгайлуу жана жазуу оңой, биз жогоруда кемчorктери жөнүндө айттык: "өзүңүздү бутуңузга атуу" мүмкүнчүлүгү иллюзия эмес. "Татаал рекурсия" деп аталган нерсени колдонууда дагы этият болушуңуз керек: Функция функцияны чакырган 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