Rekursi ing Jawa

Kanggo mangerteni apa rekursi, sampeyan kudu ngerti apa rekursi. Nyatane, ora ana sing angel kanggo ngerti fungsi kasebut, sampeyan mung kudu ngerti kanthi bener. Lan praktek nalika nerangake program. Rekursi ing basa Jawa - 1

Rekursi dumadi ora mung ing program, nanging uga ing urip nyata. Njupuk pangilon ing tangan lan ngadeg ing ngarepe pangilon liyane. Refleksi refleksi bakal kagambar ing refleksi lan liya-liyane. Sampeyan bakal weruh nomer tanpa wates saka bayangan menyang tanpa wates. Sampeyan bisa nemokake luwih akeh babagan rekursi "nyata" ing artikel " Darmabakti kanggo Groundhog Day ... " Ayo bali saka jagad nyata menyang urip saben dinane programmer. Dhéfinisi prasaja: Fungsi rekursif ing basa Jawa yaiku fungsi sing ngarani dhéwé. Ayo kula menehi conto sing prasaja lan mbebayani banget:

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

Apa sebabe mbebayani? Aku saranake sampeyan mriksa dhewe! Yen sampeyan arep kanggo njupuk petualangan iki (lan sampeyan paling kamungkinan bakal, sampeyan programmer!), Tulis ing komentar apa kesalahan JVM bakal uncalan =) Conto iki, lan akeh liyane, nduduhake sing nggunakake recursion ing Jawa kudu nyedhaki kanthi teliti. . Sampeyan kudu ngerti ing ngendi, kapan lan ngapa pendekatan kasebut kanggo ngrampungake masalah kasebut bener, lan priksa manawa fungsi sampeyan ora ngowahi eksekusi program kasebut dadi "Groundhog Day". Ana rong definisi sing luwih penting kanggo mangerteni rekursi:

Basis rekursi - kondisi kanggo metu saka blok panggilan rekursif - solusi dhasar kanggo masalah kasebut, ing kahanan nalika ora perlu nelpon rekursi.
Langkah rekursi yaiku nalika fungsi nelpon dhewe nalika ngganti paramèter.

Conto klasik nggunakake fungsi rekursif yaiku ngitung faktorial saka nomer. Yen sampeyan kelalen, mugi kula ngelingake sampeyan: faktorial saka integer positif N(dituduhake minangka N!) Iku produk saka nomer saka 1 до N: N! = 1 * 2 * 3 * … (N - 1) * N. Miturut cara, faktorial saka nol kanthi definisi padha karo 1. Dadi faktorial bisa ditemokake kanggo sembarang integer positif lan nol (ing basa matématika - kanggo himpunan bilangan bulat non-negatif utawa kanggo himpunan nomer alam lan nul). Aku sampeyan ngerti yen sampeyan bisa program faktorial nggunakake puteran. Bener, iki cara non-rekursif kanggo ngrampungake masalah iki:

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

Ayo nambah mriksa sing nomer positif lan integer, lan mriksa kapisah kanggo nul.

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;
}

Saiki aku bakal menehi kode metode kanggo ngrampungake masalah iki kanthi rekursif:

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

Ayo katon ing asil output kanggo telpon:

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));

Kita entuk nilai sing dikarepake:

Ayo nambah output sing apik lan ngitung faktorial kanggo nomer sing luwih gedhe:

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) + "!");

We njaluk: 15 * 14 * 13 * 12 * 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 1 307 674 368 000! Ing kasus iki, nggunakake fungsi rekursif sabdho lan aman. Kita wis nemtokake kanthi jelas kondisi kanggo metu saka blok rekursif, lan kita yakin manawa bisa ditindakake: kita ngetik nomer integer non-negatif, yen nomer padha karo nol utawa siji, kita bali asil, yen nomer luwih. , kita multiply asil karo fungsi nomer n-1. Nggunakake faktorial saka telung minangka conto:

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

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

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

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

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

Babagan ati-ati sing digunakake: apa kerentanan fungsi iki? Yen sampeyan menehi cara nomer negatif minangka parameter, banjur mriksa

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

ndadekake ora pangertèn lan kita bakal mungkasi munggah ing siklus telas nelpon dhéwé. Iku worth nambah mriksa kanggo non-negatif:

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

Lan kabeh bakal apik.

Apa kauntungan saka siji cara tinimbang liyane? Ora koyone ana prabédan amba, nanging nyatane, akeh telpon rekursif bakal duwe impact negatif ing kinerja lan konsumsi memori: tumpukan telpon minangka sumber sing meh ora bisa dikendhaleni lan ing kahanan sing beda kanggo nelpon fungsi rekursif padha. kita bisa utawa ora nemu masalah gadhah sumber iki. Meh kabeh masalah sing ditanggulangi nggunakake iterasi (siklus kaya for-each) uga bisa ditanggulangi kanthi rekursif. Kauntungan saka rekursi yaiku maca lan gampang nulis, kita ngomong babagan kekurangan ing ndhuwur: kesempatan kanggo "nembak dhewe ing sikil" ora khayalan. Sampeyan kudu malah luwih ati-ati nalika nggunakake disebut "rekursi Komplek": A fungsi A()bakal nelpon fungsi B()sing nelpon fungsi A().. Ngatasi masalah kuwi mbutuhake pangerten lengkap carane recursion dianggo. Conto tugas kasebut: ngitung nilai x^n/(n!). Faktorial, kaya sing wis kita rembugan ing ndhuwur, ditetepake ing set integer non-negatif. Pungkasan, aku bakal menehi kode solusi. Rekursi kompleks bakal kalebu rong cara:

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);
}

Kanggo nglebokake rekursi, cara digunakake calculate, sing diarani metode power, sing banjur diarani metode calculate. Kita nemtokake basis rekursi ing metode daya:

if (n == 1) return x;

Langkah rekursi uga ditetepake ing kono:

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

Iku tetep kanggo nambah mriksa kanggo validitas data input:

Sembarang nomer liyane saka nol padha karo daya nol 1. Yen n = 0, banjur n! = 1. Perlu bali 1.
Zero kanggo sembarang daya padha karo nul.
Kita ora bakal nimbang kahanan sing durung mesthi jinis 0^0lan bakal nampa data input kasebut minangka ora sah.

Kanthi kabeh mriksa, cara bakal katon kaya iki:

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);
}

Inggih, nalika nelpon fungsi sampeyan kudu elinga kanggo nyekel kesalahan:

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

Komentar

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