Jak myśleć w sposób rekurencyjny?

Question

Aby zrozumieć zaawansowane algorytmy, takie jak chciwe metody i dynamiczne programowanie, najpierw trzeba dobrze znać rekursję.

Jestem stosunkowo nowy w rekursji. Ilekroć zadawane jest pytanie, pierwsze rzeczy, które pojawiają się w umyśle, to rozwiązania wykorzystujące iteracje. Chociaż wiem, co oznaczają metody rekursywne i jak to działa, bardzo trudno jest myśleć w sposób rekursywny.

Proszę pomóc odpowiadając na poniższe pytania:

1) może być dowolny sposób iteracyjny zastąpione przez rekursji i vice versa?

Na przykład, jak drukować elementy w tablicy o rozmiarze n rekursywnie?

for i 0 to n 
Print a[i] 

2) Jak rozwiązać problem rekurencyjnie? Jakie są kroki? Czy są jakieś wskazówki, aby zidentyfikować, że problemy można rozwiązać rekurencyjnie?

Dla ex: Jeśli jestem pytany, aby wydrukować wszystkie sznurki Sub ciąg

INPUT: CAT 
OUTPUT: CAT,CA,A,AT,T 

mogę wymyślić iteracyjny sposób fast.Using dwie pętle może rozwiązać ten problem.

Rekursywnie, jak go rozwiązać. Jak zidentyfikować, że problemy można rozwiązać rekursywnie.

Jeśli odpowiedź na moje pierwsze pytanie brzmi "tak", użycie dwóch rekursji zamiast iteracji może być rozwiązaniem mojego problemu?

3) Czy ktoś może zaproponować mi jakieś materiały/zasoby, aby dokładnie zrozumieć koncepcję rekurencji?

Answer 1

1. Tak, głównie. Ogólnie rekurencja jest wykonywana dla programisty, a nie dla komputera. Istnieją metody iteracyjne, które w niektórych przypadkach mogą działać szybciej niż rekursywne, ale iteratywna metoda może zająć 300 linii kodu i rekursywną 3. Istnieją również przypadki, w których łatwo jest znaleźć sposób, aby programowo rekursywnie, ale jest bardzo trudne do napisania iteracyjnie i odwrotnie.

2. Zasadniczo rozwiązanie rekurencyjne musi być pod względem funkcji. Jeśli używamy czegoś takiego jak C++, możemy użyć rozwiązania obsługującego odwołania do łańcuchów i rzeczy, powoli dostosowując łańcuchy przekazywane jako parametry. Punkt pod koniec "dwóch rekursji" jest jednak błędny. Zasada polega na tym, że zamiast dwóch iteracji możemy wykonać jedno podejście rekurencyjne.

3. Ta strona (wysoko w wyszukiwarce Google) uczy wielu teorii matematycznych rekursji i zawiera FAQ, które mogą dać ci bardziej satysfakcjonującą odpowiedź na numer jeden.

Answer 2

@Test 
public void testStrings() { 
    TreeSet<String> finalTree = getSubStringsOf("STACK"); 
    for(String subString : finalTree){ 
     System.out.println(subString); 
    } 
} 

public TreeSet<String> getSubStringsOf(String stringIn) { 
    TreeSet<String> stringOut = new TreeSet<String>(); 
    if (stringIn.length() == 1) { 
     stringOut.add(stringIn); 
     return stringOut; 
    } else { 
     for (int i = 1; i < stringIn.length() ; i++) { 
      String stringBefore = stringIn.substring(0, i); 
      String stringAfter = stringIn.substring(i); 
      stringOut.add(stringBefore); 
      stringOut.add(stringAfter); 
      stringOut.addAll(getSubStringsOf(stringBefore)); 
      stringOut.addAll(getSubStringsOf(stringAfter)); 
     } 
     return stringOut; 
    } 
} 

Nie wiem, jeśli potrzebujesz wyjaśnienia. Dzielicie łańcuch na dwa za każdym razem, gdy jest to możliwe. Cat jest więc podzielony na CA, T i C, AT, dodajesz je do listy podłańcuchów, następnie poszukujesz każdego podciągu tych podłańcuchów. Jeśli ciąg jest pojedynczym znakiem, dodajesz pojedynczy znak do drzewa.

EDIT: to wyjście dla stosu:

A AC ACK C CK K S ST STA STAC T TA TAC TACK

EDIT ponownie: Jak widać, za każdym razem uruchomić metodę podciąg, będziesz używać go dwa razy w środku, chyba że jest to pojedynczy ciąg znaków. Tak więc złożoność jest O (n²). W przypadku "STACK" program ma długość 0,200 ms, a "STACKSTACKSTACK" (3-krotny stos) wynosi 2 sekundy, ponieważ "STACKSTACKSTACKSTACKSTACK" jest teoretycznie 2^10 razy więcej, a więc 2000 sekund.

Answer 3

Istnieje sposób myślenia o rekurencji, który sprawia, że ​​jest to tak proste jak iteracja.

W iteracji mamy pętlę. Pomyśl o tym, że ma 4 części:

1. Decyzja o kontynuacji lub zatrzymaniu, w oparciu o niektóre dane "kontrolne", ocenione jako warunek logiczny.

2. Ciało, gdzie praca została wykonana. Czasami ciało łączy się z kolejną częścią.

3. Sposób zmiany danych "kontrolujących". Często poprzez zmianę licznika.

4. Sposób wywołania konstruktu (w tym przypadku pętli) ponownie. W językach w stylu c jest to zapewniane przez składnię for, while lub do.

W rekurencji mamy funkcję (czasami kilka). Mają te same 4 części:

1. Decyzję o kontynuacji lub stop, na podstawie niektórych „Sterowanie” danych, ocenianych jako warunek logiczny. Dane sterujące są zwykle przekazywane do funkcji jako parametr (y).

2. Ciało, gdzie praca została wykonana. Czasami ciało łączy się z kolejną częścią.

3. Sposób zmiany danych "kontrolujących". Często poprzez zmianę licznika.

4. Droga ponownie powołując konstrukt (w tym przypadku funkcja.) - co oznacza, że ​​wywołanie funkcji (i pamiętać, aby przekazać zmieniony „Sterowanie” dane

Należy o nie dziwnego, że obie konstrukcje mają te same części, ponieważ są one równoważne.

Answer 4

Weźmy proste zadanie. drukowania numerów od 1 do 10. użyję Python2.7 tutaj.

for i in range(1,11): 
    print i 

Teraz spróbujmy zrobić to samo, używając rekursji.

>>> def print_me(n): 
    if n > 0: 
     print_me(n - 1) 
     print n 
    else: 
     return 

>>> print_me(10) 
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 

Jak o tym myślimy?

• Step1: Pomyśl o moich granicach. Potrzebuję dwóch. 1 i 10. Następnie.
• Step2: Instrukcja drukowania. To nasz motyw. Aby wydrukować liczby. I chcemy to od 1 do 10. Więc muszę najpierw wydrukować 1.

• Step3: Zaczynamy od napisania funkcji, która wykonuje zadanie drukowania numeru przekazanego jako argument. Pomyślmy tylko o głównym zadaniu .

  def print_me (n): druku n

• Etap 4: I chce funkcję powrotu, gdy n < 1.

  def print_me (n): gdy n> 0 : druk n else: powrót

• Krok 5: teraz chcę przekazać numery, f od 1 do 10 do tej funkcji, ale nie chcemy pętli od 1 do 10, a następnie przekazujemy ją do naszej funkcji. Mamy chcemy, żeby to było wykonywane rekurencyjnie.

Co to jest rekursja? W prostych słowach, wielokrotne zastosowanie procedury rekursywnej lub definicji.

Aby więc było rekursywne, musimy wywołać samą funkcję. I chcemy przekazać naszą zakresie od 1 do 10.

def print_me(n): 
    if n > 0: 
     print_me(n - 1) 
     print n 
    else: 
     return 

podsumowując: Wszystkie połączenia rekurencyjne muszą przestrzegać 3 ważne zasady:

1. rekurencyjna algorytm musi mieć przypadek bazowy.
2. Algorytm rekursywny, MUSI zmienić jego stan i przejść w kierunku podstawy .
3. Algorytm rekursywny MUSI wywoływać sam siebie, rekursywnie.

Źródło: interactivepython

Inny program w JavaScript, aby znaleźć silnia:

function factorial(n){ 
    if (n == 1) 
     { 
     return 1; 
     } 
    else { 
     return n * factorial(n-1); 
     } 
} 

Answer 5

Oto mój prosty test w Pythonie:

def p(l, index): 
    if index == len(l): 
     return 
    else: 
     print l[index] 
     index = index + 1 
     p(l, index) 

i zadzwoń:

p("123456", 0)