Co to jest funkcja rekurencyjna i jak ją utworzyć w Javie?

Nigdy nie można lekceważyć potrzeby powtarzania kodu w poszukiwaniu rozwiązań niektórych z największych problemów świata. Musisz wiedzieć, że w programowaniu powtarzanie przybiera jedną z dwóch form - iteracji lub rekurencji.

Celem jest wprowadzenie powtórzeń w kodzie i zademonstrowanie, jak można je wykorzystać do ulepszenia programów Java.

Powtarzające się programy mogą pomóc rozwiązać niektóre z najtrudniejszych problemów programistycznych. Oto, co musisz wiedzieć, aby tworzyć programy rekurencyjne w języku Java.

Korzystanie z iteracji

Iteracja wykorzystuje strukturę pętli do powtarzania kodu. Trzy typy struktur iteracyjnych to pętla przed testem (podczas), pętla po teście (do-podczas) i pętla sterowana licznikiem (dla).

Te iteracyjne struktury działają poprzez powtarzanie bloku kodu, podczas gdy określony warunek pozostaje prawda, ale gdy tylko warunek stanie się fałszywy, pętla zostanie zatrzymana, a program wróci do swojego normalnego stanu pływ.

Na przykład, możemy zastosować jedną ze struktur iteracyjnych, aby rozwiązać problem sumy wszystkich liczb całkowitych od 1 do n. W zależności od zastosowanej struktury iteracyjnej rozwiązanie przybierze określoną formę, ale dowolną trzy struktury iteracyjne mogą zapewnić rozwiązanie tego problemu, wykorzystując następujące elementy pseudo kod.

Przykład pseudokodu iteracyjnego

POCZĄTEK
DECLEARE suma, licz jako liczbę całkowitą
suma = 0
liczba = 1
POWTARZAĆ
Suma = suma + liczba
Liczba = liczba + 1
DO zliczenia> n
KONIEC

Powyższy pseudokod zawiera dwie zmienne, sumę i licznik, które są inicjalizowane odpowiednio na 0 i 1. Zmienna „count” jest inicjalizowana na 1, ponieważ problem, który próbujemy rozwiązać, mówi, że potrzebujemy sumy wszystkich liczb całkowitych od 1 do n.

Zmiennej „n” zostanie przypisana losowa liczba od użytkownika, a zmienna „count” zwiększy się o jeden w czasie wykonywania pętli, ale gdy tylko wartość zmiennej „count” przekroczy wartość „n”, pętla zatrzymać.

Dlaczego warto korzystać z rekursji?

Gdybyśmy mieli zbadać fakty dotyczące iteracji i rekurencji, stwierdzilibyśmy, że kilka rzeczy jest prawdziwych.

• Obie metody wymagają powtórzeń.
• Obie metody wymagają warunku testu, który wskaże, kiedy przestać.
• Obie metody mogą teoretycznie działać w nieskończoność, jeśli warunek zakończenia nie zostanie podany lub nie zostanie spełniony.
• Każdy problem, który można rozwiązać za pomocą iteracji, można również rozwiązać za pomocą rekursji i odwrotnie.

Dlaczego więc mielibyśmy wybierać jedną metodę zamiast drugiej? Prosta odpowiedź brzmi: wydajność. W przypadku rekurencji programista może użyć mniej kodu, aby osiągnąć zasadniczo ten sam wynik. Mniej kodu oznacza, że ​​istnieje znaczny spadek możliwości niezauważenia błędów.

Rekurencja zużywa więcej pamięci i jest wolniejsza niż iteracja, ale ma wbudowany stos (strukturę danych). W przypadku iteracji musiałbyś zbudować strukturę danych (zasadniczo wymyślając na nowo koło), pozostawiając program otwarty na większe prawdopodobieństwo niezłapanych błędów z powodu dodatkowego kodu.

Związane z: Wyjątki w Javie: czy dobrze sobie z nimi radzisz?

Jak działa rekursja

Rekursja to nazwa nadana procesowi, w którym funkcja wielokrotnie wywołuje samą siebie, dopóki nie zostanie spełniony określony warunek. Ta powtarzalna metoda rozwiązuje problemy, dzieląc je na mniejsze, prostsze wersje samych siebie.

Każda funkcja rekurencyjna składa się z dwóch części - przypadku podstawowego i przypadku ogólnego.

Podstawowa struktura przykładu funkcji rekurencyjnej

Funkcjonować(){
// podstawa
// przypadek ogólny
}

Przypadek podstawowy to sekcja funkcji rekurencyjnej, która rozwiązuje problem. Tak więc, ilekroć funkcja rekurencyjna dociera do przypadku podstawowego, program wychodzi z funkcji rekurencyjnej i kontynuuje swój naturalny przepływ.

Ogólny przypadek to sekcja funkcji rekurencyjnej, która jest powtarzalna. Tutaj funkcja wywołuje samą siebie i wykonuje większość pracy.

Korzystanie z rekursji w Javie

Niektóre języki programowania obsługują tylko iterację, podczas gdy inne obsługują tylko rekurencję. Na szczęście Java jest jednym z języków obsługujących obie powtarzalne metody.

W Javie rekurencja jest używana w taki sam sposób, jak w każdym innym języku, który ją obsługuje. Najważniejsze jest, aby zawsze upewnić się, że funkcja rekurencyjna ma zarówno przypadek podstawowy, jak i ogólny, w tej kolejności.

Wróćmy do naszego początkowego przykładu podsumowania, celem jest znalezienie sumy wszystkich liczb całkowitych od 1 do n, gdzie n jest liczbą całkowitą podaną przez użytkownika.

Przykład rekurencji w języku Java

// funkcja rekurencyjna
int Sum (int n) { 
// podstawa
if (n <= 1) {
powrót 1;
}
// przypadek ogólny
jeszcze{
return n + Sum (n-1);
}
}

Powyższa funkcja rekurencyjna przyjmuje liczbę całkowitą „n” i kończy swoje wykonanie tylko wtedy, gdy wartość n jest mniejsza lub równa 1.

Gdybyśmy mieli przekazać liczbę całkowitą 5 do powyższego programu, zmienna „n” przyjęłaby wartość 5. Wartość „n” byłaby wtedy sprawdzana w przypadku podstawowym, ale biorąc pod uwagę, że 5 jest większe niż 1, „n” zostanie teraz przekazane do przypadku ogólnego.

W tym przykładzie ogólny przypadek wywoła funkcję rekurencyjną cztery razy. Przy ostatnim wywołaniu funkcji wartość „n” będzie wynosić 1, skutecznie spełniając wymagania przypadku bazowego, co skutkuje zakończeniem funkcji rekurencyjnej i zwróceniem 15.

Jeśli zmienimy wartość „n” na 7, funkcja rekurencyjna wywoła siebie sześć razy i zwróci 28 przed zakończeniem wykonywania.

Chcesz spróbować samemu? Możesz wykonać powyższy program rekurencyjny, używając następującego wiersza kodu w głównej funkcji programu Java.

System.out.println (Sum (7));

Czego się nauczyłeś

Jeśli przeszedłeś przez cały ten artykuł, masz teraz podstawową wiedzę na temat dwóch powtarzalnych metod, które są używane w programowaniu. Rozpoznajesz teraz podobieństwa między iteracją a rekurencją i dlaczego programista zdecydowałby się na użycie rekurencji zamiast iteracji oraz jak używać funkcji rekurencyjnej w Javie.

Źródło zdjęcia: ThisIsEngineering /Pexels

Co to jest rekursja i jak z niej korzystasz?

Naucz się podstaw rekurencji, podstawowego, ale nieco przykuwającego uwagę narzędzia dla programistów.

Czytaj dalej

O autorze