Java-da rekursiya

Rekursiyanın nə olduğunu başa düşmək üçün rekursiyanın nə olduğunu anlamaq lazımdır. Əslində, bu cür funksiyaları başa düşməkdə çətin bir şey yoxdur, yalnız bir dəfə yaxşı başa düşmək lazımdır. Proqramlaşdırmaya gəldikdə isə məşq edin. Java-da rekursiya - 1

Rekursiya təkcə proqramlaşdırmada deyil, real həyatda da baş verir. Əllərinizə bir güzgü götürün və başqa bir güzgünün qarşısında dayanın. Yansımanın əksi əksini əks etdirəcək və s. Sonsuzluğa gedən sonsuz sayda əksləri görəcəksiniz. “Həqiqi” rekursiya haqqında daha çox məlumatı “ Groundhog Gününə həsr olunmuş... ” məqaləsində tapa bilərsiniz. Gəlin real dünyadan proqramçının gündəlik həyatına qayıdaq. Sadə tərif: Java-da rekursiv funksiyalar özlərini çağıran funksiyalardır. Sizə çox sadə və çox zərərli bir misal verim:

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

Niyə zərərlidir? Bunu özünüz yoxlamağı təklif edirəm! Bu macəra ilə məşğul olmaq qərarına gəlsəniz (və çox güman ki, olacaqsınız, proqramçı!), şərhlərdə JVM-nin hansı səhvi atacağını yazın =) Bu və bir çox başqa nümunələr Java-da rekursiyadan istifadəyə diqqətlə yanaşmaq lazım olduğunu nümayiş etdirir. . Problemin həllinə bu cür yanaşmanın harada, nə vaxt və nə üçün əsaslandırıldığını başa düşməli və funksiyanızın proqramın icrasını “Groundhog Day”ə çevirmədiyinə əmin olmalısınız. Rekursiyanı başa düşmək üçün daha iki vacib tərif var:

Rekursiya əsası - rekursiv çağırışlar blokundan çıxmaq şərti - rekursiya çağırmağa ehtiyac olmadığı şəraitdə problemin əsas həlli.
Rekursiya addımı parametrləri dəyişdirərkən funksiyanın özünü çağırmasıdır.

Rekursiv funksiyadan istifadənin klassik nümunəsi ədədin faktorialının hesablanmasıdır. Əgər unutmusunuzsa, sizə xatırlatmağa icazə verin: müsbət tam ədədin faktorialı N(N kimi qeyd olunur!) -dən gələn ədədlərin hasilidir 1 до N: N! = 1 * 2 * 3 * … (N - 1) * N. Yeri gəlmişkən, sıfırın faktorialı tərifinə görə 1-ə bərabərdir. Beləliklə, faktorialı istənilən müsbət tam və sıfır üçün tapmaq olar (riyaziyyatın dilində - mənfi olmayan tam ədədlər çoxluğu və ya natural ədədlər çoxluğu üçün və sıfır). Düşünürəm ki, siz looplardan istifadə edərək faktorial proqramlaşdıra biləcəyinizi başa düşürsünüz. Əslində, bu problemi həll etmək üçün rekursiv olmayan bir üsul var:

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

Ədədin müsbət və tam olduğunu təsdiq edən bir çek və sıfır üçün ayrıca bir yoxlama əlavə edək.

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

İndi bu problemin rekursiv həlli üçün metod kodunu verəcəyəm:

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

Zənglər üçün çıxış nəticələrinə baxaq:

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

Gözlənilən dəyərləri alırıq:

Gəlin gözəl bir nəticə əlavə edək və daha böyük rəqəm üçün faktorial hesablayaq:

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

Alırıq: 15 * 14 * 13 * 12 * 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 1 307 674 368 000! Bu halda rekursiv funksiyanın istifadəsi əsaslandırılmış və təhlükəsizdir. Biz rekursiv blokdan çıxmaq şərtini aydın şəkildə müəyyən etmişik və bunun əldə oluna biləcəyinə əminik: mənfi olmayan tam ədədi daxil edirik, əgər ədəd sıfıra və ya birə bərabərdirsə, nəticəni qaytarırıq, əgər ədəd daha böyükdürsə. , nəticəni ədədin funksiyasına vururuq n-1. Nümunə olaraq üçünün faktorialından istifadə:

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

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

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

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

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

İstifadə ehtiyatına gəlincə: bu funksiyanın zəifliyi nədir? Bir metoda parametr kimi mənfi bir rəqəm verirsinizsə, onda çek

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

heç bir məna kəsb etmir və biz özümüzü çağırmağın sonsuz dövrünə girəcəyik. Mənfi olmamaq üçün bir çek əlavə etməyə dəyər:

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

Və hər şey yaxşı olacaq.

Bir metodun digərindən üstünlüyü nədir? Görünür, elə də böyük fərq yoxdur, amma əslində çoxlu rekursiv zənglər performansa və yaddaş istehlakına mənfi təsir göstərəcək: zəng yığını demək olar ki, idarəolunmaz resursdur və eyni rekursiv funksiyanı çağırmaq üçün müxtəlif şərtlər altında, biz bu resursla bağlı problemlərlə üzləşə bilərik və ya olmaya bilərik. İterasiyalardan istifadə etməklə həll edilən demək olar ki, bütün problemlər (kimi dövrələr for-each) rekursiv şəkildə də həll edilə bilər. Rekursiyanın üstünlüyü oxunaqlılıq və yazmaq asanlığıdır, yuxarıda çatışmazlıqlar haqqında danışdıq: "özünüzü ayağınıza vurmaq" imkanı illüziya deyil. Siz “mürəkkəb rekursiya” adlanandan istifadə edərkən daha diqqətli olmalısınız: Funksiya funksiyanı çağıran A()funksiyanı çağıracaq.Belə məsələlərin həlli rekursiyanın necə işlədiyini tam başa düşməyi tələb edir. Belə bir tapşırığın nümunəsi: dəyərinin hesablanması . Faktorial, yuxarıda müzakirə etdiyimiz kimi, mənfi olmayan tam ədədlər çoxluğunda müəyyən edilir. Nəhayət, həll kodunu verəcəyəm. Kompleks rekursiya iki üsuldan ibarət olacaq: 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);
}

Rekursiyaya daxil olmaq üçün metoddan istifadə olunur calculateki, o da metodu çağırır power, o da öz növbəsində metodu çağırır calculate. Güc metodunda rekursiya əsasını təyin etdik:

if (n == 1) return x;

Rekursiya addımı da orada müəyyən edilir:

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

Giriş məlumatlarının etibarlılığı üçün bir çek əlavə etmək qalır:

Sıfırdan başqa istənilən ədəd sıfırın gücünə bərabərdir 1. Əgər n = 0, onda n! = 1. Geri qaytarmaq lazımdır 1.
Sıfırdan istənilən güc sıfıra bərabərdir.
Biz növün qeyri-müəyyənliyini nəzərə almayacağıq 0^0və bu cür giriş məlumatlarını etibarsız kimi qəbul edəcəyik.

Bütün yoxlamalarla üsullar belə görünəcək:

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

Yaxşı, bir funksiyaya zəng edərkən xətanı tutmağı unutmayın:

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

Şərhlər

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