Рекурсия дар Java

Барои фаҳмидани он ки рекурсия чист, шумо бояд фаҳмед, ки рекурсия чист. Дарвоқеъ, дар фаҳмидани ин вазифаҳо ҳеҷ чизи душворе нест, шумо бояд онро танҳо як маротиба хуб дарк кунед. Ва вақте ки сухан дар бораи барномасозӣ меравад, машқ кунед. Рекурсия дар Java - 1

Рекурсия на танҳо дар барномасозӣ, балки дар ҳаёти воқеӣ низ рух медиҳад. Дар даст оина гиред ва дар назди оинаи дигар истед. Инъикоси тафаккур дар тафаккур ва ғ. Шумо шумораи беохири инъикосҳоро хоҳед дид, ки ба беохир меравад. Шумо метавонед бештар дар бораи рекурсияи "воқеӣ" дар мақолаи " Бахшида ба Рӯзи Groundhog... " Биёед, ки аз ҷаҳони воқеӣ ба ҳаёти ҳаррӯзаи барномасоз баргардем. Таърифи оддӣ: Функсияҳои рекурсивӣ дар java функсияҳое мебошанд, ки худро даъват мекунанд. Биёед ман ба шумо як мисоли хеле содда ва хеле зиёновар меорам:

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

Чаро зараровар аст? Ман тавсия медиҳам, ки шумо онро худатон тафтиш кунед! Агар шумо қарор диҳед, ки ба ин саёҳат машғул шавед (ва шумо эҳтимолан хоҳед, шумо барномасоз!), дар шарҳҳо нависед, ки JVM кадом хатогиро медиҳад =) Ин мисол ва бисёр чизҳои дигар нишон медиҳанд, ки ба истифодаи рекурсия дар Java бояд бодиққат муносибат кард. . Шумо бояд фаҳмед, ки дар куҷо, кай ва чаро чунин муносибат ба ҳалли мушкилот асоснок аст ва боварӣ ҳосил кунед, ки функсияи шумо иҷрои барномаро ба "Рӯзи заминӣ" табдил надиҳад. Ду таърифи муҳими дигар барои фаҳмидани рекурсия вуҷуд дорад:

Асоси рекурсивӣ - шарти баромадан аз блоки зангҳои рекурсивӣ - ҳалли асосии масъала, дар шароите, ки зарурати даъвати рекурсия вуҷуд надорад.
Қадами рекурсия вақтест, ки функсия ҳангоми тағир додани параметрҳо худашро даъват мекунад.

Мисоли классикии истифодаи функсияи рекурсивӣ ин ҳисобкунии факториали адад мебошад. Агар шумо фаромӯш карда бошед, ба шумо хотиррасон мекунам: факториали бутуни мусбат N(бо N нишон дода мешавад) ҳосor ададҳо аз 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;
}

Ҳоло ман рамзи усулро барои ҳалли рекурсивии ин мушкилот медиҳам:

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()функсияеро даъват мекунад 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