Jaki jest dobry przykład rekurencji inny niż generowanie ciągu Fibonacciego?

Inne odpowiedzi wspominają o różnych algorytmach, co jest całkowicie w porządku, ale jeśli chcesz nieco bardziej "konkretny" przykład, możesz wyświetlić listę wszystkich plików w jakimś katalogu i jego podkatalogach. Hierarchiczny system plików jest dobrze znanym przykładem rekurencyjnej (drzewiastej) struktury, a za pomocą tego konkretnego przykładu można pokazać Wyszukiwanie głębokości i szerokości.

Moim ulubionym przykładem rekurencji jest Towers of Hanoi: aby przesunąć stos pionków z bieguna A do bieguna B, przesuwasz wszystko powyżej najniższego pionka na biegun, który nie jest A lub B, następnie przesuwasz najniższy pionek do B, a następnie przesuwasz stos, który położyłeś na "słup pomocnika" na szczycie najniższego pionka. W pierwszym i trzecim kroku wykonujemy tę instrukcję rekurencyjnie. Zobacz link dla dłuższego wyjaśnienia:)

Sprawdź dla palyndrom :

bool recursivePalindrome(std::string str, unsigned int index = 0) {
    if (index > str.length()/2) return true;
    else if (str[index] == str[str.length()-index-1])
        return recursivePalindrome(str, ++index);
    else return false;
}

Albo w mniej poważnej nucie:)

void StackOverflow()
{
   StackOverflow();
}

Jak o znalezieniu factorial.

int GetFactorial(int n )
{
  if ( n==0) return 1;
  return n*GetFactorial(n-1);
}

Idea jest taka, że czynnik jest definiowany rekurencyjnie jako iloczyn n i czynnik (n-1). Z definicji rekurencyjnej otrzymujemy rekurencję.

Przemierzanie hierarchii katalogów drzewa katalogów jako części systemu plików jest dobrym przykładem w świecie rzeczywistym. Zajrzyj do tego posta dla przykładu C++:

Dlaczego mam problemy z rekurencyjnym usuwaniem katalogów?

• większość innych przykładów podanych tutaj to przykłady matematyczne, które naprawdę ilustrują to samo zastosowanie rekursji.
• warianty wyszukiwania i sortowania są dobrymi przykładami algorytmów, ale często są zbyt skomplikowane dla początkujących.
Wieże Hanoi to klasyka, ale całkiem wymyślna.

================

Przykładem, którego używam do wykazania prostej mocy rekurencji, jest rekurencyjne przetwarzanie plików w katalogu drzewo.

Oto przykład C#

void ProcessFiles( string sFolder )
{
    foreach( string f in Directory.GetFiles( sFolder ) )
    {
        DoSomethingTo( f );
    }
    foreach( string d in Directory.GetDirectories( sFolder ))
    {
        ProcessFiles( d );
    }
}

Sortowanie scalające jest całkiem dobrym przykładem algorytmu, który jest łatwiejszy do odczytania i zrozumienia, gdy jest zaimplementowany rekurencyjnie.

Oto mała, wysokopoziomowa wersja pseudokodu sortowania Merge:

def merge_sort(List sortlist)
    if sortlist.length <= 1 return sortlist
    split sortlist into leftlist and rightlist
    return merge(merge_sort(leftlist), merge_sort(rightlist))   

def merge(List leftlist, List rightlist)
    while(leftlist and rightlist not empty)
        compare leftlist.first to rightlist.first
        pop lowest value off its list and append to resultlist
    append any remains of leftlist onto resultlist
    append any remains of rightlist onto resultlist
    return resultlist

Iteracyjna wersja tego jest byłaby znacznie bardziej skomplikowana w pisaniu i wizualizacji.

Istnieje kilka próbek:

Liczby katalońskie :

T(n) = Sum(T(i)*T(n-i)) for all 1 <= i < n

Funkcja Ackermanna :

A(x,y) = y+1 (if x = 0)
A(x,y) = A(x-1,1) (if y=0)
A(x,y) = A(x-1, A(x,y-1)) otherwise.

Simple Maze problem

Znalezienie Hamiltonian Path problem

Factorial.

I możesz zobaczyć stronę wiki dla innych odniesień.

Dobre przykłady rekurencji są często związane z przypadkami, w których podstawowa struktura danych lub sam problem jest rekurencyjny: drzewa, wykresy, algorytmy wykorzystujące podejście divide and conquer (jak wiele rodzajów), parser rekurencyjnych gramatyk( jak popularne wyrażenia arytmetyczne), znajdź strategię dla szachowych gier dwóch graczy (dla prostego przykład rozważ Nim), problemy kombinacyjne itp.

Spróbuj rekurencyjnego wyszukiwania binarnego: http://www.fredosaurus.com/notes-cpp/algorithms/searching/rbinarysearch.html

Lub rekurencyjny szybki sort: http://www.dreamincode.net/forums/topic/72311-recursive-quicksort-algorithm/

To tylko dwa małe przykłady w ogromnym świecie funkcji rekurencyjnych.

Ocena wyrażeń arytmetycznych może być wykonywana rekurencyjnie lub iteracyjnie za pomocą stosu. Porównanie tych dwóch podejść może być dość pouczające.

Moja teściowa wzięła kurs wprowadzający do C. miała problem z pracą domową, coś w stylu:

Masz pasek Metalu (Długość len), a liczba zlecenia (n) cięcia metalu na różne długości. Chcesz zmaksymalizować ilość użytego metalu, ale nie może przekraczać całkowitej długości.

Instruktor zasugerował iterację od 1 do 2**N w systemie binarnym, wyłączając kolejność, jeśli jej odpowiedni bit wynosi 0 I włączając kolejność, jeśli jego bit wynosi 1, przy zachowaniu maksymalnej sumy. Jego propozycja przebiegała w czasie wielomianowym.

Inne rozwiązanie istnieje przy użyciu rekurencyjnego algorytmu knapsack . Możesz iterować z len do 1 i najpierw przeszukać głębię, aby rekurencyjnie znaleźć sumę długości.

Innym obszarem, w którym użyłem rekurencji było kodowanie Huffmana (do kompresji ciągu znaków), ale nie ma to intuicyjnego odczucia problemu plecaka.

Rekurencja jest cudowna koncepcja, która jest radykalnie inna. Najlepsze życzenia w nauce lub nauczaniu.

Funkcja Ackermanna:

/* undefined if m and n are negative */
uint32 ackermann( uint32 m, uint32 n )
{
  if( m < 0 && n < 0 ) { exit(1); /* invalid m and n */ }

  if( m == 0 ){ return n + 1; }

  if( m > 0 && n == 0 ){ return ackermann( m - 1, 1 ); }

  if( m > 0 && n > 0 ){ return ackermann( m - 1, ackermann(m, n - 1) ); }
}

Wielokrotne porównania m > 0 są zbędne (i można je uprościć). Pozostawienie ich jako-is pokazuje jednak standardową definicję funkcji Ackermanna.

Ale nie trzeba iść tak daleko poza matematyczną krawędź, aby znaleźć interesujące funkcje rekurencyjne inne niż liczby Fibonnaciego.

Masz największy wspólny mianownik (GDC) funkcja, quicksort i zawsze typowy binarny algorytm wyszukiwania.

Wszystko, co ma hierarchię. Na przykład wymieniając wszystkich pracowników poniżej swojego szefa.

Rekurencja znajduje swoje podstawy w indukcji matematycznej i powinna być nauczana jako taka.

Definiowanie funkcji przez indukcję może być wyraźnie widoczne przy przetwarzaniu listy. Jest wiele rzeczy do powiedzenia na temat fold na przykład.

Następnie przejdź do drzew.

To oczywiście nie C++, ale koncepcja jest dźwiękowa:

PHP rekurencyjnie przemierza zagnieżdżone wielowymiarowe tablice:

public function recurse_me($collection) {
    foreach ($collection as $value) {
        if (is_array($value)) {
            $this->recurse_me($value);
        } else {
            // process value.
        }
    }
}

Pamiętam, że rozumiałem rekurencję pisząc program, który wyszukuje drabiny wyrazów . W danym słowniku.

Przykładem akademickim jest Faktoria

N!

Kalkulator. W prawdziwym życiu, dostajesz matematyczne libs.

Istnieją algorytmy sortowania, które opierają się na rekurencji.

A następnie, jest wyszukiwanie binarne , które jest zaimplementowane z rekurencją.

Trójkąt Pascala

Sortowanie sterty jest również dobrym przykładem. Można o tym przeczytać w "wstępie do algorytmów" Cormena, Rivesta i innych. Świetna książka, mam nadzieję, że znajdziesz tam wiele ciekawych

Wiele operacji na strukturach typu linked-node może być rekurencyjnych. Inni wspominali o BST, ale jeśli nie chcesz wyjaśniać, czym one są, rozważ poszukiwanie najwyższej wartości w liniowej, niesortowanej liście:

int MaxValue(Node node)
{
    if (node == null)
        return 0;

    if (node.Next == null)
        return node.Value;

    int maxNext = MaxValue(node.Next);
    return node.Value > maxNext ? node.Value : maxNext;
}

Listy (w tym przypadku listy połączone) są bardzo łatwe do wyjaśnienia w rzeczywistych warunkach; Twoi odbiorcy nie muszą nawet mieć zaplecza programistycznego. Można go po prostu opisać jako grupę niesortowanych pól lub listę liczb.