Rekurencja w strukturze danych: jak to działa, typy i kiedy są używane

Zacznijmy od definicji rekurencji w strukturze danych. Później omówimy różne typy rekurencji i sposób jej wykorzystania do rozwiązywania różnych problemów.

Co to jest rekurencja?

Mówiąc prościej, rekurencja to rozwiązywanie problemów, aw niektórych przypadkach technika programowania, która ma bardzo specjalną i wyłączną właściwość. W rekursji funkcja lub metoda może wywołać siebie w celu rozwiązania problemu. Proces rekurencji polega na rozwiązaniu problemu poprzez przekształcenie go w mniejsze odmiany samego siebie.

Proces, w którym funkcja wywołuje samą siebie, może zachodzić zarówno bezpośrednio, jak i pośrednio. Ta różnica w wywołaniu powoduje powstawanie różnych typów rekurencji, o których powiemy nieco później. Niektóre problemy, które można rozwiązać za pomocą rekurencji, obejmują DFS wykresu, wieże Hanoi, różne typy przechodzenia przez drzewa i inne. Aby dowiedzieć się o rekurencji i innych koncepcjach nauki o danych, zapoznaj się z internetowymi kursami nauki o danych IIIT-B.

Przeczytaj: 13 ciekawych pomysłów na projekty dotyczące struktury danych

Jak działa rekurencja?

Pojęcie rekurencji opiera się na założeniu, że problem można rozwiązać znacznie łatwo iw krótszym czasie, jeśli jest reprezentowany w jednej lub mniejszej wersji. Dodanie warunków bazowych w celu zatrzymania rekurencji to kolejna ważna część użycia tego algorytmu do rozwiązania problemu.

Ludzie często uważają, że nie da się zdefiniować podmiotu w kategoriach samego siebie. Rekurencja dowodzi, że teoria jest błędna. A jeśli ta technika zostanie przeprowadzona we właściwy sposób, może przynieść bardzo mocne rezultaty. Zobaczmy, jak działa rekurencja na kilku przykładach. Co to jest zdanie? Można go zdefiniować jako dwa lub więcej zdań połączonych ze sobą za pomocą spójnika. Podobnie folder może być urządzeniem pamięci masowej używanym do przechowywania plików i folderów. Przodkiem może być rodzic jednego i przodek innego członka rodziny w drzewie genealogicznym.

Rekurencja pomaga w definiowaniu złożonych sytuacji za pomocą kilku bardzo prostych słów. Jak zwykle zdefiniowałbyś przodka? Rodzica, dziadka lub pradziadka. To może trwać. Podobnie zdefiniowanie folderu może być trudnym zadaniem. Może to być wszystko, co przechowuje niektóre pliki i foldery, które mogą być same w sobie plikami i folderami, i to może się powtarzać. Dlatego rekurencja sprawia, że ​​definiowanie sytuacji jest dużo łatwiejsze niż zwykle.

Rekurencja jest również wystarczająco dobrą techniką programowania. Podprogram rekurencyjny jest zdefiniowany jako taki, który bezpośrednio lub pośrednio wywołuje sam siebie. Wywołanie podprogramu bezpośrednio oznacza, że ​​definicja podprogramu zawiera już instrukcję wywołania podprogramu, który został zdefiniowany.

Z drugiej strony, pośrednie wywołanie podprogramu ma miejsce, gdy podprogram wywołuje inny podprogram, który następnie wywołuje oryginalny podprogram. Rekurencja może wykorzystać kilka linijek kodu do opisania bardzo złożonego zadania. Zwróćmy teraz naszą uwagę na różne rodzaje rekurencji, o których już wspomnieliśmy.

Przeczytaj także: 6 najlepszych języków programowania do nauki

Rodzaje rekurencji

Jak już wspomniano, istnieją tylko dwa rodzaje rekurencji. Zobaczmy, jak różnią się od siebie. Rekurencja bezpośrednia jest prostszym sposobem, ponieważ obejmuje tylko jeden krok wywołania oryginalnej funkcji, metody lub podprogramu. Z drugiej strony rekurencja pośrednia obejmuje kilka etapów.

Pierwsze wywołanie jest wykonywane przez oryginalną metodę z drugą metodą, która z kolei wywołuje oryginalną metodę. Ten łańcuch wywołań może zawierać wiele metod lub funkcji. W prostych słowach możemy powiedzieć, że zawsze istnieje różnica w głębokości rekurencji pośredniej, a ta zmiana głębokości zależy od liczby metod zaangażowanych w proces.

Rekurencja bezpośrednia może być używana do wywoływania tylko pojedynczej funkcji. Z drugiej strony, rekursja pośrednia może być używana do wywoływania więcej niż jednej metody lub funkcji za pomocą innych funkcji, i to również wiele razy. Rekurencja pośrednia nie powoduje narzutu, podczas gdy jej bezpośredni odpowiednik.

Kiedy używana jest rekurencja?

Są sytuacje, w których możesz użyć rekurencji lub iteracji. Należy jednak zawsze wybierać rozwiązanie, które wydaje się bardziej naturalne dla problemu. Rekurencja jest zawsze odpowiednią opcją, jeśli chodzi o abstrakcję danych. Ludzie często używają definicji rekurencyjnych do definiowania danych i powiązanych operacji.

I nie będzie błędem stwierdzenie, że rekurencja jest w większości naturalnym rozwiązaniem problemów związanych z realizacją różnych operacji na danych. Jednak są pewne rzeczy związane z rekurencją, które mogą nie sprawić, że będzie to najlepsze rozwiązanie dla każdego problemu. W takich sytuacjach najlepiej sprawdza się alternatywa, taka jak metoda iteracyjna.

Implementacja rekurencji zajmuje dużo miejsca na stosie, co często może skutkować redundancją. Za każdym razem, gdy używamy rekurencji, wywołujemy metodę, która powoduje utworzenie nowej instancji tej metody. Ta nowa instancja niesie ze sobą różne parametry i zmienne, które są przechowywane na stosie i pobierane przy powrocie. Tak więc, chociaż rekurencja jest prostszym rozwiązaniem niż inne, zwykle nie jest najbardziej praktyczna.

Ponadto nie mamy zestawu predefiniowanych reguł, które mogą pomóc w wyborze iteracji lub rekurencji dla różnych problemów. Największą zaletą korzystania z rekurencji jest to, że jest to metoda zwięzła. To sprawia, że ​​czytanie i utrzymywanie go jest łatwiejsze niż zwykle. Jednak metody rekurencyjne nie są najbardziej wydajnymi dostępnymi metodami, ponieważ zajmują dużo miejsca i zajmują dużo czasu podczas implementacji.

Pamiętając o kilku rzeczach, możesz zdecydować, czy wybór rekursji dla problemu jest właściwą drogą, czy nie. Powinieneś wybrać rekurencję, jeśli problem, który zamierzasz rozwiązać, jest wymieniony w terminach rekurencyjnych, a rozwiązanie rekurencyjne wydaje się mniej złożone.

Powinieneś wiedzieć, że rekurencja w większości przypadków upraszcza implementację algorytmów, których chcesz użyć. Teraz, jeśli złożoność związana z używaniem iteracji i rekurencji jest taka sama dla danego problemu, powinieneś skorzystać z iteracji, ponieważ szanse na to, że będzie bardziej wydajne, są większe.

Sprawdź także: 23 najlepsze kursy programowania komputerowego, aby zdobyć pracę

Wniosek

Mogą jednak zaistnieć sytuacje, w których podjęcie decyzji może nie być takie łatwe. Musisz wybierać między wydajnością a prostotą. Jeśli jesteś doświadczonym projektantem, wiedziałbyś dokładnie, kiedy przykładać większą wagę do wydajności, a wybór prostoty lub zwięzłości jest drogą do zrobienia.

Jeśli chcesz dowiedzieć się więcej o strukturze danych, nauce o danych, sprawdź program Executive PG w dziedzinie Data Science IIIT-B i upGrad, który jest stworzony dla pracujących profesjonalistów i oferuje ponad 10 studiów przypadków i projektów, praktyczne warsztaty praktyczne, mentoring z przemysłem eksperci, indywidualni z mentorami branżowymi, ponad 400 godzin nauki i pomocy w pracy z najlepszymi firmami.