Jakie są rozważania, aby ustalić, czy można użyć rekurencji do rozwiązania problemu?

Czasami w wywiadach mogę użyć rekurencji, aby rozwiązać problem (na przykład dodanie 1do nieskończonej liczby całkowitej precyzji) lub gdy problem wydaje się odpowiedni do użycia rekurencji. Czasami może to wynikać z częstego używania rekurencji do rozwiązywania problemów, więc bez większego zastanowienia rekursja służy do rozwiązania problemu.

Jakie są jednak uwagi, zanim zdecydujesz, że do rozwiązania problemu należy użyć rekurencji?

Kilka myśli, które miałem:

Jeśli użyjemy rekurencji na danych, które są zmniejszane o połowę za każdym razem, wydaje się, że nie ma problemu z użyciem rekurencji, ponieważ wszystkie dane, które mogą zmieścić się w 16 GB pamięci RAM, a nawet na dysku twardym o pojemności 8 TB, mogą być obsługiwane przez rekurencję na głębokości zaledwie 42 poziomów. (więc nie ma przepełnienia stosu (myślę, że w niektórych środowiskach stos może mieć głębokość 4000 poziomów, znacznie więcej niż 42, ale jednocześnie zależy to również od tego, ile zmiennych lokalnych, jak każdy stos wywołań, zajmuje więcej pamięci jeśli istnieje wiele zmiennych lokalnych i to rozmiar pamięci, a nie poziom, determinuje przepełnienie stosu)).

Jeśli obliczasz liczby Fibonacciego za pomocą czystej rekurencji, naprawdę musisz martwić się złożonością czasu, chyba że buforujesz wyniki pośrednie.

A co powiesz na dodanie 1liczby całkowitej nieskończonej precyzji? Może jest to dyskusyjne, ponieważ czy będziesz pracować z liczbami o długości 3000 cyfr lub długości 4000 cyfr, tak dużej, że może to spowodować przepełnienie stosu? Nie myślałem o tym, ale może odpowiedź brzmi nie, nie powinniśmy używać rekurencji, ale po prostu używać zwykłej pętli, ponieważ co, jeśli w niektórych aplikacjach liczba naprawdę musi mieć długość 4000 cyfr, aby sprawdzić niektóre właściwości liczby, takie jak to, czy liczba jest liczbą pierwszą, czy nie.

Ostateczne pytanie brzmi: jakie są względy, zanim zdecydujesz się użyć rekurencji do rozwiązania problemu?

Jednym z rozważań jest to, czy algorytm ma być rozwiązaniem abstrakcyjnym, czy praktycznym rozwiązaniem wykonywalnym. W pierwszym przypadku poszukiwanymi atrybutami są poprawność i łatwość zrozumienia dla grupy docelowej ¹ . W tym drugim przypadku problemem jest także wydajność. Te uwagi mogą wpłynąć na twój wybór.

Drugim zagadnieniem (dla praktycznego rozwiązania) jest to, czy język programowania (a ściślej jego implementacja), którego używasz, eliminuje ogon? Bez eliminacji wywołania ogonowego rekurencja jest wolniejsza niż iteracja, a głęboka rekurencja może prowadzić do problemów z przepełnieniem stosu.

Zauważ, że (poprawne) rozwiązanie rekurencyjne można przekształcić w równoważne rozwiązanie nierekurencyjne, więc niekoniecznie musisz dokonać trudnego wyboru między tymi dwoma podejściami.

Wreszcie, czasami wybór między formami rekurencyjnymi i nierekurencyjnymi jest motywowany potrzebą udowodnienia (w sensie formalnym) właściwości algorytmu. Formuły rekurencyjne bardziej bezpośrednio pozwalają na korektę przez indukcję.

^{1 - Obejmuje to takie kwestie, jak to, czy docelowi odbiorcy ... a może to obejmować programistów czytających praktyczny kod ... postrzegaliby jeden styl rozwiązania jako „bardziej naturalny” niż drugi. Pojęcie „naturalny” będzie się różnić w zależności od osoby, w zależności od tego, jak nauczyli się programowania lub algorytmiki. (Rzucam wyzwanie każdemu, kto zaproponuje „naturalność” jako podstawowe kryterium przy podejmowaniu decyzji o użyciu rekurencji (lub jej braku) do zdefiniowania „naturalności” w kategoriach obiektywnych, tj. Jak byś ją zmierzył.)}

Jako programista C / C ++, uważam przede wszystkim za wydajność. Mój proces decyzyjny przypomina:

1. Jaka jest maksymalna głębokość stosu wywołań? Jeśli jest zbyt głęboko, pozbądź się rekurencji. Jeśli jest płytki, przejdź do 2.

2. Czy ta funkcja może stanowić wąskie gardło mojego programu? Jeśli tak, przejdź do 3. Jeśli nie, zachowaj rekurencję. W razie wątpliwości uruchom profiler.

3. Jaki ułamek czasu procesora spędzonego na wywołaniach funkcji rekurencyjnych? Jeśli wywołania funkcji zajmują znacznie mniej czasu niż reszta treści funkcji, można użyć rekurencji.

Jakie są jednak uwagi, zanim zdecydujesz, że do rozwiązania problemu należy użyć rekurencji?

Pisząc funkcje w schemacie, uważam za naturalne pisanie funkcji rekurencyjnych bez myślenia za dużo.

Pisząc funkcje w C ++, zastanawiam się, zanim użyję funkcji rekurencyjnej. Pytania, które sobie zadaję to:

• Czy obliczenia można wykonać przy użyciu algorytmu iteracyjnego? Jeśli tak, zastosuj podejście iteracyjne.

• Czy głębokość rekurencji może wzrosnąć o rozmiar modelu? Niedawno wpadłem na przypadek, w którym głębokość rekurencji wzrosła do prawie 13000 z powodu wielkości modelu. Musiałem przekonwertować funkcję, aby użyć algorytmu iteracyjnego po pośpiechu.

  Z tego powodu nie polecałbym pisania algorytmu przechodzenia przez drzewo przy użyciu funkcji rekurencyjnych. Nigdy nie wiadomo, kiedy drzewo stanie się zbyt głębokie dla środowiska wykonawczego.

• Czy funkcja może stać się zbyt skomplikowana przy użyciu algorytmu iteracyjnego? Jeśli tak, użyj funkcji rekurencyjnej. Nie próbowałem pisać qsortmetodą iteracyjną, ale mam wrażenie, że użycie funkcji rekurencyjnej jest dla niej bardziej naturalne.

W przypadku liczb Fibonacciego naiwna „rekurencja” jest po prostu całkowicie głupia. To dlatego, że prowadzi to do tego samego podproblemu, który jest rozwiązywany w kółko.

W rzeczywistości istnieje trywialna zmienność liczb Fibonacciego, w których rekurencja jest bardzo skuteczna: Biorąc pod uwagę liczbę n ≥ 1, oblicz zarówno fib (n), jak i fib (n-1). Potrzebujesz więc funkcji, która zwraca dwa wyniki, nazwijmy tę funkcję fib2.

Implementacja jest dość prosta:

function fib2 (n) -> (fibn, fibnm1) {
    if n ≤ 1 { return (1, 1) }
    let (fibn, fibnm1) = fib2 (n-1)
    return (fibn + fibnm1, fibn)
}