Co to jest rekurencja i kiedy należy jej używać?

Jednym z tematów, który wydaje się regularnie pojawiać się na listach mailingowych i w dyskusjach online, są zalety (lub ich brak) zdobycia tytułu informatyka. Argumentem, który wydaje się pojawiać raz po raz dla strony negatywnej, jest to, że kodowała ona od kilku lat i nigdy nie używała rekurencji.

Więc pytanie brzmi:

1. Co to jest rekurencja?
2. Kiedy używać rekursji?
3. Dlaczego ludzie nie używają rekurencji?

Istnieje wiele dobrych wyjaśnień rekurencji w tym wątku, ta odpowiedź dotyczy tego, dlaczego nie powinieneś jej używać w większości języków. * W większości głównych implementacji języków imperatywnych (tj. Każda większa implementacja C, C ++, Basic, Python Iteracja w Rubim, Javie i C #) jest zdecydowanie lepsza niż rekurencja.

Aby zobaczyć, dlaczego, wykonaj czynności, których używają powyższe języki do wywołania funkcji:

1. przestrzeń jest wycinana na stosie dla argumentów funkcji i zmiennych lokalnych
2. argumenty funkcji są kopiowane do tej nowej przestrzeni
3. sterowanie przechodzi do funkcji
4. działa kod funkcji
5. wynik funkcji jest kopiowany do wartości zwracanej
6. stos jest przewijany do poprzedniej pozycji
7. control przeskakuje z powrotem do miejsca, w którym została wywołana funkcja

Wykonanie wszystkich tych kroków zajmuje trochę czasu, zazwyczaj trochę więcej niż przejście przez pętlę. Jednak prawdziwy problem tkwi w kroku 1. Kiedy uruchamia się wiele programów, alokują one pojedynczy fragment pamięci dla swojego stosu, a gdy zabraknie im tej pamięci (często, ale nie zawsze z powodu rekurencji), program ulega awarii z powodu przepełnienia stosu .

Zatem w tych językach rekurencja jest wolniejsza i naraża Cię na awarie. Nadal istnieją argumenty przemawiające za jego użyciem. Ogólnie rzecz biorąc, kod napisany rekurencyjnie jest krótszy i nieco bardziej elegancki, gdy wiesz, jak go czytać.

Istnieje technika, której mogą używać implementatorzy języka, nazywanej optymalizacją wywołań ogonowych, która może wyeliminować niektóre klasy przepełnienia stosu. Mówiąc zwięźle: jeśli wyrażenie zwracane przez funkcję jest po prostu wynikiem wywołania funkcji, nie musisz dodawać nowego poziomu do stosu, możesz ponownie użyć bieżącego poziomu dla wywoływanej funkcji. Niestety, kilka imperatywnych implementacji języka ma wbudowaną optymalizację wywołań ogonowych.

* Uwielbiam rekurencję. Mój ulubiony język statyczny w ogóle nie używa pętli, rekurencja to jedyny sposób, aby coś powtarzać. Po prostu nie sądzę, aby rekurencja była ogólnie dobrym pomysłem w językach, które nie są do niej dostrojone.

** Swoją drogą Mario, typowa nazwa Twojej funkcji ArrangeString to „join” i byłbym zdziwiony, gdyby Twój wybrany język nie posiadał jeszcze jej implementacji.

Prosty angielski przykład rekurencji.

A child couldn't sleep, so her mother told her a story about a little frog,
    who couldn't sleep, so the frog's mother told her a story about a little bear,
         who couldn't sleep, so the bear's mother told her a story about a little weasel... 
            who fell asleep.
         ...and the little bear fell asleep;
    ...and the little frog fell asleep;
...and the child fell asleep.

W najbardziej podstawowym sensie informatycznym rekurencja jest funkcją, która wywołuje samą siebie. Załóżmy, że masz połączoną strukturę listy:

struct Node {
    Node* next;
};

I chcesz dowiedzieć się, jak długa jest połączona lista, możesz to zrobić z rekurencją:

int length(const Node* list) {
    if (!list->next) {
        return 1;
    } else {
        return 1 + length(list->next);
    }
}

(Można to oczywiście zrobić również za pomocą pętli for, ale jest to przydatne jako ilustracja koncepcji)

Za każdym razem, gdy funkcja wywołuje samą siebie, tworząc pętlę, jest to rekursja. Jak ze wszystkim, rekurencja ma dobre i złe zastosowania.

Najprostszym przykładem jest rekurencja ogona, gdzie ostatnia linia funkcji jest wywołaniem samej siebie:

int FloorByTen(int num)
{
    if (num % 10 == 0)
        return num;
    else
        return FloorByTen(num-1);
}

Jest to jednak kiepski, prawie bezsensowny przykład, ponieważ można go łatwo zastąpić bardziej wydajną iteracją. W końcu rekursja cierpi z powodu narzutu wywołania funkcji, który w powyższym przykładzie może być znaczny w porównaniu z operacją wewnątrz samej funkcji.

Tak więc cały powód, aby wykonywać rekursję zamiast iteracji, powinien polegać na wykorzystaniu stosu wywołań do wykonania sprytnych rzeczy. Na przykład, jeśli wywołujesz funkcję wiele razy z różnymi parametrami wewnątrz tej samej pętli, jest to sposób na wykonanie rozgałęzienia . Klasycznym przykładem jest trójkąt Sierpińskiego .

Możesz narysować jedną z nich w bardzo prosty sposób za pomocą rekurencji, w której stos wywołań rozgałęzia się w 3 kierunkach:

private void BuildVertices(double x, double y, double len)
{
    if (len > 0.002)
    {
        mesh.Positions.Add(new Point3D(x, y + len, -len));
        mesh.Positions.Add(new Point3D(x - len, y - len, -len));
        mesh.Positions.Add(new Point3D(x + len, y - len, -len));
        len *= 0.5;
        BuildVertices(x, y + len, len);
        BuildVertices(x - len, y - len, len);
        BuildVertices(x + len, y - len, len);
    }
}

Jeśli spróbujesz zrobić to samo z iteracją, myślę, że okaże się, że wykonanie znacznie więcej kodu zajmie dużo więcej.

Inne typowe przypadki użycia mogą obejmować hierarchie przechodzenia, np. Przeszukiwacze witryn, porównania katalogów itp.

Wniosek

W praktyce rekurencja ma największy sens, gdy potrzebujesz iteracyjnego rozgałęziania.

Rekurencja to metoda rozwiązywania problemów oparta na mentalności dziel i zwyciężaj. Podstawową ideą jest to, aby wziąć pierwotny problem i podzielić go na mniejsze (łatwiejsze do rozwiązania) wystąpienia samego siebie, rozwiązać te mniejsze wystąpienia (zwykle używając ponownie tego samego algorytmu), a następnie złożyć je ponownie w ostateczne rozwiązanie.

Przykładem kanonicznym jest procedura generowania silni n. Silnię n oblicza się, mnożąc wszystkie liczby od 1 do n. Iteracyjne rozwiązanie w C # wygląda następująco:

public int Fact(int n)
{
  int fact = 1;

  for( int i = 2; i <= n; i++)
  {
    fact = fact * i;
  }

  return fact;
}

Nie ma nic zaskakującego w rozwiązaniu iteracyjnym i powinno mieć sens dla każdego, kto zna C #.

Rozwiązanie rekurencyjne znajdujemy, uznając, że n-ta silnia to n * Fakt (n-1). Innymi słowy, jeśli wiesz, jaka jest konkretna liczba silnia, możesz obliczyć następną. Oto rozwiązanie rekurencyjne w C #:

public int FactRec(int n)
{
  if( n < 2 )
  {
    return 1;
  }

  return n * FactRec( n - 1 );
}

Pierwsza część tej funkcji jest znana jako przypadek bazowy (lub czasami klauzula ochronna) i to ona uniemożliwia działanie algorytmu w nieskończoność. Zwraca po prostu wartość 1 za każdym razem, gdy wywoływana jest funkcja z wartością 1 lub mniejszą. Druga część jest bardziej interesująca i jest znana jako krok rekurencyjny . Tutaj nazywamy tę samą metodę z nieznacznie zmodyfikowanym parametrem (zmniejszamy ją o 1), a następnie mnożymy wynik przez naszą kopię n.

Przy pierwszym napotkaniu może to być trochę zagmatwane, więc pouczające jest zbadanie, jak to działa po uruchomieniu. Wyobraź sobie, że nazywamy FactRec (5). Wchodzimy w rutynę, nie jesteśmy wychwytywani przez przypadek podstawowy, więc kończymy tak:

// In FactRec(5)
return 5 * FactRec( 5 - 1 );

// which is
return 5 * FactRec(4);

Jeśli ponownie wprowadzimy metodę z parametrem 4, ponownie nie zostaniemy zatrzymani przez klauzulę guard, a więc otrzymamy:

// In FactRec(4)
return 4 * FactRec(3);

Jeśli podstawimy tę wartość zwracaną do wartości zwracanej powyżej, otrzymamy

// In FactRec(5)
return 5 * (4 * FactRec(3));

To powinno dać ci wskazówkę, jak doszło do ostatecznego rozwiązania, więc szybko prześlemy i pokażemy każdy krok na drodze w dół:

return 5 * (4 * FactRec(3));
return 5 * (4 * (3 * FactRec(2)));
return 5 * (4 * (3 * (2 * FactRec(1))));
return 5 * (4 * (3 * (2 * (1))));

Ta ostatnia zamiana ma miejsce, gdy zostanie uruchomiony przypadek podstawowy. W tym miejscu mamy do rozwiązania prosty algorytm algrebraiczny, który w pierwszej kolejności równa się bezpośrednio definicji silni.

Warto zauważyć, że każde wywołanie metody powoduje wyzwolenie przypadku podstawowego lub wywołanie tej samej metody, w której parametry są bliżej przypadku podstawowego (często nazywane wywołaniem rekurencyjnym). Jeśli tak nie jest, metoda będzie działać wiecznie.

Rekursja to rozwiązywanie problemu za pomocą funkcji, która wywołuje samą siebie. Dobrym tego przykładem jest funkcja silnia. Silnia to problem matematyczny, w którym na przykład silnia 5 wynosi 5 * 4 * 3 * 2 * 1. Ta funkcja rozwiązuje ten problem w języku C # dla dodatnich liczb całkowitych (nie testowano - może występować błąd).

public int Factorial(int n)
{
    if (n <= 1)
        return 1;

    return n * Factorial(n - 1);
}

Rekursja odnosi się do metody, która rozwiązuje problem poprzez rozwiązanie mniejszej wersji problemu, a następnie wykorzystanie tego wyniku oraz innych obliczeń do sformułowania odpowiedzi na pierwotny problem. Często w trakcie rozwiązywania mniejszej wersji metoda rozwiązuje jeszcze mniejszą wersję problemu i tak dalej, aż osiągnie „podstawowy przypadek”, który jest trywialny do rozwiązania.

Na przykład, aby obliczyć silnię liczby X, można ją przedstawić jako X times the factorial of X-1. Tak więc metoda „powtarza się”, aby znaleźć silnię X-1, a następnie mnoży to, co otrzymała, Xaby dać ostateczną odpowiedź. Oczywiście, aby znaleźć silnię z X-1, najpierw obliczy silnię X-2, i tak dalej. Podstawowy przypadek byłby równy X0 lub 1, w którym to przypadku wie, że ma powrócić 1od tego czasu 0! = 1! = 1.

Rozważ stary, dobrze znany problem :

W matematyce największy wspólny dzielnik (gcd)… dwóch lub więcej niezerowych liczb całkowitych jest największą dodatnią liczbą całkowitą, która dzieli liczby bez reszty.

Definicja gcd jest zaskakująco prosta:

gdzie mod jest operatorem modulo (czyli resztą po dzieleniu liczb całkowitych).

W języku angielskim ta definicja mówi, że największym wspólnym dzielnikiem dowolnej liczby i zerem jest ta liczba, a największy wspólny dzielnik dwóch liczb m i n to największy wspólny dzielnik liczby n, a reszta po podzieleniu m przez n .

Jeśli chcesz wiedzieć, dlaczego to działa, zobacz artykuł w Wikipedii na temat algorytmu Euklidesa .

Obliczmy jako przykład gcd (10, 8). Każdy krok jest równy temu tuż przed nim:

1. gcd (10, 8)
2. gcd (10, 10 mod 8)
3. gcd (8; 2)
4. gcd (8, 8 mod 2)
5. gcd (2; 0)
6. 2

W pierwszym kroku 8 nie jest równe zeru, więc obowiązuje druga część definicji. 10 mod 8 = 2, ponieważ 8 przechodzi do 10 raz z resztą 2. W kroku 3 druga część ma zastosowanie ponownie, ale tym razem 8 mod 2 = 0, ponieważ 2 dzieli 8 bez reszty. W kroku 5 drugi argument to 0, więc odpowiedź to 2.

Czy zauważyłeś, że gcd pojawia się po lewej i prawej stronie znaku równości? Matematyk powiedziałby, że ta definicja jest rekurencyjna, ponieważ wyrażenie, które definiujesz, powtarza się w swojej definicji.

Definicje rekurencyjne wydają się być eleganckie. Na przykład rekurencyjna definicja sumy listy to

sum l =
    if empty(l)
        return 0
    else
        return head(l) + sum(tail(l))

gdzie headjest pierwszym elementem listy i tailpozostałą częścią listy. Zauważ, że sumna końcu powtarza się w definicji.

Może wolisz zamiast tego maksymalną wartość na liście:

max l =
    if empty(l)
        error
    elsif length(l) = 1
        return head(l)
    else
        tailmax = max(tail(l))
        if head(l) > tailmax
            return head(l)
        else
            return tailmax

Możesz zdefiniować mnożenie nieujemnych liczb całkowitych rekurencyjnie, aby przekształcić je w serię dodawania:

a * b =
    if b = 0
        return 0
    else
        return a + (a * (b - 1))

Jeśli ten fragment dotyczący przekształcania mnożenia w serię dodatków nie ma sensu, spróbuj rozwinąć kilka prostych przykładów, aby zobaczyć, jak to działa.

Sortowanie przez scalanie ma piękną rekurencyjną definicję:

sort(l) =
    if empty(l) or length(l) = 1
        return l
    else
        (left,right) = split l
        return merge(sort(left), sort(right))

Definicje rekurencyjne są wszędzie, jeśli wiesz, czego szukać. Zauważ, że wszystkie te definicje mają bardzo proste przypadki podstawowe, np. Gcd (m, 0) = m. Przypadki rekurencyjne zmniejszają problem, aby przejść do łatwych odpowiedzi.

Dzięki temu zrozumieniu możesz teraz docenić inne algorytmy w artykule Wikipedii na temat rekurencji !

1. Funkcja, która sama siebie wywołuje
2. Gdy funkcję można (łatwo) rozłożyć na prostą operację plus tę samą funkcję na jakiejś mniejszej części problemu. Powinienem raczej powiedzieć, że to czyni go dobrym kandydatem do rekurencji.
3. Robią!

Przykładem kanonicznym jest silnia, która wygląda następująco:

int fact(int a) 
{
  if(a==1)
    return 1;

  return a*fact(a-1);
}

Ogólnie rekurencja niekoniecznie musi być szybka (narzut wywołań funkcji jest zwykle wysoki, ponieważ funkcje rekurencyjne są zwykle małe, patrz wyżej) i może powodować pewne problemy (ktoś przepełnia stos?). Niektórzy twierdzą, że trudno jest je „dobrze” znaleźć w nietrywialnych przypadkach, ale ja tak naprawdę nie wierzę w to. W niektórych sytuacjach rekurencja ma największy sens i jest najbardziej eleganckim i przejrzystym sposobem zapisu określonej funkcji. Należy zauważyć, że niektóre języki preferują rozwiązania rekurencyjne i znacznie bardziej je optymalizują (przychodzi na myśl LISP).

Funkcja rekurencyjna to taka, która sama siebie wywołuje. Najczęstszym powodem, dla którego go używam, jest przechodzenie przez strukturę drzewa. Na przykład, jeśli mam TreeView z polami wyboru (pomyśl o instalacji nowego programu, strona „wybierz funkcje do zainstalowania”), mogę potrzebować przycisku „zaznacz wszystko”, który wyglądałby mniej więcej tak (pseudokod):

function cmdCheckAllClick {
    checkRecursively(TreeView1.RootNode);
}

function checkRecursively(Node n) {
    n.Checked = True;
    foreach ( n.Children as child ) {
        checkRecursively(child);
    }
}

Możesz więc zobaczyć, że checkRecursively najpierw sprawdza węzeł, do którego jest przekazywany, a następnie wywołuje siebie dla każdego z dzieci tego węzła.

Musisz być trochę ostrożny z rekurencją. Jeśli dostaniesz się do nieskończonej pętli rekurencyjnej, otrzymasz wyjątek przepełnienia stosu :)

Nie mogę wymyślić powodu, dla którego ludzie nie powinni go używać, kiedy jest to stosowne. Jest to przydatne w pewnych okolicznościach, a w innych nie.

Myślę, że ponieważ jest to interesująca technika, być może niektórzy programiści używają jej częściej niż powinni, bez prawdziwego uzasadnienia. To spowodowało, że rekurencja miała złą opinię w niektórych kręgach.

Rekurencja to wyrażenie bezpośrednio lub pośrednio odwołujące się do siebie.

Rozważmy rekurencyjne akronimy jako prosty przykład:

• GNU to skrót od GNU's Not Unix
• PHP oznacza PHP: Hypertext Preprocessor
• YAML oznacza YAML Ain't Markup Language
• WINE oznacza wino nie jest emulatorem
• VISA to skrót od Visa International Service Association

Więcej przykładów na Wikipedii

Rekurencja działa najlepiej z czymś, co lubię nazywać „problemami fraktali”, gdzie mamy do czynienia z wielką rzeczą, która składa się z mniejszych wersji tej dużej rzeczy, z których każda jest jeszcze mniejszą wersją dużej rzeczy, i tak dalej. Jeśli kiedykolwiek będziesz musiał przechodzić lub przeszukiwać coś takiego jak drzewo lub zagnieżdżone identyczne struktury, masz problem, który może być dobrym kandydatem do rekursji.

Ludzie unikają rekurencji z wielu powodów:

1. Większość ludzi (łącznie ze mną) wycina swoje umiejętności programowania w programowaniu proceduralnym lub obiektowym w przeciwieństwie do programowania funkcjonalnego. Dla takich osób podejście iteracyjne (zazwyczaj przy użyciu pętli) wydaje się bardziej naturalne.

2. Tym z nas, którzy wycinają swoje umiejętności programowania w programowaniu proceduralnym lub obiektowym, często mówiono, aby unikali rekursji, ponieważ jest ona podatna na błędy.

3. Często słyszymy, że rekurencja jest powolna. Wielokrotne wywoływanie i powracanie z rutyny wiąże się z częstym wpychaniem i wyskakiwaniem stosu, co jest wolniejsze niż zapętlanie. Myślę, że niektóre języki radzą sobie z tym lepiej niż inne, a te języki najprawdopodobniej nie są tymi, w których dominujący paradygmat jest proceduralny lub zorientowany obiektowo.

4. Przynajmniej dla kilku języków programowania, których używałem, pamiętam zalecenia, aby nie używać rekursji, jeśli przekroczy ona określoną głębokość, ponieważ jej stos nie jest tak głęboki.

Instrukcja rekurencyjna to taka, w której definiujesz proces tego, co należy zrobić, jako kombinację danych wejściowych i tego, co już zrobiłeś.

Na przykład, weź silnię:

factorial(6) = 6*5*4*3*2*1

Ale łatwo zauważyć, że silnia (6) to również:

6 * factorial(5) = 6*(5*4*3*2*1).

Więc ogólnie:

factorial(n) = n*factorial(n-1)

Oczywiście, najtrudniejsze w rekurencji jest to, że jeśli chcesz zdefiniować rzeczy w kategoriach tego, co już zrobiłeś, musisz mieć od czego zacząć.

W tym przykładzie po prostu tworzymy specjalny przypadek, definiując silnię (1) = 1.

Teraz widzimy to od dołu do góry:

factorial(6) = 6*factorial(5)
                   = 6*5*factorial(4)
                   = 6*5*4*factorial(3) = 6*5*4*3*factorial(2) = 6*5*4*3*2*factorial(1) = 6*5*4*3*2*1

Ponieważ zdefiniowaliśmy silnię (1) = 1, osiągamy „dno”.

Ogólnie rzecz biorąc, procedury rekurencyjne składają się z dwóch części:

1) Część rekurencyjna, która definiuje jakąś procedurę pod względem nowych danych wejściowych połączonych z tym, co „już zrobiłeś” za pomocą tej samej procedury. (tj. factorial(n) = n*factorial(n-1))

2) Część podstawowa, która zapewnia, że ​​proces nie będzie się powtarzał w nieskończoność, dając mu miejsce do rozpoczęcia (tj. factorial(1) = 1)

Na początku może być trochę zagmatwane, ale spójrz tylko na kilka przykładów i wszystko powinno się połączyć. Jeśli chcesz głębiej zrozumieć tę koncepcję, przestudiuj indukcję matematyczną. Należy również pamiętać, że niektóre języki są optymalizowane pod kątem wywołań rekurencyjnych, a inne nie. Tworzenie szalenie wolnych funkcji rekurencyjnych jest dość łatwe, jeśli nie jesteś ostrożny, ale istnieją również techniki, dzięki którym w większości przypadków są one wydajne.

Mam nadzieję że to pomoże...

Podoba mi się ta definicja: w
rekurencji procedura sama rozwiązuje niewielką część problemu, dzieli go na mniejsze części, a następnie wzywa siebie do rozwiązania każdego z mniejszych elementów.

Podoba mi się również dyskusja Steve'a McConnell'a na temat rekursji w Code Complete, gdzie krytykuje przykłady użyte w książkach informatycznych na temat rekursji.

Nie używaj rekurencji dla silni lub liczb Fibonacciego

Jednym z problemów z podręcznikami informatyki jest to, że przedstawiają one głupie przykłady rekurencji. Typowe przykłady to obliczanie silni lub obliczanie sekwencji Fibonacciego. Rekurencja to potężne narzędzie i korzystanie z niej w każdym z tych przypadków jest naprawdę głupie. Gdyby programista, który dla mnie pracował, użył rekurencji do obliczenia silni, zatrudniłbym kogoś innego.

Pomyślałem, że to bardzo interesująca kwestia do podniesienia i może być powodem, dla którego rekurencja jest często źle rozumiana.

EDYCJA: To nie była kopalnia odpowiedzi Dava - nie widziałem tej odpowiedzi, kiedy to opublikowałem

1.) Metoda jest rekurencyjna, jeśli może wywołać samą siebie; albo bezpośrednio:

void f() {
   ... f() ... 
}

lub pośrednio:

void f() {
    ... g() ...
}

void g() {
   ... f() ...
}

2.) Kiedy używać rekursji

Q: Does using recursion usually make your code faster? 
A: No.
Q: Does using recursion usually use less memory? 
A: No.
Q: Then why use recursion? 
A: It sometimes makes your code much simpler!

3.) Ludzie używają rekurencji tylko wtedy, gdy napisanie kodu iteracyjnego jest bardzo skomplikowane. Na przykład techniki przechodzenia po drzewie, takie jak preorder, postorder, mogą być zarówno iteracyjne, jak i rekurencyjne. Ale zwykle używamy rekurencji ze względu na jej prostotę.

Oto prosty przykład: ile elementów w zestawie. (są lepsze sposoby liczenia rzeczy, ale to jest ładny, prosty przykład rekurencyjny).

Po pierwsze, potrzebujemy dwóch zasad:

1. jeśli zestaw jest pusty, liczba elementów w zestawie wynosi zero (aha!).
2. jeśli zestaw nie jest pusty, liczba wynosi jeden plus liczba elementów w zestawie po usunięciu jednego elementu.

Załóżmy, że masz taki zestaw: [xxx]. policzmy, ile jest przedmiotów.

1. zbiór to [xxx], który nie jest pusty, więc stosujemy zasadę 2. liczba elementów to jeden plus liczba elementów w [xx] (czyli usunęliśmy element).
2. zbiór to [xx], więc ponownie stosujemy zasadę 2: jeden + liczba elementów w [x].
3. zbiór to [x], który nadal pasuje do reguły 2: jeden + liczba elementów w [].
4. Teraz zestaw to [], co odpowiada zasadzie 1: liczba wynosi zero!
5. Teraz, gdy znamy odpowiedź w kroku 4 (0), możemy rozwiązać krok 3 (1 + 0)
6. Podobnie, teraz, gdy znamy odpowiedź w kroku 3 (1), możemy rozwiązać krok 2 (1 + 1)
7. I wreszcie, skoro już znamy odpowiedź w kroku 2 (2), możemy rozwiązać krok 1 (1 + 2) i uzyskać liczbę elementów w [xxx], czyli 3. Brawo!

Możemy to przedstawić jako:

count of [x x x] = 1 + count of [x x]
                 = 1 + (1 + count of [x])
                 = 1 + (1 + (1 + count of []))
                 = 1 + (1 + (1 + 0)))
                 = 1 + (1 + (1))
                 = 1 + (2)
                 = 3

Stosując rozwiązanie rekurencyjne, zazwyczaj masz co najmniej 2 reguły:

• podstawa, prosty przypadek, który określa, co się stanie, gdy „zużyjesz” wszystkie swoje dane. Zwykle jest to odmiana „jeśli brakuje Ci danych do przetworzenia, Twoja odpowiedź brzmi X”
• reguła rekurencyjna, która określa, co się stanie, jeśli nadal masz dane. Zwykle jest to rodzaj reguły, która mówi „zrób coś, aby zmniejszyć swój zestaw danych i ponownie zastosuj swoje reguły do ​​mniejszego zestawu danych”.

Jeśli przetłumaczymy powyższe na pseudokod, otrzymamy:

numberOfItems(set)
    if set is empty
        return 0
    else
        remove 1 item from set
        return 1 + numberOfItems(set)

Jest o wiele więcej przydatnych przykładów (na przykład przechodzenie po drzewie), które z pewnością będą omawiać inne osoby.

Cóż, masz całkiem przyzwoitą definicję. Wikipedia też ma dobrą definicję. Więc dodam dla ciebie kolejną (prawdopodobnie gorszą) definicję.

Kiedy ludzie odnoszą się do „rekurencji”, zwykle mówią o napisanej przez siebie funkcji, która wywołuje samą siebie wielokrotnie, dopóki nie zostanie zakończona. Rekursja może być pomocna podczas przechodzenia przez hierarchie w strukturach danych.

Przykład: rekurencyjna definicja klatki schodowej to: Klatka schodowa składa się z: - pojedynczego stopnia i klatki schodowej (rekurencja) - lub tylko jednego stopnia (zakończenie)

Aby powtórzyć się w rozwiązanym problemie: nic nie rób, gotowe.
Aby powtórzyć się w przypadku otwartego problemu: wykonaj następny krok, a następnie powtórz resztę.

Mówiąc prostym językiem: załóżmy, że możesz zrobić 3 rzeczy:

1. Weź jedno jabłko
2. Zapisz znaczniki
3. Policz znaczniki

Masz przed sobą dużo jabłek na stole i chcesz wiedzieć, ile jest jabłek.

start
  Is the table empty?
  yes: Count the tally marks and cheer like it's your birthday!
  no:  Take 1 apple and put it aside
       Write down a tally mark
       goto start

Proces powtarzania tej samej rzeczy, dopóki nie skończysz, nazywa się rekurencją.

Mam nadzieję, że jest to odpowiedź „zwykłym angielskim”, której szukasz!

Funkcja rekurencyjna to funkcja, która zawiera wywołanie samej siebie. Struktura rekurencyjna to struktura zawierająca wystąpienie samej siebie. Możesz połączyć te dwie klasy w klasę rekurencyjną. Kluczową częścią elementu rekurencyjnego jest to, że zawiera on własną instancję / wywołanie.

Rozważ dwa lustra zwrócone do siebie. Widzieliśmy zgrabny efekt nieskończoności, jaki wywołują. Każde odbicie jest instancją zwierciadła, które jest zawarte w innej instancji lustra, itd. Lustro zawierające odbicie samego siebie jest rekurencją.

Wyszukiwania binarne drzewo jest dobrym przykładem programowanie rekursji. Struktura jest rekurencyjna, a każdy węzeł zawiera 2 wystąpienia węzła. Funkcje do pracy na drzewie wyszukiwania binarnego są również rekurencyjne.

To jest stare pytanie, ale chcę dodać odpowiedź z logistycznego punktu widzenia (tj. Nie z punktu widzenia poprawności algorytmu lub punktu widzenia wydajności).

Używam Javy do pracy, a Java nie obsługuje funkcji zagnieżdżonych. W związku z tym, jeśli chcę wykonywać rekursję, być może będę musiał zdefiniować funkcję zewnętrzną (która istnieje tylko dlatego, że mój kod zderza się z biurokratyczną regułą Javy) lub być może będę musiał całkowicie refaktoryzować kod (czego naprawdę nienawidzę robić).

Dlatego często unikam rekursji i zamiast tego używam operacji na stosie, ponieważ sama rekursja jest zasadniczo operacją na stosie.

Chcesz go używać zawsze, gdy masz strukturę drzewa. Jest to bardzo przydatne w czytaniu XML.

Rekurencja w przypadku programowania polega w zasadzie na wywołaniu funkcji z jej własnej definicji (wewnątrz samej siebie), z różnymi parametrami w celu wykonania zadania.

„Jeśli mam młotek, spraw, by wszystko wyglądało jak gwóźdź”.

Rekurencja to strategia rozwiązywania dużych problemów, w której na każdym kroku „zamień dwie małe rzeczy w jedną większą rzecz” za każdym razem tym samym młotkiem.

Przykład

Załóżmy, że twoje biurko jest pokryte chaotycznym bałaganem złożonym z 1024 kartek. Jak zrobić jeden schludny, czysty stos papierów z bałaganu, używając rekurencji?

1. Podziel: Rozłóż wszystkie arkusze, tak aby w każdym „stosie” był tylko jeden arkusz.
2. Podbić:
   2. Chodź, kładąc każdy arkusz na innym arkuszu. Masz teraz 2 stosy.
   3. Idź dookoła, kładąc każdy 2 stos na drugim 2 stosie. Masz teraz 4 stosy.
   4. Idź dookoła, kładąc każdy 4 stosy na innym 4 stosie. Masz teraz w stosach 8.
   5. ... ciągle ...
   6. Masz teraz jeden ogromny stos 1024 arkuszy!

Zauważ, że jest to dość intuicyjne, poza liczeniem wszystkiego (co nie jest absolutnie konieczne). W rzeczywistości możesz nie zejść do stosów z 1 arkuszem, ale możesz i nadal będzie działać. Ważną częścią jest młotek: za pomocą rąk zawsze możesz umieścić jeden stos na drugim, aby uzyskać większy stos, i nie ma znaczenia (w granicach rozsądku), jak duży jest każdy stos.

Rekurencja to proces, w którym wywołanie metody polega na tym, aby móc wykonać określone zadanie. Zmniejsza nadmiarowość kodu. Większość funkcji lub metod rekurencyjnych musi mieć warunek, aby przerwać wywołanie rekusyjne, tj. Zatrzymać wywoływanie samego siebie, jeśli warunek zostanie spełniony - zapobiega to tworzeniu nieskończonej pętli. Nie wszystkie funkcje nadają się do użytku rekurencyjnego.

hej, przepraszam, jeśli moja opinia się z kimś zgadza, po prostu próbuję wyjaśnić rekurencję prostym angielskim.

załóżmy, że masz trzech menedżerów - Jacka, Johna i Morgana. Jack zarządza 2 programistami, Johnem - 3 i Morganem - 5. Masz zamiar dać każdemu menedżerowi 300 $ i chcesz wiedzieć, ile by to kosztowało. Odpowiedź jest oczywista - ale co, jeśli 2 pracowników Morgan-s jest również menedżerami?

TUTAJ nadchodzi rekurencja. zaczynasz od góry w hierarchii. koszt letni to 0 $. zaczynasz od Jacka, potem sprawdź, czy ma jakichś menedżerów jako pracowników. jeśli zauważysz, że któryś z nich jest, sprawdź, czy mają jakichś menedżerów jako pracowników i tak dalej. Dodaj 300 $ do letniego kosztu za każdym razem, gdy znajdziesz menedżera. kiedy skończysz z Jackiem, udaj się do Johna, jego pracowników, a następnie do Morgana.

Nigdy nie dowiesz się, ile cykli przejdziesz, zanim uzyskasz odpowiedź, chociaż wiesz, ilu masz menedżerów i ile budżetu możesz wydać.

Rekurencja to drzewo z gałęziami i liśćmi, zwane odpowiednio rodzicami i dziećmi. Kiedy używasz algorytmu rekurencyjnego, mniej lub bardziej świadomie budujesz drzewo na podstawie danych.

Mówiąc prostym językiem, rekurencja oznacza ciągłe powtarzanie czegoś.

W programowaniu jednym z przykładów jest wywołanie funkcji w samej sobie.

Spójrz na następujący przykład obliczania silni liczby:

public int fact(int n)
{
    if (n==0) return 1;
    else return n*fact(n-1)
}

Każdy algorytm wykazuje strukturalną rekursję na typie danych, jeśli zasadniczo składa się z instrukcji przełączającej z przypadkiem dla każdego przypadku typu danych.

na przykład, gdy pracujesz nad czcionką

  tree = null 
       | leaf(value:integer) 
       | node(left: tree, right:tree)

strukturalny algorytm rekurencyjny miałby postać

 function computeSomething(x : tree) =
   if x is null: base case
   if x is leaf: do something with x.value
   if x is node: do something with x.left,
                 do something with x.right,
                 combine the results

jest to naprawdę najbardziej oczywisty sposób na napisanie dowolnego algorytmu, który działa na strukturze danych.

teraz, gdy spojrzymy na liczby całkowite (no cóż, liczby naturalne) zdefiniowane za pomocą aksjomatów Peano

 integer = 0 | succ(integer)

widzisz, że strukturalny algorytm rekurencyjny na liczbach całkowitych wygląda tak

 function computeSomething(x : integer) =
   if x is 0 : base case
   if x is succ(prev) : do something with prev

zbyt dobrze znana funkcja silnia jest najbardziej trywialnym przykładem tej postaci.

funkcja wywołuje samą siebie lub używa własnej definicji.